Bst-дерево - Большая Энциклопедия Нефти и Газа, статья, страница 2
Жизнь, конечно, не удалась, а в остальном все нормально. Законы Мерфи (еще...)

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]

29 ПОИСК И ВСТАВКА В ДЕРЕВО БИНАРНОГО ПОИСКА В процессе успешного поиска Не этом примере дерева ( вверху мы перемещаемся вправо от корня ( поскольку Н больше чем А, затем влево в правом поддереве ( поскольку Н меньше нем S и т.д., продолжая перемещаться вниз по дереву, пока не встретится Н. В процессе неуспешного поиска М в этом примере дерева ( в центре мы перемещаемся вправо от корня ( поскольку М больше нем А, затем влево в правом поддереве корня ( поскольку М меньше чем S и т.д., продолжая перемещаться вниз по дереву, пока не встретится внешняя связь слева от Ne нижней части диаграммы. Для вставки М после обнаружения промаха при поиске достаточно просто заменить связь, которая прерывает поиск, связью с М ( внизу. [29]

При наличии этой структуры рекурсивный алгоритм поиска ключа в BST-дереве становится очевидным: если дерево пусто, имеет место промах при поиске; если ключ поиска равен ключу в корне, имеет место попадание при поиске. В противном случае выполняется поиск ( рекурсивно) в соответствующем поддереве. Функция searchR в программе 12.8 непосредственно реализует этот алгоритм. Мы вызываем рекурсивную подпрограмму, которая принимает дерево в качестве первого аргумента и ключ в качестве второго, начиная с корня дерева и искомого ключа. На каждом шаге гарантируется, что никакие части дерева, кроме текущего поддерева, не могут содержать элементы с искомым ключом.  [30]



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