Bst-дерево
Cтраница 2
При вставке узла в BST-дерево с использованием вставки с расширением мы не только перемещаем этот узел в корень, но и перемещаем все встретившиеся узлы ( в пути поиска) ближе к корню. [16]
Экспериментально определите увеличение высоты BST-дерева при выполнении длинной пск сдо щтгл1носп1Чфздую11и1ксч опсраиин вставки и удаления в произвольном дереве с Af узлами. [17]
Например, для построения BST-дерева, состоящего из 100000 узлов, с использованием вставки с расширением всегда требуется менее 5 миллионов сравнений. Это не гарантирует, что результирующее дерево поиска будет хорошо сбалансировано и что каждая операция будет эффективной, но тем не менее обеспечивает весьма значительную гарантию в отношении общего времени выполнения; на практике фактическое время выполнения, скорее всего, откажется еще меньшей. [18]
Модифицируйте стандартную функцию вставки в BST-дерево, приведенную в программе 12.8, чтобы она делила примерно пополам любой встреченный узел, который в одном из своих поддеревьев содержит менее одной четверти всех узлов. [19]
Применительно к алгоритму с использованием, BST-дерева главное следствие этого допущения заключается в том, что каждый узел дерева с равной вероятностью может оказаться корневым, причем это же справедливо и по отношению к поддеревьям. Как это ни удивительно, случайность можно включить в алгоритм, чтобы это свойство сохранялось без каких-либо допущений относительно порядка вставки элементов. Идея весьма проста: при вставке нового узла в дерево, состоящее из N узлов, вероятность появления нового узла в корне должна быть равна / ( N 1), поэтому мы просто принимаем рандомизованное решение использовать вставку в корень с этой вероятностью. В противном случае мы рекурсивно используем метод для вставки новой записи в левое поддерево, если ключ записи меньше ключа в корне, и в правое поддерево - если он больше. Программа 13.2 содержит реализацию этого метода. [20]
Эта последовательность отображает результат вставки G в BST-дерево, приведенное на верхнем рисунке, после ( рекурсивного) выполнения ротации после вставки с целью перемещения вставленного узла G в корень. Этот процесс эквивалентен вставке G с последующим выполнением последовательности ротаций для перемещения его в корень. [21]
Для удаления узла с данным ключом из BST-дерева вначале необходимо проверить, находится ли он в одном из поддеревьев. Если да, мы заменяем это поддерево результатом удаления ( рекурсивного) из него узла. Если удаляемый узел находится в корне, дерево заменяется результатом объединения двух поддеревьев в одно. Для выполнения такого объединения существует несколько возможностей. Один из возможных подходов проиллюстрирован на рис. 12.18, а реализация представлена в программе 12.16. Для объединения двух BST-деревьев, все ключи второго из которых заведомо больше ключей первого, ко второму дереву применяется операция partition с целью перемещения в корень наименьшего элемента в этом дереве. На данном этапе левое поддерево корня должно быть пустым ( иначе в нем располагался бы элемент, который меньше элемента в корне - явное противоречие), и задачу можно завершить, заменив эту связь связью с первым деревом. На рис. 12.19 показана последовательность удалений в примере дерева, которая иллюстрирует некоторые из возможных ситуаций. [22]
На рис. 12.15 и 12.16 показано создание BST-дерева путем вставки последовательности ключей в первоначально пустое дерево с использованием метода вставки в корень. Если последовательность ключей произвольна, построенное таким образом BST-дерево обладает совершенно теми же стохастическими свойствами, что BST-дерево, построенное стандартным методом. Например, леммы 12.6 и 12.7 справедливы и для BST-деревьев, построенных при помощи вставки в корень. [23]
Лемма 13.1 Построение рандомизованного BST-дерева эквивалентно построению стандартного BST-дерева из случайно переставленных в исходном состоянии ключей. Для конструирования рандомизованного BST-дерева из N элементов используется около 2 / VlnTV сравнений ( независимо от порядка вставки элементов), а для выполнения поиска в таком дереве требуется приблизительно 2 1пЛ сравнений. [24]
В разделе 13.2 рассматривается расширенное дерево - вариант BST-дерева, которое можно использовать для обеспечения таких гарантий при реализации таблиц символов. Этот алгоритм - вполне очевидное расширение метода вставок в корень, рассмотренного в главе 12, но аналитическое обоснование предельных значений производительности является достаточно сложным. [25]
На рис. 12.5 и 12.6 показан пример создания BST-дерева путем вставки последовательности ключей в первоначально пустое дерево. Новые узлы присоединяются к нулевым связям в нижней части дерева, а в остальном структура дерева никак не изменяется. Поскольку каждый узел имеет две связи, дерево растет скорее в ширину, нежели в высоту. [26]
Эта последовательность отображает результат ( внизу) разбиения примера BST-дерева ( вверху) на части расположенным практически посередине ключом; при этом применяется ( рекурсивно) ротация, как это делалось во время вставки в корень. [27]
Цель применения алгоритма с использованием сбалансированного дерева - сохранение BST-дерева максимально сбалансированным при сохранении эффективности вставки, удаления и других операций с ЛТД словаря. [28]
При наличии этой структуры рекурсивный алгоритм поиска ключа в BST-дереве становится очевидным: если дерево пусто, имеет место промах при поиске; если ключ поиска равен ключу в корне, имеет место попадание при поиске. В противном случае выполняется поиск ( рекурсивно) в соответствующем поддереве. Функция searchR в программе 12.8 непосредственно реализует этот алгоритм. Мы вызываем рекурсивную подпрограмму, которая принимает дерево в качестве первого аргумента и ключ в качестве второго, начиная с корня дерева и искомого ключа. На каждом шаге гарантируется, что никакие части дерева, кроме текущего поддерева, не могут содержать элементы с искомым ключом. [30]
Страницы: 1 2 3 4