Определение полного бинарного дерева звучит так: «Полное бинарное дерево — это бинарное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы максимально левые». Я хотел знать, почему последний уровень может быть частично заполнен. Помогает ли это в некоторых ситуациях/случаях?
Я пытался найти ответ на этот вопрос во многих местах, но не смог найти удовлетворительного ответа. Может кто-нибудь, пожалуйста, помогите мне, ответив на это. Большое спасибо...
Другой взгляд на этот вопрос, чем на другой ответ: если все уровни должны быть полностью заполнены, у вас могут быть деревья только с (2^n)-1 элементами для некоторых n. т.е. 1, 3, 7, 15, ... элементы. Разрешив частичное заполнение последнего уровня, вы можете иметь бинарные деревья с любым количеством элементов.
Это просто определение полного бинарного дерева. Это не обязательно помогает или мешает чему-то, это просто так, как есть.
Если вам интересна эта тема, поищите сбалансированные бинарные деревья. Там имеет смысл не заполнять полностью только самые нижние уровни, чтобы убедиться, что дерево сбалансировано, и у вас нет 10 узлов в глубину слева и 1 узла в глубину справа.
Полное заполнение всех уровней дерева гарантирует быстрое время поиска. Если все уровни полностью заполнены, вы знаете, что глубина дерева одинакова на всех возможных путях, что обеспечивает хорошую верхнюю границу скорости поиска. В таких случаях вы можете рассчитать глубину всех возможных путей листовых узлов с помощью D = floor(lg(N)), где N — количество узлов.
Теперь представьте, что у вас вообще не обязательно есть заполненные уровни. У вас может быть что-то вроде этого чудовища, где некоторые элементы будут загружаться намного быстрее, чем другие.
