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]