высота = 4, глубина 0, глубина 1 и т.п.

Рис. 5.6 (а) Корневое дерево высоты 4. Дерево нарисовано обычным образом: корень (вершина 7) нарисована сверху, соседние с ним вершины (дети корня, вершины глубины 1) нарисованы под ней, вершины следующего уровня (дети детей корня, вершины глубины 2) под ними и т. д. Для деревьев с порядком на детях для каждой вершины фиксирован порядок на множестве её детей, (б) То же самое корневое дерево, но с другим порядком (среди детей вершины 3), будет другим деревом с порядком на детях.

зу «вершина является своим собственным потомком» можно толковать по разному, и при одном толковании она верна, а при другом нет.]

Для каждой вершины ж можно рассмотреть дерево, состоящее из всех потомков ж, в котором ж считается корнем. Оно называется поддеревом с корнем в ж (subtree rooted at ж). Например, на рис. 5.6 (а) поддерево с корнем в 8 содержит вершины 8, 6, 5 и 9.

Если (у, ж) - последнее ребро на пути из корня в ж, то у называется родителем (parent) ж, а ж называется ребёнком у. [Раньше вместо «родитель» и «ребёнок» говорили «отец» (father) и «сын»(son), что было более логично, так как вообще-то у человека двое родителей, а у вершины дерева - не более одного. Зато принятая теперь в американской литературе терминология «политически корректна».]

Корень является единственной вершиной, у которой нет родителя. Вершины, имеющие общего родителя, называют в американской литературе siblings; к сожалению, русского перевода у этого слова нет, и мы будем (как это делалось раньше) называть такие вершины братьями. Вершина корневого дерева, не имеющая детей, называется листом (leaf, external node). Вершины, имеющие детей, называются внутренними (internal).

Число детей у вершины корневого дерева называется её степенью (degree). Отметим, что для всех вершин, кроме корня, степень на единицу меньше степени той же вершины в том же дереве, если рассматривать дерево как неориентированный граф (поскольку тогда надо учитывать и ребро, идущее вверх). Длина пути от корня до произвольной вершины ж называется глубиной (depth) вершины ж. Максимальная глубина вершин дерева называется высотой

Рис. 5.7 Двоичные деревья, (а) Двоичное дерево, изображённое традиционным образом. Левый ребёнок вершины нарисован слева-снизу от неё, правый - справа-снизу, (б) Другое двоичное дерево (отличие в том, что теперь у вершины 7 есть правый ребёнок 5 и нет левого, а не наоборот). Такое различие возможно в двоичном дереве, но не в дереве с порядком на детях, (в) Добавляя дополнительные листья к дереву (а), мы получаем дерево, у которого каждая старая вершина имеет двух детей. Добавленные листья изображены квадратиками.

(height) дерева.

Деревом с порядком на детях (ordered tree) называется корневое дерево с дополнительной структурой: для каждой вершины множество её детей упорядочено (известно, какой её потомок первый, какой второй и т. д.). Два дерева на рис. 5.6 одинаковы как корневые деревья, но различны как деревья с порядком на детях.

5.5.3. Двоичные деревья. Позиционные деревья

Двоичное дерево (binary tree) проще всего определить рекурсивно как конечный набор вершин, который

•либо пуст (не содержит вершин),

•либо разбит на три непересекающиеся части: вершину, называемую корнем (root), двоичное дерево, называемое левым поддеревом (left subtree) корня, и двоичное дерево, называемое правым поддеревом (right subtree) корня.

Двоичное дерево, не содержащее вершин, называется пустым (empty). Оно иногда обозначается NIL. Если левое поддерево непусто, то его корень называется левым ребёнком (left child) корня всего дерева; правый ребёнок (right child) определяется аналогично. Если левое или правое поддерево корня пусто, то говорят, что у корня нет левого или правого ребёнка (child is absent). Пример двоичного дерева показан на рис. 5.7 (а).

Было бы ошибкой определить двоичное дерево просто как дерево с порядком на детях, в котором степень каждой вершины не превосходит 2. Дело в том, что в двоичном дереве важно, каким является единственный ребёнок вершины степени 1 - левым или

высота=3, глубина 0, глубина 1 и т.п.

Рис. 5.8 Полное двоичное дерево высоты 3 имеет 8 листьев и 7 внутренних вершин.

правым, а для дерева с порядком на детях такого различия не существует. На рис. 5.7 (а,б) показаны два различных двоичных дерева, которые одинаковы как деревья с порядком на детях.

Пустующие места в двоичном дереве часто заполняют фиктивными листьями. После этого у каждой старой вершины будет двое детей (либо прежних, либо добавленных). Это преобразование показано на рис. 5.7 (в).

Можно определить аналоги двоичных деревьев для деревьев большей степени: двоичные деревья являются частным случаем к-ичных (/г-агу) деревьев при к = 2. Более подробно, позиционное дерево (positional tree) определяется как корневое дерево, в котором дети любой вершины помечены различными целыми положительными числами, которые считаются их номерами. При этом у каждой вершины есть вакансии для детей номер 1, 2, 3 и так далее, из которых некоторые (конечное число) заполнены, а остальные свободны (ith child is absent). При этом /г-ичным деревом называется позиционное дерево, не имеющее вершин с номерами больше к.

Полным /г-ичным деревом (complete /г-ary tree) называется к-ичное дерево, в котором все листья имеют одинаковую глубину и все внутренние вершины имеют степень к. (Тем самым структура такого дерева полностью определяется его высотой.) На рис. 5.8 показано полное двоичное дерево высоты 3. Подсчитаем, сколько листьев имеет полное /г-ичное дерево высоты h. Корень является единственной вершиной глубины 0, его к детей являются вершинами глубины 1, их детьми являются к2 вершин глубины к и так далее вплоть до kh листьев глубины h. Можно добавить, что высота /г-ичного дерева с п листьями равна logk п (такое дерево существует, только если этот логарифм целый). Число внутренних вершин полного /г-ичного дерева высоты h равно

l + k + k2 + ... + kh-l = k-

к - 1

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