Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

АВЛ-дерево



АВИ-дерево получило своё название по фамилиям его раз- работчиков — советских математиков Георгия Максимовича Адельсон-Вельского (родился 8 января 1922 г. в Самаре) и Евге- ния Михайловича Ландиса, которые предложили использовать такое дерево в 1962 году.
АВЛ-дерево полностью удовлетворяет менее строгому on- ределению сбалансированности дерева. Сбалансированность дос- тигается за счёт упомянутых выше операций поворотов (или вращений), а для сравнения высот ветвей в каждом узле двоично- го дерева поиска используется дополнительное поле признак сбалансированности ветвей (или разность их высот).

2. 
   Красно-чёрное дерево
   

Красно-чёрное дерево (RB-tree) отличается от АВЛ-дерева смыслом признака сбалансированности: вместо разности высот ветвей используется абстрактный «цвет» (красный или чёрный) и дерево строится по следующим правилам:

1. 
   Все указатели на терминальные узлы считаются пeпyc-
   

ты ми (т.е. в дереве имеются фuкmusныe терминальные узлы).

2. 
   Все такие терминальные узлы считаются « чёрны мп».
   
3. 
   Все узлы, соседние с «красными» узлами, считаются
   

136
« чёрны ми» (т.е. запрещена ситуация с двумя «красными» узлами

4. 
   В левой и правой ветвях дерева, ведущих от его корня к листьям, число « чёрпы.v» узлов одинаково. Это число называется
   

«чёрной высотой» дерева.
Красно-чёрное дерево, соответствующее перечисленным правилам, показано на рисунке 10.12.

22 27

Рис. 10.12 — Пример красно-чёрного дерева с фиктивными чёр- ными терминальными узлами

Теоретически считается, что красно-чёрное дерево требует меньшего объёма памяти для хранения отдельного узла, чем АВЛ-дерево, т.к. для представления цвета достаточно всего одно- го бита. Но на практике это преимущество реализовать без потерь на дополнительные операции доступа к отдельным битам весьма сложно. Даже один из вариантов реализации красно-чёрного де- рева — когда «красные» узлы обозначаются нечётными ключами, а «чёрные» узлы — чётными (или наоборот), не всегда пригоден на практике, т.к. решаемая задача может не допускать такого раз- деления узлов.

Используемые при балансировке операции вращения фак- тически представляют собой переприсвоения значений указате- лей в узлах дерева и, как следствие, перепроведение связей меж- ду узлами, после которого высоты левой и правой ветвей оказы- ваются одинаковыми (или отличаются не более чем на один уро- вень) и дерево считается сбалансированным. Суть операции вра- щения иллюстрируется следующим рисунком:

137

Рис. 10.13 — Операция вращения (поворота)

Здесь сплошными линиями показано исходное несбаланси- рованное дерево (ветви показаны большими треугольниками, внутри этих ветвей узлы могут быть уже сбалансированы). Мож- но считать, что дерево «подвешено» за свой текущий корень на крюк, показанный сплошной линией. Поворот состоит в «подвес- ке» дерева за другой узел (который станет новым корнем) на крюк, показанный пунктирной линией, и коррекции связей: к ле- вой ветви нового корня проводится новая связь (показана пунк- тирной линией) от старого корня (эта ветвь будет новой правой веткой старого корня), связь от нового корня к его старой левой ветви рвётся (штриховая линия), и связь между старым и новым корнями меняет направление (фактически существующая связь в одном направлении уже порвана, а в обратном направлении проводится заново). В итоге дерево «поворачивается» вокруг но- вой точки подвески, откуда эта операция и получила своё назва- ние. После вращения в рассматриваемом случае высоты левой и правой ветвей нового корня будут одинаковыми.

Для выполнения операции вращения может потребоваться информация о текущем узле и связанных с ним узлах (его «роди- теле» и его «сыне»), т.е. адреса этих узлов в памяти. Или инфор- мация о текущем узле, его «отце» и «деде», или информация о текущем узле, его «сыне» и «внуке» (в зависимости от того, рас- сматривается дерево как ненаправленная структура данных, или как направленная).

Операция вращения может применяться не только для ба- лансировки АВЛ- или красно-чёрных деревьев, но и обычных двоичных деревьев, не обязательно деревьев поиска. Например, один из вариантов принудительной балансировки обычного дере- ва заключается в преобразовании исходного дерева в лево- ассоциативное (т.е. в левую «лозу») с помощью последователь- ных операций вращения (см. рисунки ).

а

а

Рис. 10.14 — l -й этап. Преобразование дерева в «лозу»

Затем «лоза» преобразуется в сбалансированное дерево при помощи той же операции.

^а
Рис. 10.15 — Однократный правый поворот
139

P c. 10.16 — 2- 3TI1H. Hauauo npeo6pasOBI1HHII « uO3si11 B Qé]3éBO

6

P c. 10.17 — 3I1Bé]3IIIéHne npeo6]3II3OBiIHHII « no3sI» B ae]3éBO.

PeKypcHBHas QyHKuHs nOCT]3OéHHII H@éIIJIhHO c6aniIHCH]3OB£tH- HOFO @é]3éB£t C saQ£tHHhIM UHCnoM ysnoB His II3hIKé HiICKOJIh .

function maketree(n node:integer) :ptr; var

newnode: ptr;
newkey, nl, nr: integer; begin
if n node = 0 then newnode := nil
else begin
nl := n node div 2;

nr := n node - nl read(newkey); new(newnode);
with newnode’ do begin
KJIIOUII H QI1HHI>IX

140

key := newkey;
left := maketree(nl); right := maketree(nr)
end; end;
maketree newnode end;

read(n); (* Ввод числа узлов *) tree := maketree(n); (* Первый вызов *)

3.