Рандомизированные бинарные деревья поиска (R-BST)

Термины   30 Июнь 2013  Автор статьи:  

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

Вращение бинарного дерева поиска

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

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

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

Вставка

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

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

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

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

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

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

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

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


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

Научиться программировать

  • на Delphi

  • на Java

  • на C++