Поддеревья

Cтраница 4

Пусть Тп - бинарное дерево с п 1 узлами, в котором корень имеет правое и левое поддеревья Т1; и Тг с / 0 и г О узлами соответственно. [46]

Заметим, что по определению числа D ( с, I, К) при / 1 поддеревья в Т ( k) с корнями высоты h заменяются деревьями с единственным листом. ЧН длины с на всех листьях. [47]

Три правила построения нового AVL-дерева. [48]

В случае, когда X меньше, чем А, имеем аналогичную ситуацию, причем левее и правое поддеревья меняются местами. Таким образом, в любом случае мы должны построить дерево НовДер, используя три дерева ( назовем их Дер1, Дер2 и ДерЗ) и два отдельных элемента А и В. Теперь рассмотрим вопрос: как соединить между собой эти пять составных частей, чтобы дерево НовДер было AVL-справочником. [49]

Конечное множество, в котором выделен один элемент ( корень), а остальные элементы разбиты на непересекающиеся множества ( поддеревья), каждое из которых является деревом; ориентированный граф, в котором имеется ровно одна вершина ( корень дерева), не имеющая входящих ребер, а в каждую из остальных вершин входит ровно одно ребро. D Связный граф без циклов. [50]

О Поиск вершины дерева, удовлетворяющей некоторому условию или оптимизирующей некоторую функцию; поиск начинается с корпя и распространяется на поддеревья, См. [51]

Указание: если Т - дерево с п узлами из WB [ a ], a левое и правое его поддеревья содержат I и г узлов соответственно, то существует лишь около ( 1 - 2а) п возможных различных значений I и г, и все они равновероятны. [52]

Группа G подстановок, относительно которых раскраски дерева инвариантны, порождается тремя подстановками, показанными на рис. 3.2; эти подстановки переставляют поддеревья с узлами 1, 2 и 3 соответственно. Компактным способом представления подстановок является циклическая запись. [53]

Предположим, что каждый узел бинарного дерева имеет четыре поля связи; LLINK и RLINK, которые указывают на левое и правое поддеревья либо равны Л, как в непрошитом дереве, и SUC и PRED, которые указывают на преем. Такое дерево содержит больше информации, чем прошитое дерево. Разработайте алгоритм, аналогичный алгоритму I, для включений в такое дерево. [54]

Если все поддеревья узла SU уже исследованы, так что порождены все клики, включающие S ( J x, то все неисследованные поддеревья с корнями Su можно проигнорировать. [55]

По окончании разрезания дерева с корнем в вершине х удалим х из множества вершин W, обладающих тем свойством, что все их поддеревья разрезаны. Выбираем другую вершину из И7 и разрезаем соответствующее поддерево. Как только множество W будет исчерпано, алгоритм заканчивает свою работу: оптимальное разрезание получено. [56]

В этом бинарном дереве каждый подфайл представлен своим разделяющим элементом ( или самим собой, если он имеет размер 1), и поддеревья каждого узла суть деревья, представляющие подфайлы после разделения. Дабы не загромождать рисунок, нулевые подфайлы на нем не показаны, хотя наши рекурсивные версии алгоритма выполняют рекурсивные вызовы при выполнении условия г1, когда разделяющим элементом становится наименьший или наибольший элемент файла. Само по себе дерево не зависит от очередности, в которой подфайлы подвергаются разделению. Наша рекурсивная реализация сортировки соответствует посещению узлов при их обходе в прямом порядке, а нерекурсивная реализация соответствует правилу посещения сначала наименьшего дерева. [57]

Для того чтобы определить, что называется длиной внешнего пути, дополним дерево специальными вершинами в тех местах, где в исходном дереве отсутствуют поддеревья. Причем будем предполагать, что все вершины должны быть одной и той же степени, а именно степени дерева. Следовательно, такое расширение дерева порождает вместо пустых ребер массу специальных вершин, которые, конечно, уже не имеют потомков. На рис. 4.19 показано такое расширенное специальными вершинами дерево с рис. 4.17, специальные вершины отмечены квадратиками. Длина внешнего пути теперь может быть определена как сумма длин путей всех специальных вершин. [58]

Эта запись соответствует лесу ( 1): мы представляем дерево, записывая сначала информацию, заложенную в его корне, а затем представляем его поддеревья. Таким образом, представлением непустого леса служит заключенный в скобки список представлений его деревьев, разделяемых запятыми. [59]

Пример весов узлов и взвешенных длин всех путей деревьев бинарного поиска из. [60]

Страницы: 1 2 3 4 5