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

Bst-деревей

Cтраница 1


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

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

Второй недостаток использования BST-деревьев - возможность того, что деревья могут стать плохо сбалансированными и в результате снижать производительность. В главе 13 исследуются еще несколько подходов к обеспечению гарантированной производительности. При наличии достаточного объема памяти под связи, эти алгоритмы делают BST-деревья весьма привлекательными в качестве основы для реализации АТД таблиц символов, поскольку обеспечивают гарантированно высокую производительность для большого набора полезных операций с АТД.  [3]

Такой способ реализации BST-деревьев как средства упрощения поиска в больших массивах элементов иногда весьма полезен, поскольку исключает дополнительные затраты на копирование элементов во внутреннее представление АТД и перегрузки, связанной с распределением и конструированием при помощи new. Использование массивов не подходит, когда объем памяти играет первостепенную роль, а таблица символов увеличивается и уменьшается в значительных пределах. В особенности это актуально, если заранее трудно предвидеть максимальный размер таблицы символов. Если невозможно точно предвидеть размер, неиспользуемые связи могут привести к напрасному расходованию памяти в области массива элементов.  [4]

5 Эмпирические исследования реализаций таблиц символов. [5]

В стандартной реализации BST-деревьев каждый новый вставленный узел попадает куда-то в нижнюю часть дерева, заменяя какой-то внешний узел. Это не является абсолютно обязательным; это всего лишь следствие естественного алгоритма с использованием рекурсивной вставки. В этом разделе рассматривается другой метод вставки, при котором каждый новый элемент вставляется в корень, и поэтому недавно вставленные узлы находятся вблизи вершины дерева.  [6]

Время выполнения алгоритмов обработки BST-деревьев зависит от форм деревьев. В лучшем случае дерево может быть полностью сбалансированным и содержать приблизительно IgTV узлов между корнем и каждым из внешних узлов, но в худшем случае в каждый из путей поиска может содержать N узлов.  [7]

Еще один потенциальный недостаток рандомизованных BST-деревьев - необходимость наличия в каждом узле поля количества узлов поддерева данного узла. Дополнительный объем памяти, требуемый для поддержки этого поля, может оказаться чрезмерной платой для больших деревьев. С другой стороны, как было показано в разделе 12.9, это поле может требоваться по ряду других причин - например, для поддержки операции select или для обеспечения проверки целостности структуры данных. В подобных случаях рандомизованные BST-деревья не требуют никаких дополнительных затрат памяти и их использование представляется весьма привлекательным.  [8]

Реализуйте версию операции remove для BST-деревьев ( программа 12.16), которая удаляет все узлы дерева, имеющие ключи, равные данному.  [9]

Создайте программу, которая строит / BST-деревьев за счет вставки N произвольных ключей в первоначально пустое дерево и вычисляет максимальную высоту дерева ( максимальное количество сравнений, необходимых для обнаружения любого промаха при вставке в любом из / деревьев) для N 103, 104, 105 и 106 при / 10, ЮО и ЮОО.  [10]

Различие между производительностью в усредненном случае для рандомизованных и стандартных BST-деревьев очень невелико, но имеет большое значение. Это допущение не справедливо во многих практических приложениях, и, следовательно, рандомизованный алгоритм примечателен тем, что позволяет избавиться от такого допущения и вместо этого исходить из законов распределения вероятностей в генераторе случайных чисел. При вставке элементов в порядке следования их ключей, в обратном порядке или любом другом порядке, BST-дерево все равно будет рандомизо-ванным.  [11]

Базовые операции search, insert и sort для BST-деревьев легко реализовать и выполнить даже при весьма незначительной случайности в последовательности операций, поэтому BST-деревья широко используются применительно к динамическим таблицам символов. Они допускают также простые рекурсивные решения для поддержки других видов операций, как было показано в этой главе на примере операций select, remove и join, и как будет показано во многих примерах далее в книге.  [12]

Несмотря на всю полезность, существует два основных недостатка использования BST-деревьев в приложениях. Во-первых, они требуют существенного дополнительного объема памяти для связей. Часто мы считаем, что ссылки и записи имеют практически одинаковые размеры ( скажем, одно машинное слово) - если это так, реализация с использованием BST-дерева использует две трети выделенного для нее объема памяти под ссылки и только одну треть под ключи. Данный эффект менее важен в приложениях с большим количеством записей и более важен в средах, в которых указатели велики.  [13]

Мы используем ту же функцию remove, которая применялась для стандартных BST-деревьев ( см. программу 12.6), но при этом функция joinLR заменяется функцией, приведенной здесь, которая принимает рандомизованное, а не произвольное решение о замещении удаленного узла предком или потомком, исходя из того, что каждый узел в результирующем дереве с равной вероятностью может быть корнем.  [14]

Несмотря на гарантию производительности, которую можно обеспечить при использовании рандомизованных и расширенных BST-деревьев, в обоих случаях не исключается вероятность того, что время выполнения отдельной операции поиска может определяться линейной зависимостью. Следовательно, эти методы не помогают ответить на основной вопрос в отношении сбалансированных деревьев: существует ли тип BST-дерева, для которого можно гарантировать логарифмическую зависимость времени выполнения каждой операции insert и search от размеров дерева. В этом и следующем разделах мы рассмотрим абстрактное обобщение BST-деревьев и абстрактное представление этих деревьев в виде типа BST-дерева, которые позволяют утвердительно ответить на этот вопрос.  [15]



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