Теоретический материал
Декартово дерево (Treap)
А. Климовский
Скорее всего, каждый встречался с задачей, которая легко решается написанием сбалансированного дерева поиска. Хотя чаще всего на олимпиадах такие задачи имеют более простое в реализации решение, всегда не хочется его придумать. Поэтому рассмотрим задачу: реализовать бинарное дерево поиска с высотой порядка logN. Из подобных деревьев декартово имеет одну из самых простых реализаций.
И
дея следующая: для каждой вершины, кроме его ключа (key), заведем еще служебное поле приоритета (priority), значение которого будет постоянно на всем времени жизни вершины. Значение же будем присваивать случайное. Суть его в том, что в нашем дереве будем поддерживать два свойства: по ключу оно является деревом поиска, а по приоритету кучей. На мой взгляд, проще всего это понять, если нарисовать на плоскости точки с координатами (v.key, v.priority). Тогда соединив эти точки, как в дереве, мы получим на плоскости привычный рисунок коневого дерева (рис. 1).
Приступим к реализации основных процедур и функций.
Начнем с описания типа.
Type
PEl = ^TEl;
TEl = record
Key : TKey;
Y : integer;
L,R : PEl;
end;
Инициализация дерева:
//Без комментариев
procedure Init(var root : PEl);
begin
root := nil;
end;
Добавление элемента. Алгоритм следующий: найдем то поддерево, у которого он будет корнем. Процедурой Split разделим это поддерево в соответствии с ключом нового корня и сразу же подвесим все, куда необходимо. Код лучше читать снизу вверх.
//Процедура Split разбирает все дерево с корнем в pt
//в соответствии с ключом key и вешает к pR и pL
procedure
begin
if pt = nil then
begin
//разбор пустого дерева
pL := nil;
pR := nil;
end
else
//Здесь смотрится, куда отнести корень и соответственно вызывается
//опять процедура
if pt^.key < key then
begin
pL := pt;
end
else
begin
pR := pt;
end;
end;
procedure Add1(var p : PEl; var np : PEl);
//p – ссылка на корень поддерева, к которому идет добавление
//np – ссылка на новый элемент
begin
if p = nil then
//Добавление к пустому поддереву
p := np
else
if np^.y < p^.y then
//Если приоритет корня еще больше приоритета новой вершины, идем
//дальше по дереву
if np^.key = p^.key then
exit
else
if np^.key < p^.key then
Add1(p^.L, np)
else
Add1(p^.R, np)
else
begin
//Подвесим к новой вешнине все необходимое поддерево
//И привесим эту вершину вместо поддерева
p := np;
end;
end;
procedure Add(var root : PEl; const a : TKey);
// root – корень дерева, a – значение нового ключа
var
np : PEl;
begin
//Создание вершины
new(np);
np^.key := a;
np^.y := Random(maxRand);
np^.L := nil;
np^.R := nil;
//Вызов непосредственно процедуры добавления
Add1(root, np);
end;
//Функция возвращает указатель на искомый элемент или nil, если его нет
function Search(var p : PEl; const A : TKey) : PEl;
begin
if p = nil then
result := nil
else
if A = p^.key then
result := P
else
if A < p^.key then
result := Search(p^.L, A)
else
result := Search(p^.R, A)
end;
Процедура удаления находит этот элемент в дереве и удаляет его. Затем два его поддерева подвешиваются к ее родителю.
//Процедура подвешивает к p поддеревья pL и pR
procedure Merge(var p : PEl; pL, pR : PEl);
begin
//Елси одно из поддеревьев пусто, то подвешиваем другое
if pL = nil then
p := pR
else
if pR = nil then
p := pL
else
// Смотрим по приоритету
if pL^.y > pR^.y then
begin
p := pL;
Merge(p^.R, p^.R, pR);
end
else
begin
p := pR;
Merge(p^.L, pL, p^.L);
end
end;
procedure Delete(var p : PEl; const A : TKey);
begin
if p = nil then
Writeln('No such element')
else
if A = p^.key then
//Найден элемент
Merge(p, p^.L, p^.R)
//Поиск элемента
else
if A < p^.key then
Delete(p^.L, A)
else
Delete(p^.R, A)
end;
Оценим теперь сложность работы операций. Они все выполняются за O(h), где h – высота дерева. В работе [1] доказывается, что в таком дереве можно считать, что h = O(logN).
[1] Raimund Seidel «Randomized Search Trees»
[2] Кормен, Лейзерсон, Ривест. «Алгоритмы: построение и анализ» (2-е издание на русском языке)