Bst-дерево

Cтраница 3

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

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

Эти две симметричных процедуры выполняют операцию rotation ( ротация) в BST-дереве. [33]

Используя функцию разделения на части partR из программы 12.15, эта рекурсивная функция приводит BST-дерево в полностью сбалансированное состояние при затратах времени, которые определяются линейной зависимостью. Разделение на части выполняется с целью помещения среднего узла в корень, а затем это же выполняется для поддеревьев. [34]

Эта последовательность отображает результат вставки ключей A S E R С HI в nepeoHanajtbHo пустое BST-дерево при помощи метода вставки в корень. Каждый новый узел вставляется в корень с изменением связей, расположенных вдоль его пути поиска, что приводит к образованию соответствующего BST-дерева. [35]

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

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

На этих рисунках показана вставка ключей А В С D E F G HI в первоначально пустое BST-дерево методом рандомизованных вставок. Дерево на нижнем рисунке выглядит так же, как если бы оно было построено с применением стандартного алгоритма BST-дерева при вставке этих же ключей в случайном порядке. [38]

Таким образом, можно воспользоваться лучшим из обоих подходов: простой метод поиска, присущий стандартному BST-дереву, и простой метод вставки-балансировки, характерный для 2 - 3 - 4-дерева поиска. [39]

Лемма 13.3 Создание дерева через произвольную последовательность рандомизованных операций вставки, удаления и объединения эквивалентно построению стандартного BST-дерева за счет случайной перестановки ключей в дереве. [40]

Определите вероятность того, что каждое из деревьев в упражнении 13.30 образовано в результате вставки N случайных различных элементов в первоначально пустое BST-дерево. [41]

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

В этой реализации функции search и insert используют приватные рекурсивные функции searchR и insertR, которые непосредственно отражают рекурсивное определение BST-дерева. Ссылка head указывает на корень дерева. [43]

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

Эта функция принимает рандомизованное решение о том, использовать ли метод вставки в корень программы 12.13 или стандартный метод вставки программы 12.8. В рандомизованном BST-дереве каждый из узлов с равной вероятностью является корнем; поэтому, помещая новый узел в корень дерева размера Л / с вероятностью 1 / ( Л / 1), мы получаем рандомизованное дерево. [45]

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