Декартово дерево (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 Split(pt : PEl; key : TKey; var pL, pR : PEl);

begin

if pt = nil then

   begin

   //разбор пустого дерева

   pL := nil;

   pR := nil;

   end

else

   //Здесь смотрится, куда отнести корень и соответственно   вызывается

   //опять процедура Split

   if pt^.key < key then

      begin

      pL := pt;

      Split(pL^.R, key, pL^.R, pR);

      end

   else

      begin

      pR := pt;

      Split(pR^.L, key, pL, pR^.L);

      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

      //Подвесим к новой вешнине все необходимое поддерево

      Split(p, np^.key, np^.L, np^.R);

      //И привесим эту вершину вместо поддерева

      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-е издание на русском языке)