R-BST — это тоже бинарные деревья поиска, которые обладают дополнительными свойством, что для любого поддерева этого дерева его корнем является любой из элементов.

Правое вращение — это такое локальное преобразование дерева, при котором корнем становится левый сын.

• Меняем местами левого сына и корень
• При корень становится правым сыном
• А бывший правый сын становиться становится левым сыном корня

Левое вращение — это такое локальное преобразование, при котором корнем становится правый сын.

Тут необходимо реализовать две вставки, обычная вставка и вставка как корня, начнем с нее:

• Если корня не существует, то вернуть текущий элемент в качестве корня
• Если текущее значение корня больше переданного значения ключа, то выполнить операцию вставку в корень в левое поддерево, а затем осуществить правый поворот
• Иначе выполнить операцию вставку как корня в правое поддерево, а затем выполнить левый поворот

А обычная операция вставки выглядит следующим образом:

• Если корня не существует, то вернуть текущий элемент в качестве корня
• Если случайное число от size текущего корня равно 0, то выполнить вставку в корень
• Если текущее значение корня больше переданного значения ключа, то выполнить операцию вставки в левое поддерево
• Иначе выполнить операцию вставки в правое поддерево, а затем выполнить левый поворот

Рассмотрим операцию merge. Данная операция сливает два поддерева:

• Если корня первого поддерева не существует вернуть корень второго поддерева
• Если корня второго поддерева не существует вернуть корень первого поддерева
• Если число из диапазона с 0 до p.size + q.size < p.size, то слить правого сына и q
• Иначе слить p и левого соседа q

Операция удаления:

• Если корень не существует, вернуть корень
• Если значение ключа корня совпадает с ключом элемента, который мы хотим удалить, то выполнить операцию merge от левого и правого сына корня
• Если значение ключа элемента меньше корня то выполнить операцию удаления в левом поддереве
• Иначе в правом

Реализация R-BST на Java
hydraruzxpnew4af