Cтраница 2
На рис. 13.13 представлено посроение 2 - 3 - 4-дерева для тестового набора ключей. В отличие от стандартных BST-деревьев, которые разрастаются вниз от вершины, эти деревья разрастаются вверх от нижней части. Поскольку 4-узлы разделяются на пути от вершины вниз, деревья называются нисходящими 2 - 3 - 4-деревьями. Этот алгоритм важен, поскольку он создает практически идеально сбалансированные деревья поиска, хотя в процессе прохождения по дереву выполняются всего лишь несколько локальных преобразований. [16]
Бинарные изображения для упр. 3. [17] |
Коротко обсудите эффект переходов и поворотов для представления в виде 4-дерева. [18]
Бинарные изображения для упр. 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]