3.3. Бинарные деревья
3.3.1. Определение. Представления бинарных деревьев
Бинарное (двоичное) дерево — особый вид дерева, в котором каждый узел имеет не более двух поддеревьев, причем в случае одного поддерева следует различать левое и правое поддерево. При изображении бинарных деревьев левого и правого сына различают по наклону соединительной линии (влево или вправо). На рис.3.4 показаны два различных бинарных дерева. Интересно отметить, что если рассматривать данные структуры как обычные упорядоченные деревья, то они являются полностью идентичными (в упорядоченном дереве единственный сын всегда первый, т. е. левый потомок). Это говорит о том, что бинарные деревья не являются частным случаем упорядоченого дерева, а представляют собой особый вид деревьев.
Рис.3.5. Два различных бинарных дерева
Приведем формальное рекурсивное определение бинарного дерева [8].
Бинарное дерево — конечное множество узлов, которое является пустым или состоит из корня и двух непересекающихся бинарных деревьев, которые называются левым и правым поддеревьями данного корня.
Обратим внимание на то, что бинарное дерево может быть пустым, в отличие от обычного дерева, которое всегда содержит хотя бы один узел (однако лес может быть пустым).
Бинарное дерево может быть представлено и в форме скобочного выражения. Аналогично обычному корневому дереву, для бинарного дерева также возможен различный порядок перечисления узлов в скобочном представлении. Например, левое скобочное представление непустого бинарного дерева рекурсивно определяется так:
Иногда при записи левое и правое поддерево разделяют запятыми, но чаще пробелом.
Левое или правое поддерево или оба вместе (для листьев) могут быть пустыми, при этом для пустых деревьев часто используется специальное обозначение . Чтобы сократить запись, в ней разрешается опустить правое поддерево, если оно пустое, а для листьев опустить оба пустых поддерева (но нельзя опускать пустое левое поддерево, иначе по такой записи нельзя будет правильно восстановить изображение бинарного дерева!). Так, деревьям, изображенным на рис.3.5, соответствуют различные левые скобочные записи в сокращенной форме:
Бинарные деревья, у которых все узлы, кроме листьев, имеют сторого по два сына, называются строго бинарными. Деревья, изображенные на рис. 3.5, не являются строго бинарными.
3.3.2. Математические свойства бинарных деревьев
Бинарные деревья, как абстрактные математические объекты, обладают рядом интересных свойств, которые могут пригодиться при анализе различных алгоритмов, поэтому остановимся подробнее на этом вопросе.
На любом уровне n бинарное дерево может содержать от 1 до 2 n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. На рис. 3.6 дерево А содержит 8 узлов при высоте 3, в то время как дерево B содержит 5 узлов при высоте 4.
Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (e) и каждый внутренний узел имеет только одного сына. Вырожденное дерево можно считать аналогом линейного связного списка, его высота равна количеству узлов без единицы. Это максимально возможное значение для высоты бинарного дерева. В большинстве алгоритмов, использующих бинарные деревья, вырожденное дерево — наихудший случай при оценке производительности.
Рис.3.6. Бинарные деревья различной плотности
Наоборот, деревья с большой плотностью очень важны в качестве структур данных, так как они содержат пропорционально больше элементов вблизи корня, т.е. с более короткими путями от корня.
Наивысшей степенью плотности обладают полные бинарные деревья, которые имеют 2 k узов на каждом уровне k.
Рис.3.7. Полное и почти полное бинарные деревья
На рис. 3.7, а показано полное бинарное дерево высоты два. Обратим внимание на такие факты.
На нулевом уровне имеется 2 0 узлов, на первом — 2 1 , на втором — 2 2 и т.д. На первых k-1 уровнях количество узлов составляет
1 + 2 + 4 + . + 2 k-1 = 2 k -1
На уровне k количество узлов 2 k , т. е. ровно на один больше.
Из этого следует, что в полном бинарном дереве количество внутренних узлов на единицу меньше количества листьев. Зная количество листьев, легко определить и высоту h полного бинарного дерева:
h=log 2 n, где n — количество листьев
h= log 2 (N+1)-1, где N —количество узлов полного бинарного дерева.
Для полного бинарного дерева приведенные формулы дают точное значение, сответствующее минимальному значению высоты при таком количестве узлов. Если количество узлов дерева такое, что невозможно построить полное бинарное дерево, для получения бинарного дерева минимально возможной высоты необходимо заполнять все уровни дерева, кроме последнего, максимально возможным количеством узлов. Если оставшиеся узлы располагать на последнем уровне по порядку, начиная слева, то полученное таким образом бинарное дерево называют почти полным. На рис. 3.7, б изображено пости полное бинарное дерево.
Полные и почти полные бинарные деревья обладают еще одним интересным свойством — если их узлы нумеровать, начиная с единицы, сверху вниз и слева направо, то левому сыну всегда будет соответствовать код, в два раза больше кода его родителя, а правому сыну — код, на единицу больший, чем код код левого сына (рис.3.8). Номер корня всегда равен 1, его левый потомок получает номер 2, правый — номер 3. Левый потомок узла 2 получит номер 4, а правый — 5, левый потомок узла 3 получит номер 6, правый — 7 и т.д. Такая схема нумерации используется при представлении деревьев с помощью массивов. К этой теме мы еще вернемся.
Рис.3.8. Нумерация узлов полного или почти полного бинарного дерева
По такой схеме можно нумеровать и узлы бинарных деревьев, которые не являются почти полными, поскольку в этом случае гарантируется уникальность каждого номера, если в процессе работы к дереву добавляются новые листья. Используя такой способ нумерации, можно реализовать древовидную структуру на основе массива. Такая реализация будет приведена в главе 4.
После анализа основных свойств бинарных деревьев можно снова вернуться к упорядоченным деревьям и лесам и проанализировать соответствие между этими структурами и бинарным деревом.
Источник
Бинарные деревья
Хотя деревья общего вида достаточно важны, мы сосредоточимся на ограниченном классе деревьев, где каждый родитель имеет не более двух сыновей (рис. 4). Такие бинарные деревья (binary trees) имеют унифицированную структуру, допускающую разнообразные алгоритмы прохождения и эффективный доступ к элементам. Изучение бинарных деревьев дает возможность решать наиболее общие задачи, связанные с деревьями, поскольку любое дерево общего вида можно представить эквивалентным ему бинарным деревом.
У каждого узла бинарного дерева может быть 0, 1 или 2 сына. По отношению к узлу слева будем употреблять термин левый сын (left child), а по отношению к узлу справа – правый сын (right child). Наименования «левый» и «правый» относятся к графическому представлению дерева. Бинарное дерево является рекурсивной структурой. Каждый узел – это корень своего собственного поддерева. У него есть сыновья, которые сами являются корнями деревьев, называемых левым и правым поддеревьями соответственно. Таким образом, процедуры обработки деревьев рекурсивны.
Дадим рекурсивное определение бинарного дерева.
Бинарное дерево — это такое множество узлов B, что
а) B является деревом, если множество узлов пусто (пустое дерево – тоже дерево);
б) B разбивается на три непересекающихся подмножества:
Рис.4. Пример бинарного дерева
На любом уровне n бинарное дерево может содержать от 1 до 2n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. Интуитивно плотность есть мера величины дерева (число узлов) по отношению к глубине дерева. На рис. 4 дерево А содержит 8 узлов при глубине 3, в то время как дерево B содержит 5 узлов при глубине 4. Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (E) и каждый нелистовой узел имеет только одного сына. Вырожденное дерево эквивалентно связанному списку.
Рис.5. Бинарные деревья различной плотности
Деревья с большой плотностью очень важны в качестве структур данных, так как позволяют хранить большие коллекции данных и осуществлять эффективный доступ к элементам. Быстрый поиск – главное, что обусловливает использование деревьев для хранения данных.
Вырожденные деревья имеют наименьшую плотность (1). Другая крайность – законченные бинарные деревья (complete binary tree) глубины N, где каждый уровень 0, 1, . N-1 имеет полный набор узлов, и все листья уровня N расположены слева. Законченное бинарное дерево, содержащее 2N узлов на уровне N, является полным. На Рис. 6 показаны законченное и полное бинарные деревья.
Законченные и полные бинарные деревья дают интересные математические факты. На нулевом уровне имеется 2 0 узлов, на первом — 2 1 , на втором — 2 2 и т.д. На первых k-1 уровнях имеется 2 k-1 узлов.
1 + 2 + 4 + . + 2 k-1 = 2 k -1
На уровне k количество дополнительных узлов колеблется от 1 до 2k (полное). В полном дереве число узлов равно
1 + 2 + 4 + . + 2 k-1 + 2 k = 2 k-1 — 1
Число узлов законченного бинарного дерева удовлетворяет неравенству
2 k N 2 k-1 — 1 2 k-1
Решая его относительно k, имеем
k log2 (N) k+1
Например, полное дерево глубины 3 имеет
2 4 — 1 = 15 узлов
Рис.6. Классификация бинарных деревьев
Структура бинарного дерева
Структура бинарного дерева состоит из узлов (рис.7). Как и в связанном списке, эти узлы содержат поля данных и указатели на другие узлы в коллекции. В этом разделе мы определим узлы дерева и операции для его построения и прохождения. Объявим класс TreeNode, реализующий функциональность узла дерева, и разработаем ряд функций, позволяющих создавать бинарные деревья и осуществлять прохождение по их узлам.
Узел дерева содержит поле данных и два поля с указателями. Поля указателей называются левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево, соответственно. Значение NULL является признаком пустого дерева.
Рис.7. Структура узлов дерева
Корневой узел определяет входную точку дерева, а поля указателей – узлы следующего уровня. Листовой узел содержит NULL в полях правого и левого указателей. Пример представления структуры дерева дан на рис. 8.
Рис.8. Представление структуры дерева
Источник