Теоретический материал
| Сайт: | Информатикс |
| Курс: | Структуры данных |
| Книга: | Теоретический материал |
| Напечатано:: | Гость |
| Дата: | Пятница, 15 Август 2025, 11:00 |
Декартово дерево (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-е издание на русском языке)
{$O-}
{$MAXSTACKSIZE 30000000}
program dec_tree;
{$APPTYPE CONSOLE}
uses
SysUtils;
type
int=longint;
real=extended;
bool=boolean;
TKey=int;
PEl=^TEl;
TEl=record
key:TKey;
y:int;
L,R:PEl;
end;
TDecTree=object
root:PEl;
procedure Init;
procedure Add(const a:TKey);
function Search(const a:TKey):PEl;
procedure Delete(const a:TKey);
procedure Print;
end;
const
maxRand=1000000000;
mx=100000;
var
tr:TDecTree;
a:array[0..mx] of Bool;
i,t:int;
procedure TDecTree.Init;
begin
root:=nil;
end;
procedure Split(pt: PEl; key: TKey; var pL,pR:PEl);
begin
if pt=nil then
begin
pL:=nil;
pR:=nil;
end
else
if pt^.keypR^.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 Delete1(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 Anil then
begin
Print1(P^.L);
Write(p^.key,' ');
Print1(P^.R);
end;
end;
procedure TDecTree.Print;
begin
Print1(root);
end;
procedure TDecTree.Delete(const a:TKey);
begin
Delete1(root,a);
end;
begin
Randomize;
RandSeed:=Random(1000);
// RandSeed:=722;
Writeln(RandSeed);
tr.Init;
fillchar(a,sizeof(a),0);
for i := 1 to 3*mx do
begin
t:=mx-i mod mx;
// t:=random(mx);
if a[t]<>(tr.Search(t)<>nil) then
Writeln(IntToStr(i) + ' 1'+'BAD!!!');
if a[t] then
tr.Delete(t)
else
tr.Add(t);
a[t]:=not a[t];
if a[t]<>(tr.Search(t)<>nil) then
Writeln(IntToStr(i) + ' 2'+'BAD!!!');
Writeln(i,' ok ', ord(a[t]));
// Write ('Added ', t, ' Now: ');
// tr.Print;
// readln;
// writeln;
end;
Readln;
end.