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

Bst-дерево

Cтраница 1


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

Нарисуйте BST-дерево, образованное в результате вставки элементов с ключами Е A S Y в первоначально пустое дерево, вставки элементов с ключами Q U Е S ТI О N в другое первоначально пустое дерево и последующего объединения результатов.  [2]

Это BST-дерево является результатом рандомизованной вставки 200 элементов в порядке возрастания их ключей в первоначально пустое дерево.  [3]

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

Нарисуйте рандомизованное BST-дерево, образующееся в результате вставки элементов с ключами EASYQUTIONe указанном порядке в первоначально пустое дерево при использовании версии программы 13.2, в которой выражение, содержащее функцию randQ, заменяется проверкой ( 111 % h - N) 3 для принятия решения о применении вставки в корень.  [5]

Нарисуйте расширенное BST-дерево, образованное в результате вставки элементов с ключами EASYQUTIONe указанном порядке в первоначально пустое дерево с использованием вставки с расширением.  [6]

Нарисуйте расширенное BST-дерево, образованное в результате вставки элементов с ключами 000000000000 1 в указанном порядке в первоначально пустое дерево.  [7]

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

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

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

В этом BST-дереве, которое было построено за счет вставки около 200 произвольных ключей в первоначально пустое дерево, ни один поиск не использует более 12 сравнений.  [11]

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

При поперечном обходе BST-дерева элементы посещаются в порядке следования их ключей. В этой реализации функция-член show элемента item используется для вывода элементов в порядке следования их ключей.  [13]

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

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



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