Базовые структуры данных. Деревья, страница 2

Аналогично двоичным деревьям существуют деревья большей степени: двоичные деревья являются частным случаем k-ичных (k-ary) деревьев при k=2. Более подробно, позиционное дерево (positional tree) определяется как корневое дерево, в котором дети для любой вершины помечены целыми положительными числами – номерами от 1 до k, причем некоторые из них (конечное число) заполнены, а остальные свободны. При этом k-ичным деревом называется позиционное дерево, степень каждой вершины которого не превосходит k.

Полным k-ичным деревом (complete k-ary tree) называется k-ичное дерево, в котором все листья имеют одинаковую глубину и все внутренние вершины имеют степень k. Логично заметить, что структура такого дерева полностью определяется его высотой. Подсчитаем, сколько листьев имеет полное k-ичное дерево. Корень является единственной вершиной с глубиной 0, его k детей являются вершинами глубины 1, у ребенка есть своих k детей, значит на глубине 2 количество вершин k². Таким образом на глубине h находится k^h листьев. Легко заметить, что высота полного k-ичного дерева с количеством вершин n равна log_kn (такое дерево существует, только если логарифм есть целое число). Число внутренних вершин полного k-ичного дерева высоты h равно

k^h – 1

1 + k + k² + … + k^h-1 =            .

k – 1

В частности для полного двоичного дерева число внутренних вершин на единицу меньше числа листьев.

2  Двоичные деревья поиска

В общем случае деревья поиска позволяют выполнять такие операции с динамическими множествами: поиск, минимальный, максимальный, предыдущий, следующий элемент, вставка, удаление. Таким образом, двоичные деревья поиска могут быть использованы как словарь, как очередь с приоритетами и т. д.

Время операций, выполняемых над двоичными деревьями поиска пропорционально их высоте. Если дерево плотно заполнено, то его высота будет равна log n, а значит и время, необходимое на выполнение операций будет пропорционально логарифму числа вершин. С другой стороны, если высота дерева n, то и время вырастет до  Θ(n). В случайных же деревьях высота поиска есть Ο(log n), поэтому время выполнения основных операций есть Θ(log n).

Очевидно, что возникающие на практике двоичные деревья далеки от случайных. Однако существуют методы, позволяющие балансировать деревья для обеспечения их максимально плотной заполненности. Некоторые из них будут рассмотрены в следующей лекции.

2.1  Что такое двоичное дерево поиска?

В двоичном дереве поиска (binary search tree) каждая вершина может иметь левого и/или правого ребенка, у каждой вершины, кроме корневой, есть родитель. При представлении такого дерева мы храним указатели p (на родителя),left (на левого ребенка) и right (на правого ребенка). Если какого-то из детей нет, указатель имеет нулевое значение.

Ключи в двоичном дереве поиска хранятся с соблюдением свойства упорядоченности:

если у некоторой вершины x есть левый ребенок, то его ключ не больше ключа x; если есть правый ребенок, то его ключ не меньше ключа x.

Данное свойство позволяет напечатать все элементы дерева в неубывающем порядке, используя простой рекурсивный алгоритм (именуемый inorder tree walk). При этом ключи левого поддерева печатаются перед ключом корня, который в свою очередь выводится перед ключами правого поддерева (кстати, в англоязычной литературе порядок, при котором значение корня выводится перед ключами его поддеревьев, называется preorder, а после – postorder). При этом свойство упорядоченности гарантирует правильность алгоритма, а его сложность на дереве с n вершинами есть Θ(n), поскольку каждая вершина обрабатывается точно один раз.