Рандомизированные бинарные деревья поиска (R-BST)
R-BST — это тоже бинарные деревья поиска, которые обладают дополнительными свойством, что для любого поддерева этого дерева его корнем является любой из элементов.
Вращение бинарного дерева поиска
Правое вращение — это такое локальное преобразование дерева, при котором корнем становится левый сын.
- Меняем местами левого сына и корень
- При корень становится правым сыном
- А бывший правый сын становиться становится левым сыном корня
Левое вращение — это такое локальное преобразование, при котором корнем становится правый сын.
Вставка
Тут необходимо реализовать две вставки, обычная вставка и вставка как корня, начнем с нее:
- Если корня не существует, то вернуть текущий элемент в качестве корня
- Если текущее значение корня больше переданного значения ключа, то выполнить операцию вставку в корень в левое поддерево, а затем осуществить правый поворот
- Иначе выполнить операцию вставку как корня в правое поддерево, а затем выполнить левый поворот
А обычная операция вставки выглядит следующим образом:
- Если корня не существует, то вернуть текущий элемент в качестве корня
- Если случайное число от size текущего корня равно 0, то выполнить вставку в корень
- Если текущее значение корня больше переданного значения ключа, то выполнить операцию вставки в левое поддерево
- Иначе выполнить операцию вставки в правое поддерево, а затем выполнить левый поворот
Удаление
Рассмотрим операцию merge. Данная операция сливает два поддерева:
- Если корня первого поддерева не существует вернуть корень второго поддерева
- Если корня второго поддерева не существует вернуть корень первого поддерева
- Если число из диапазона с 0 до p.size + q.size < p.size, то слить правого сына и q
- Иначе слить p и левого соседа q
Операция удаления:
- Если корень не существует, вернуть корень
- Если значение ключа корня совпадает с ключом элемента, который мы хотим удалить, то выполнить операцию merge от левого и правого сына корня
- Если значение ключа элемента меньше корня то выполнить операцию удаления в левом поддереве
- Иначе в правом
Удаление