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.
После анализа основных свойств бинарных деревьев можно снова вернуться к упорядоченным деревьям и лесам и проанализировать соответствие между этими структурами и бинарным деревом.
Источник
Деревья поиска
Дерево — одна из наиболее распространенных структур данных в программировании.
Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой (вершина 8 на рисунке), можно дойти до всех остальных единственным способом.
- Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
- Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
- Предки — родители родителей, их родители, и так далее.
- Потомки — дети детей, их дети, и так далее.
- Лист (терминальная вершина) — вершина, не имеющая детей.
- Поддерево — вершина дерева вместе со всеми её потомками.
- Степень вершины — количество её детей.
- Глубина вершины — расстояние от корня до неё.
- Высота дерева — максимальная из глубин всех вершин.
Деревья чаще всего представляются в памяти как динамически создаваемые структуры с явными указателями на своих детей, либо как элементы массива связанные отношениями, неявно определёнными их позициями в массиве.
Деревья также используются в контексте графов.
Бинарные деревья поиска
Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:
- У каждой вершины не более двух детей.
- Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
- У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
- У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
Более общим понятием являются обычные (не бинарные) деревья поиска — в них количество детей может быть больше двух, и при этом в «более левых» поддеревьях ключи должны быть меньше, чем «более правых». Пока что мы сконцентрируемся только на двоичных, потому что они проще.
Чаще всего бинарные деревья поиска хранят в виде структур — по одной на каждую вершину — в которых записаны ссылки (возможно, пустые) на правого и левого сына, ключ и, возможно, какие-то дополнительные данные.
Как можно понять по названию, основное преимущество бинарных деревьев поиска в том, что в них можно легко производить поиск элементов:
Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.
Источник