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

Bst-дерево

Cтраница 4


46 КОНСТРУИРОВАНИЕ BST-ДЕРЕВА ПРИ ПОМОЩИ ВСТАВКИ В КОРЕНЬ ( ПРОДОЛЖЕНИЕ Эта последовательность отображает вставку ключей NGXMPLe BST-дерево, которое начинало создаваться на. [46]

Для реализации операции select можно использовать рекурсивную процедуру, аналогичную методу выбора с использованием быстрой сортировки, который описан в разделе 7.8. Для отыскания в BST-дереве элемента с k - м наименьшим ключом проверяется количество узлов в левом поддереве. Если там имеется k узлов, возвращается корневой элемент. В противном случае, если левое поддерево содержит более k узлов, отыскивается ( рекурсивно) А: - и наименьший узел в нем. Если ни одно из этих условий не соблюдается, то левое поддерево содержит г элементов при t k, н Ar - й наименьший элемент в BST-дереве является ( k - t - 1) - м наименьшим элементом в правом поддереве. Программа 12.14 содержит реализацию описанного метода.  [47]

Деревья бинарного поиска можно определить таким образом, чтобы индексы строились в точности так же, как при обеспечении косвенного метода для сортировки в разделе 6.8 и для сортирующих деревьев в разделе 9.6: необходимо использовать контейнер Index для определения элементов BST-дерева и обеспечить, чтобы ключи извлекались из элементов, как обычно, через функцию-члена key. Используются три массива: для элементов, левых связей и правых связей.  [48]

При использовании BST-деревьев реализация функции sort требует незначительного объема дополнительной работы. Построение BST-дерева сводится к сортировке элементов, поскольку при соответствующем рассмотрении BST-де-рево представляет отсортированный файл.  [49]

Лемма 13.1 Построение рандомизованного BST-дерева эквивалентно построению стандартного BST-дерева из случайно переставленных в исходном состоянии ключей. Для конструирования рандомизованного BST-дерева из N элементов используется около 2 / VlnTV сравнений ( независимо от порядка вставки элементов), а для выполнения поиска в таком дереве требуется приблизительно 2 1пЛ сравнений.  [50]

Последняя операция с АТД таблиц символов, которую мы рассмотрим - операция join. В реализации с использованием BST-дерева это сводится к объединению двух деревьев.  [51]

Если одно из BST-деревьев пустое, второе будет представлять результат. В противном случае два BST-дерева объединяются путем выбора ( произвольного) корня первого дерева в качестве результирующего корня, вставки этого корня в корень второго дерева, а затем ( рекурсивного) объединения пары левых поддеревьев и пары правых поддеревьев.  [52]

Программа 12.17 - компактная, линейная по затратам времени рекурсивная реализация операции join. Вначале мы вставляем корень первого BST-дерева во второе BST-дерево, используя метод вставки в корень. Каждый узел может быть корневым максимум при одном рекурсивном вызове, поэтому общее время определяется линейной зависимостью.  [53]



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