4-дерево - Большая Энциклопедия Нефти и Газа, статья, страница 2
Еще никто так, как русские, не глушил рыбу! (в Тихом океане - да космической станцией!) Законы Мерфи (еще...)

4-дерево

Cтраница 2


На рис. 13.13 представлено посроение 2 - 3 - 4-дерева для тестового набора ключей. В отличие от стандартных BST-деревьев, которые разрастаются вниз от вершины, эти деревья разрастаются вверх от нижней части. Поскольку 4-узлы разделяются на пути от вершины вниз, деревья называются нисходящими 2 - 3 - 4-деревьями. Этот алгоритм важен, поскольку он создает практически идеально сбалансированные деревья поиска, хотя в процессе прохождения по дереву выполняются всего лишь несколько локальных преобразований.  [16]

17 Бинарные изображения для упр. 3. [17]

Коротко обсудите эффект переходов и поворотов для представления в виде 4-дерева.  [18]

19 Бинарные изображения для упр. 3. [19]

Предположим, что мы используем следующую структуру данных для представления 4-дерева. Каждая вершина представлена записью с четырьмя указателями на дочерние вершины, указателем на родительскую вершину и полем, показывающим тип вершины.  [20]

Только для разделений, которые в 2 - 3 - 4-дереве соответствуют 3-узлу, соединенному с 4-узлом, требуется ротация в RB-дереве; таким образом эта лемма - следствие леммы 13.2. Худший случай возникает тогда, когда путь к точке вставки состоит из чередующихся 3-узлов и 4-узлов.  [21]

Кавагучи и др. [6.12] предложили представление 4-дерева, использующее список листьев 4-дерева, соответствующий перебору в глубину. Этот список представляет собой строку, состоящую из символов (, 5, И7, соответствующих меткам серый, черный и белый соответственно.  [22]

Помечивание связанных компонентов в области объекта требует четкого определения связанности для представления в виде 4-дерева.  [23]

Определение 13.2 Сбалансированное 2 - 3 - 4-дерево поиска - это 2 - 3 - 4-дерево поиска, все пустые деревья которого расположены на одинаковом расстоянии от корня.  [24]

На этой последовательности рисунков показан результат вставки элементов с ключами А SERCHINGXe первоначально пустое 2 - 3 - 4-дерево. Каждый встречающийся по пути поиска 4-узел разделяется, обеспечивая тем самым свободное место для нового элемента в нижней части дерева.  [25]

Создайте программу, которая вычисляет процент элементов, находящихся в 3-узлах и 4-узлах заданного 2 - 3 - 4-дерева поиска.  [26]

Действительно, лежащую в их основе абстракцию можно непосредственно обобщить и реализовать В-деревья, обобщив реализации нисходящего 2 - 3 - 4-дерева, описанные в разделе 13.4. Однако, различия между внешним и внутренним поиском, упомянутые в разделе 16.1, приводят к ряду различий в реализациях.  [27]

А теперь давайте рассмотрим альтернативный подход к разработке алгоритма с использованием сбалансированного дерева, заключающийся в полном игнорировании абстракции 2 - 3 - 4-дерева и формулировании алгоритма вставки, который сохраняет определяющее свойство сбалансированных RB-деревьев бинарного поиска за счет применения ротаций. Например, использование восходящего алгоритма соответствует присоединению нового узла в нижней части пути поиска с помощью R-связи, затем продвижению вверх по пути поиска с выполнением ротаций или изменений цвета, как это делалось в случаях, представленных на рис. 13.17, с целью разбиения любой встретившейся пары последовательных R-связей. Основные операции не отличаются от выполняемых в программе 13.6 и в ее восходящем аналоге, но при этом имеются незначительные различия, поскольку 3-узлы могут быть ориентированы в любом направлении, операции могут выполняться в ином порядке и различные решения в отношении различных ротаций могут приниматься с равным успехом.  [28]

Результирующее 4-дерево называют / ( - деревом квадрантов, поскольку всего 16 примитивных визуальных образов использованы вместо двух примитивных визуальных образов в исходном представлении в виде 4-дерева. Очевидно, что / ( - дерево квадрантов имеет меньше вершин, чем исходное 4-дерево, и операции соответственно ускоряются.  [29]

Таким образом, можно воспользоваться лучшим из обоих подходов: простой метод поиска, присущий стандартному BST-дереву, и простой метод вставки-балансировки, характерный для 2 - 3 - 4-дерева поиска.  [30]



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