Бинарные деревья

Cтраница 3

Можно было бы воспользоваться связным представлением пирамидально упорядоченных деревьев, но полные деревья предоставляют возможность задействовать компактное представление в виде массива, в котором легко переходить с некоторого узла к его родителю или к его предкам без необходимости поддержки явных связей. Полные бинарные деревья, представленные в виде массивов, являются жесткими структурами, но все же обладают достаточной гибкостью, чтобы позволить реализовать эффективные алгоритмы, манипулирующие очередями по приоритетам. [31]

Пусть f5 - средний вес и бп, Вп и Мп - математические ожидания взвешенных длин путей оптимального сбалансированного ( относительно числа узлов) и монотонного деревьев бинарного поиска соответственно, построенных по этим последовательностям весов. Эти случайные бинарные деревья служат основой оценки эффективности других алгоритмов; если оказывается, что деревья, построенные в соответствии с некоторым эвристическим принципом, несущественно лучше случайных деревьев, то эвристика сомнительна. [32]

Группировки в попарные произведения. [33]

Такой граф содержит 2п - 1 вершин, не являющихся конечными. Например, на рис. 2.12 изображены бинарные деревья с корнем, отвечающие пяти различным способам перемножения элементов а, Ь, с, d; ассоциативность умножения не предполагается ( ср. [34]

Сравним алгоритм IDS с ДРЕВ и АМХ. Первые два из рассмотренных выше алгоритмов строят только бинарные деревья решений, тогда как каждый узел в дереве, построенном алгоритмом Л) 3, может иметь более двух потомков. Это обусловлено тем, что в алгоритме IDS на каждом шаге определяется важнейший признак, а в алгоритмах ДРЕВ и АМХ - важнейшее ( разделяющее) значение признака. [35]

Есть и другие возможности, которые мы, однако, не собираемся здесь обсуждать. К ним относятся древовидные сети, процессоры в которых образуют бинарные деревья, а также гиперкубы, обобщающие двумерную решетку на три и более измерений. [36]

Основная идея заключается в представлении 2 - 3 - 4-деревьев в виде стандартных BST-деревьев ( содержащих только 2-узлы), но с добавлением к каждому узлу дополнительного информационного разряда для кодирования 3-узлов и 4-узлов. Мы будем представлять связи двумя различными типам связей: красными ( red) связями ( R-связями), которые объединяют воедино небольшие бинарные деревья, образующие 3-узлы и 4-узлы, и черными ( black) связями ( В-связями), которые объединяют воедино 2 - 3 - 4-дерево. [37]

Как и следовало ожидать, существует много способов для представления Списочных структур в памяти машины. Обычно все они являются вариациями на одну и ту же основную тему, согласно которой для представления общих лесов деревьев используются бинарные деревья: одно поле, скажем RL1NK, используется для указания на следующий элемент Списка, а другое поле DLINK можно использовать для указания на первый элемент под - Списка. [38]

Поскольку а0 не накладывает ограничений вообще, WB [0] представляет собой класс всех бинарных деревьев. Случай а1 / 2 означает, что левое и правое noRi деревья каждого узла содержат одинаковое число узлов; поэтому WB l1 / ] принадлежат только полностью сбалансированные бинарные деревья с п 2Л - 1 узлами. [39]

Такое простое и естественное представление в памяти ЭВМ объясняет особую важность структур типа бинарных деревьев. Помимо того что произвольные деревья можно легко представить с помощью бинарных деревьев, многие деревья, возникающие в прикладных вопросах, по своему существу являются бинарными, поэтому-то бинарные деревья и вызывают такой повышенный интерес. [40]

Если в табличном представлении произвести лексикографическое упорядочение и сделать склейку по совпадающим префиксам, то получается древовидное представление данных, в основе которого лежит понятие дерева. Такое представление ведет к большей компактности данных и к ускорению поиска нужных данных. Такие древовидные структуры, как бинарные деревья, 2 - 3-деревья, В-деревья, сортирующие деревья [10] используются для внутреннего представления данных. Древовидное представление удобно использовать в лингвистических и подобных им БД, например, когда надо найти то или иное слово. Древовидное представление все еще достаточно просто для понимания, хотя и не так наглядно как табличное. [41]

Пусть Р указывает на узел в некотором бинарном дереве, и пусть HEAD - адрес головы списка пустого бинарного дерева. Предложите алгоритм, который убирает узел NODE ( Р) и вес его поддеревья из произвольного дерева, где он был, и который привязывает поддерево с корнем NODE ( P) к HEAD. Предположите, что все рассматриваемые в этой задаче бинарные деревья право-прошитые с полями LLINK, RTAG, RLINK. [42]

В их статье вводится также важная идея прохождения деревьев различными путями и приводятся многочисленные примеры алгоритмов алгебраических манипуляций. К сожалению, эта важная статья готовилась в спешке и содержит множество опечаток. В нашей терминологии прошитые списки Пирлиса и Торнтона являются всего лишь право-прошитыми деревьями; бинарные деревья, которые прошиваются в обоих направлениях, были независимо открыты А. [43]

Мы увидим ниже, что эти три способа расстановки узлов бинарного дерева в последовательность чрезвычайно важны, поскольку они используются во многих вычислительных методах, применяемых к деревьям. Название прямой порядок отражает тот факт, что каждый корень проходится прежде своего левого поддерева); при обратном порядке каждый корень проходится после своего левого поддерева. Эта терминология оправдывается тем особым значением, которое придается левым поддеревьям, когда для представления обычных деревьев используются бинарные деревья. Об этом более подробно будет сказано в следующем пункте. [44]

Пустое бинарное дерево, не имеющее ни корня, ни поддеревьев, удовлетворяет этим условиям и, следовательно, является сбалансированным по высоте. Дерево с единственным узлом является сбалансированным по высоте в соответствии с соглашением о высоте пустого дерева. На рис. 6.13 показаны некоторые сбалансированные по высоте деревья и одно бинарное дерево, не являющееся таковым. Ограничение высоты предупреждает сбалансированные по высоте бинарные деревья от слишком большого уклонения от полностью сбалансированного бинарного дерева. [45]

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