Деревья поиска (Алгоритм4 Заметки к учебнику)

(1) Двоичные деревья поиска: среднее lgN, наихудшее N для вставки и поиска.

Свойства: ключ в любом узле больше, чем ключи во всех узлах левого поддерева этого узла и меньше, чем ключи во всех узлах правого поддерева этого узла. Растет сверху вниз.

По сравнению с бинарным поиском:

1. Поиск BST составляет 1.39lgN (из-за пропусков поиска, аналогично быстрой сортировке), бинарный поиск - lgN.
2. BST подходит для вставки (бинарный поиск - O(n + logn)).

Общие операции:

1. Минимум: если(левая ссылка != null), наименьший ключ = наименьший ключ в поддереве, укорененном в узле, на который ссылается левая ссылка. иначе наименьший ключ = корень.
2. Floor: если данный ключ ≤ root, он должен находиться в левом поддереве. Если данный ключ > root, он может находиться в правом поддереве, если существует ключ ≤ данного ключа.
3. Выбор: ищем ключ ранга k. Если leftSubtree.size() > k, то он находится в левом поддереве; в противном случае проверяем наличие ключа ранга k - leftSubtree.size()-1 в правом поддереве. 1 - для корня.
4. Ранг: если задан ключ < root, просматриваем левое поддерево; если задан ключ == root, rank = leftSubtree.size(); else rank > leftSubtree.size() + 1
5. Удалить: удалить узел x, заменив его преемником или предшественником случайным образом. Преемник = min(rightSubtree), предшественник = max(leftSubtree) (в пункте 1).
6. Диапазон запросов: leftSubtree - root - rightSubtree (по порядку).

(2) Сбалансированные деревья поиска

(a) 2-3 дерева поиска: гарантируется не более lgN посещений узлов для поиска и вставки.

Узел либо пуст, либо имеет 2 дочерних узла (1 ключ), либо 3 дочерних узла (2 ключа). Растет снизу вверх (см. точку вставки 4).

Идеально сбалансированное дерево поиска 2-3 def: все нулевые ссылки находятся на одинаковом расстоянии от корня.

Вставка (локальное преобразование, не затрагивающее другие узлы, и сохраняющее идеально сбалансированное глобальное свойство):

1. Вставка в 2-узел: заменить узел на 3-узел. Если узел, на котором заканчивается поиск, является 3-узлом, то работы больше.
2. Вставка в дерево с одним 3-узлом: временно поместите новый ключ в 4-узел и преобразуйте его в три 2-узла - средний ключ в корне, а в качестве дочерних - наименьший и наибольший из трех ключей.
3. Вставка в 3-узел, родителем которого является 2-узел: временно создайте 4-узел и переместите средний ключ в родительский узел.
4. Вставка в 3-узел, чей родитель является 3-узлом: временно создайте 4-узел и переместите средний ключ в родительский узел (рекурсивный). при достижении корня 3-узла, разделите как пункт 2 и увеличьте высоту дерева на 1.

(b) Красно-черный BST

Обратите внимание, что это внутренняя структура данных, используемая Java TreeMap (PriorityQueue - это куча).

Основная идея: кодировать 2-3 дерева, начиная со стандартных BST. Красные ссылки: связывают 2-узлы в 3-узлы; черные ссылки: связывают дерево.

Свойства: высота ≤ 2lgN, средняя длина пути lgN. Все операции, упомянутые выше для BST, занимают lgN времени в худшем случае (floor, deleteMax, rangeCount...).

Допущения:

1. Красные ссылки наклоняются влево.
2. Ни один узел не имеет двух красных звеньев, соединенных с ним.
3. Идеальный черный баланс: каждый путь от корня до нулевого звена имеет одинаковое количество черных звеньев.
4. Соответствие 1-1 между красно-черным деревом и 2-3 деревьями.

Операции: поворот влево: переключение с меньшего из двух ключей в корне на больший из двух ключей в корне (два ключа связаны красной ссылкой).

Вставка:

1. Вставка в один 2-узел: если новый ключ > существующий, вставьте новый ключ, затем поверните влево (красная ссылка всегда должна быть наклонена влево). В противном случае просто вставьте.
2. Вставьте в 2-узел внизу: родитель просто становится 3-узлом и повторите пункт 1.
3. Вставка в 3-узел, чей родитель является 3-узлом (P436)

• 1-й: Новый ключ > родителей, прикрепляем на крайнее правое звено, затем переворачиваем цвета (2-3 дерево вставки точка 3).
• 2-й: Новый ключ < родители, два красных звена, наклоненных влево (допустим, слева направо - a-b-c): поверните верхнее звено вправо (сделайте b корнем и измените цвет a-b и b-c на черный, а родителя b на красный, чтобы передать красное звено вверх по дереву).
• 3-й: Новый ключ проходит между родителями, левосторонняя красная ветвь с правосторонней красной ветвью внизу. Сделайте поворот влево к правой ветви, и она превратится во 2-й случай выше.
• При необходимости рекурсивно проведите красные ссылки вверх по дереву.

Вставки точно такие же, как и в дереве 2-3.

Удаление (P441) пропущено.