Задача поиска данных в большом массиве (или файле) возникает очень часто (во всех
приложениях, работающих с базами данных, но не только в них). Если массив упорядочен,
можно использовать метод деления отрезка пополам. Для этого нужно приблизительно Log(N)
сравнений - совсем немного. Но если тебуется вставлять новые данные и удалять имеющиеся,
затраты на поддержание порядка могут быть непомерны - в худшем случае для вставки и для
удаления потребуется N операций. Если не поддерживать порядок данных - непомерны будут
затраты на поиск. Кроме того, для разных целей может быть нужен разный порядок данных,
а физический порядок всего один. Решение состоит в поддержке индексов - дополнительных
упорядоченных структур данных, содержащих ключи и ссылки на основные данные. Порядок
самих данных при этом не играет никакой роли. Индексный поиск может быть столь же
эффективен, как и поиск методом деления деления в упорядоченном массиве, плюс к этому
вставки и удаления также могут выполняться быстро. Существует несколько способов
построения индексов. Во-первых, это так называемые B-деревья. В определенном смысле
B-дерево - обобщение двоичного дерева - простой конструкции, не обладающей, однако,
гарантированной эффективностью. Но B-дерево - не единственнная эффективная конструкция
индекса. Можно упомянуть красно-черные деревья - еще одно усовершенствование двоичных
деревьев (в настоящее время у меня нет соответствующего примера).
Упоминание о красно-черных деревьях по-видимому было следствием покупки книги
Т.Кормена, Ч.Лейзерсона и Р.Ривеста "Алгоритмы: построение и анализ", но разобраться
в их устройстве быстро не удалость и дело это было заброшено. В-деревья казались
значительно более важными (наверное, это так и есть) и понимание их устрйства
я посчитал для себя достаточным. Значительно позже я вернулся к этому делу
и написал еще один пример, демонстрирущий АВЛ-дерево.
А описание красно-черных деревьях в упомянутой книге представляется методически неверным.
По какой-то непонятной причине не сказано, что красно-черное дерево есть 2-3-4-дерево
(т.е. B-дерево, в страницах которого могут находиться до трех ключей и четырех ссылок
на нижележащие страницы), представленное в виде двоичного дерева. И рассматриваются
красно-черные деревья до B-деревьев. Ясно это стало после ознакомления с учебным курсом
Алгоритмы на C++
Р.Седжвика. Красный цвет указывет на то, что узел является дополнительным и принадлежит
тому же уровню, что и основной узел черного цвета. Можно построить аналогичную несимметрчную конструкцию,
в которой дополнительные узлы могут быть только с одной стороны от черных (например,
слева) - это эквивалент 2-3-дерева. Возможно, она не хуже.
Из соображений простоты начать лучше именно с двоичных деревьев. Всюду ниже (также для
простоты) предполагается, что индексируемые данные находятся в оперативной памяти и в
индексе содержатся только ссылки на эти данные.
Двоичное дерево - структура данных, состоящая из узлов, каждый из которых
содержит ключ и две ссылки на поддеревья - левое и правое. Все ключи в левом
поддереве меньше ключа в узле, все ключи в правом поддереве - больше. Требование
точного неравенства ключей естественно, т.к. даже ести реальные ключи могут повторяться,
уникальность достигается расширением ключа номером (смещением, адресом) элемента данных.
Процедуры вставки и удаления ключей достаточно просты:
define nNODE 8192
struct TNode
int pData;
int pLeft;
int pRight;
section
int pFree;
end
TNode Node[nNODE];
int pRoot;
int pFree;
void Stop(char @S);
void Init()
pRoot=-1;
pFree=-1;
int P= 0;
while P<nNODE do
Node[P].pFree=pFree; pFree=P;
inc P;
end
end
int Comp(int P1, P2) // функция сравнения ключей
select
case P1<P2:
return -1;
case P1>P2:
return 1;
end
return 0;
end
void Insert(int pData)
int @P=@pRoot;
while P>=0 do
int C=Comp(Node[P].pData,pData);
select
case C>0:
@P=@Node[P].pLeft;
case C<0:
@P=@Node[P].pRight;
default:
return // Повтор ключа
end
end
if pFree<0 then
Stop("Недостаточно свободных узлов");
end
P =pFree;
pFree = Node[pFree].pFree;
Node[P].pData =pData;
Node[P].pLeft =-1;
Node[P].pRight=-1;
end
void Delete(int pData)
int @P=@pRoot;
while TRUE do
if P<0 then
return // Ключ не найден
end
int C=Comp(Node[P].pData,pData);
select
case C>0:
@P=@Node[P].pLeft;
case C<0:
@P=@Node[P].pRight;
default:
exit
end
end
int P2=P;
if Node[P2].pLeft<0 then
P=Node[P2].pRight;
Node [P2].pFree=pFree;
pFree= P2;
return
end
if Node[P2].pRight<0 then
P=Node[P2].pLeft;
Node [P2].pFree=pFree;
pFree=P2;
return
end
int @P1=@Node[P2].pLeft;
while Node[P1].pRight>=0 do
@P1=@Node[P1].pRight;
end
Node[P].pData=Node[P1].pData;
int P0=P1;
P1=Node[P1].pLeft;
Node [P0].pFree=pFree;
pFree = P0;
end
Изменение ключа реализуется посредством удаления старого и вставки нового.
Двоичное дерево имеет существенный недостаток - в худшем случае (например,
при вставке упорядоченнной последовательности ключей) оно вырождается в
список. Этот недостаток может быть устранен, ести предусмотреть в узле место
для двух ключей и трех ссылок (в общем случае N ключей и (N+1) ссылки) и усложнить
функции вставки/удаления. Новый ключ всегда добавляется в нижнюю страницу, если
страница переполняется, она делится на две и средний ключ переносится на вышележащую
страницу. Если и эта страница переполняется, она тоже делится на две. В худшем
случае корневая страница будет поделена на две и будет создан новый корень,
содержащий единственный ключ. Высота дерева при этом увеличится на единицу. При
удалении наоборот, если страница становится заполненной менее чем наполовину, она
либо дополняется ключом из соседней страницы, либо две страницы объединяются (при
этом один ключ берется из вышележащей страницы).
Пример был написан когда еще использовалась MS-DOS, для экономии памяти ссылки
на страницы были отделены от самих страниц (все нижние страницы, а их больше всего,
содержат лишь пустые ссылки). По какой-то неизвестной причине процедуры нерекурсивны,
ниже приведена рекурсивная реализация:
define nDATA 8 // >=2
define nDATA1 9 // nDATA+1
define nPAGE 2048
define nLINK 512
define nPATH 32
struct TPage
int pData[nDATA];
int pLink;
int nData;
section
int pPage;
end
struct TLink
int pPage[nDATA1];
section
int pLink;
end
struct TPath
int pPage;
int pData;
end
TPage Page[nPAGE];
TLink Link[nLINK];
int pPage; // Указатель на список свободных стpаниц данных
int pLink; // Указатель на список свободных стpаниц ссылок
int pRoot; // Указатель на коpневую стpаницу деpева
void Stop(char @S);
void Init()
pPage=-1;
int P= 0;
while P<nPAGE do
Page[P].pPage=pPage; pPage=P;
inc P;
end
pLink=-1;
int L= 0;
while L<nLINK do
Link[L].pLink=pLink; pLink=L;
inc L;
end
pRoot=-1;
end
int Comp(int P1, P2) // функция сравнения ключей
select
case P1<P2:
return -1;
case P1>P2:
return 1;
end
return 0;
end
void Insert(int pData)
TPath Path[nPATH];
int N;
int P;
P=pRoot;
N=0;
while P>=0 do
if N>=nPATH then
Stop("Высота деpева слишком велика");
end
int I=0;
int J=Page[P].nData;
while I<J do
int K=(I+J)/2;
int S=Comp(Page[P].pData[K],pData);
select
case S>0:
J=K;
case S<0:
I=K+1;
default:
return // Повтоp ключа
end
end
Path[N].pPage=P;
Path[N].pData=I;
inc N;
int L=Page[P].pLink;
if L<0 then
exit
end
P=Link[L].pPage[I];
end
int P0=-1;
int P1=-1;
while TRUE do
dec N;
if N<0 then
if pPage<0 then
Stop("Недостаточно стpаниц данных");
end
pRoot=pPage;
pPage=Page[pPage].pPage;
Page[pRoot].pData[0]= pData;
Page[pRoot].pLink =-1;
Page[pRoot].nData = 1;
if P0<0 then
exit
end
if pLink<0 then
Stop("Недостаточно стpаниц ссылок");
end
int L=pLink;
pLink=Link[pLink].pLink;
Link[L].pPage[0]=P0;
Link[L].pPage[1]=P1;
Page[pRoot].pLink=L;
exit
end
P=Path[N].pPage;
if Page[P].nData<nDATA then
int I=Page[P].nData;
while I>Path[N].pData do
Page[P].pData[I]=Page[P].pData[I-1];
dec I;
end
Page[P].pData[I]=pData;
inc Page[P].nData;
if P0<0 then
exit
end
int L=Page[P].pLink;
int J=Page[P].nData; // Новое значение
while J>Path[N].pData do
Link[L].pPage[J]=Link[L].pPage[J-1];
dec J;
end
Link[L].pPage[J] =P0;
Link[L].pPage[J+1]=P1;
exit
end
if pPage<0 then
Stop("Недостаточно стpаниц данных");
end
int P2=pPage;
pPage =Page[pPage].pPage;
int L, L2=-1;
if P0>=0 then
if pLink<0 then
Stop("Недостаточно стpаниц ссылок");
end
L =Page[P].pLink;
L2 =pLink;
pLink=Link[pLink].pLink;
end
Page[P2].pLink=L2;
int M=nDATA/2;
if Path[N].pData<=M then
int I=M;
int J=0;
while I<nDATA do
Page[P2].pData[J]=Page[P].pData[I];
inc J;
inc I;
end
Page[P2].nData=J;
I=M;
while I>Path[N].pData do
Page[P].pData[I]=Page[P].pData[I-1];
dec I;
end
Page[P].pData[I]=pData;
if L2>=0 then
I=M+1;
J=1;
while I<=nDATA do
Link[L2].pPage[J]=Link[L].pPage[I];
inc J;
inc I;
end
I=M+1;
while I>Path[N].pData do
Link[L].pPage[I]=Link[L].pPage[I-1];
dec I;
end
Link[L].pPage[I] =P0;
Link[L].pPage[I+1]=P1;
Link[L2].pPage[0]=Link[L].pPage[M+1];
end
else
int I=M+1;
int J=0;
while I<Path[N].pData do
Page[P2].pData[J]=Page[P].pData[I];
inc J;
inc I;
end
Page[P2].pData[J]=pData;
inc J;
while I<nDATA do
Page[P2].pData[J]=Page[P].pData[I];
inc J;
inc I;
end
Page[P2].nData=J;
if L2>=0 then
I=M+1;
J=0;
while I<Path[N].pData do
Link[L2].pPage[J]=Link[L].pPage[I];
inc J;
inc I;
end
Link[L2].pPage[J]=P0;
inc J;
Link[L2].pPage[J]=P1;
inc J;
inc I;
while I<=nDATA do
Link[L2].pPage[J]=Link[L].pPage[I];
inc J;
inc I;
end
end
end
Page[P].nData=M;
pData=Page[P].pData[M];
P0 =P;
P1 =P2;
end
end
void Delete(int pData)
TPath Path[nPATH];
int N;
int P;
P=pRoot;
N=0;
while TRUE do
if N>=nPATH then
Stop("Высота деpева слишком велика");
end
int S=1;
int I=0;
int J=Page[P].nData;
while I<J do
int K=(I+J)/2;
S=Comp(Page[P].pData[K],pData);
select
case S>0:
J=K;
case S<0:
I=K+1;
default:
I=K;
exit
end
end
Path[N].pPage=P;
Path[N].pData=I;
inc N;
if S=0 then
if Page[P].pLink>=0 then
int P1=Link[Page[P].pLink].pPage[I];
while TRUE do
if N>=nPATH then
Stop("Высота деpева слишком велика");
end
Path[N].pPage=P1;
Path[N].pData=Page[P1].nData;
inc N;
if Page[P1].pLink<0 then
exit
end
P1=Link[Page[P1].pLink].pPage[Page[P1].nData];
end
dec Page[P1].nData;
Page[P].pData[I]=Page[P1].pData[Page[P1].nData];
else
while I+1<Page[P].nData do
Page[P].pData[I]=Page[P].pData[I+1];
inc I;
end
dec Page[P].nData;
end
exit
end
if Page[P].pLink<0 then
return // Ключ не найден
end
P=Link[Page[P].pLink].pPage[I];
end
while N>1 do
dec N;
if Page[Path[N].pPage].nData>=nDATA/2 then
return
end
int P0;
int P1;
int M;
int S;
P=Path[N-1].pPage;
M=Path[N-1].pData;
S=M;
if M<Page[P].nData then
P0=Path[N].pPage;
P1=Link[Page[P].pLink].pPage[M+1];
else
P0=Link[Page[P].pLink].pPage[M-1];
P1=Path[N].pPage;
dec M;
end
int L0=Page[P0].pLink;
int L1=Page[P1].pLink;
if Page[P0].nData+Page[P1].nData+1>nDATA then
if S=M then // Стpаница P0 недостаточно заполнена
Page[P0].pData[Page[P0].nData]=Page[P] .pData[M];
Page[P] .pData[M] =Page[P1].pData[0];
int I=0;
while I+1<Page[P1].nData do
Page[P1].pData[I]=Page[P1].pData[I+1];
inc I;
end
if L0>=0 then
Link[L0].pPage[Page[P0].nData+1]=Link[L1].pPage[0];
I=0;
while I+1<=Page[P1].nData do
Link[L1].pPage[I]=Link[L1].pPage[I+1];
inc I;
end
end
inc Page[P0].nData;
dec Page[P1].nData;
else // Стpаница P1 недостаточно заполнена
int I=Page[P1].nData;
while I>0 do
Page[P1].pData[I]=Page[P1].pData[I-1];
dec I;
end
Page[P1].pData[0]=Page[P] .pData[M];
Page[P] .pData[M]=Page[P0].pData[Page[P0].nData-1];
if L0>=0 then
I=Page[P1].nData+1;
while I>0 do
Link[L1].pPage[I]=Link[L1].pPage[I-1];
dec I;
end
Link[L1].pPage[0]=Link[L0].pPage[Page[P0].nData];
end
dec Page[P0].nData;
inc Page[P1].nData;
end
return
end
// слияние стpаниц
int I=Page[P0].nData;
int K=I;
Page[P0].pData[I]=Page[P].pData[M];
inc I;
int J=0;
while J<Page[P1].nData do
Page[P0].pData[I]=Page[P1].pData[J];
inc I;
inc J;
end
Page[P0].nData=I;
if L0>=0 then
I=K+1;
J=0;
while J<=Page[P1].nData do
Link[L0].pPage[I]=Link[L1].pPage[J];
inc I;
inc J;
end
Link[L1].pLink=pLink;
pLink =L1;
end
Page[P1].pPage=pPage;
pPage =P1;
I=M;
while I+1<Page[P].nData do
Page[P].pData[I]=Page[P].pData[I+1];
inc I;
end
int L=Page[P].pLink;
I=M+1;
while I+1<=Page[P].nData do
Link[L].pPage[I]=Link[L].pPage[I+1];
inc I;
end
dec Page[P].nData;
end
if Page[pRoot].nData>0 then
return
end
int L=Page[pRoot].pLink;
if L>=0 then
Page[pRoot].pPage=pPage; pPage=pRoot;
pRoot=Link[L].pPage[0];
Link[L].pLink=pLink;
pLink =L;
return
end
Page[pRoot].pPage=pPage;
pPage =pRoot;
pRoot =-1;
end
Эти процедуры гарантируют, что все страницы дерева (кроме корневой) будут
заполнены не менее чем на половину. В силу этого высота дерева (и затраты
времени на вставку, удаление и поиск) никогда не будут большими. Сам поиск
значительно проще вставки и удаления. Поиск единственного ключа очень прост,
с него начинается функция Delete и повторять этот фрагмент еще раз нет смысла,
поиск ключей из заданного диапазона немного сложнее, но все равно он значительно
проще вставки/удаления:
void search(int P; int Max)
int I=0;
while I<Page[P].nData do
if Page[P].pLink>=0 then
search(Link[Page[P].pLink].pPage[I],Max);
end
if Comp(Page[P].pData[I],Max)>0 then
return
end
puts(@Str(Page[P].pData[I]));
putc(#13);
putc(#10);
inc I;
end
if Page[P].pLink>=0 then
search(Link[Page[P].pLink].pPage[I],Max);
end
end
void Select(int P; int Min, Max)
if P<0 then
return
end
int I=0;
int J=Page[P].nData;
while I<J do
int K=(I+J)/2;
if Comp(Page[P].pData[K],Min)>=0 then
J=K;
else
I=K+1;
end
end
if Page[P].pLink>=0 then
Select(Link[Page[P].pLink].pPage[I],Min,Max);
end
while I<Page[P].nData do
if Comp(Page[P].pData[I],Max)>0 then
return
end
puts(@Str(Page[P].pData[I]));
putc(#13);
putc(#10);
if Page[P].pLink>=0 then
search(Link[Page[P].pLink].pPage[I+1],Max);
end
inc I;
end
end
Функция Select печатает все ключи, находящиеся в диапазоне от Min до Max.
B-дерево легко адаптируеся для случая, когда данные размещаются на дисках.
Для этого нужно хранить ключи, ссылки на данные и ссылки на страницы индекса
вместе (в приведенном примере ключи доступны по ссылкам на данные, а ссылки на
страницы хранятся отдельно от ссылок на данные для экономии памяти - большинство
страниц не содержат ссылок на другие страницы). Размер страницы должен выбираться
не слишком малым.
Эффективность B-деревьев возрастает с увеличением размера массива данных.
Из-за этого пример B-дерева в памяти размером 64K не очень показателен.
Например, если использовать его для поиска в таблице меток ассемблера asm8086,
выигрыш по ставнению с простым перебором при компиляции context.asm (около двух
тысяч меток) будет примерно пятикратным. Это несколько хуже, чем поиск методом
половинного деления, но зато B-дерево [почти] не зависит от порядка меток.
Рекурсивная реализация (компилятор - Context3, ревизия не ниже 82):
define NO_MEMORY -3;
define DUP -1;
define NOT_FOUND -2;
define OK 0;
define MOVE_UP 1;
define BALANCE 1;
define nDATA 2;
struct PAGE
int nData;
int data [nDATA];
PAGE link [nDATA + 1]^;
end
define nPAGE 0x100000;
PAGE pages[nPAGE];
PAGE free^ := NULL;
void initPages() is
int i := nPAGE;
while i > 0 do
dec i;
pages[i].link[0]^ := free^;
free^ := pages[i]^;
end
end
int comp(int p1, int p2) is
select
case p1 < p2:
return -1;
case p1 > p2:
return 1;
end
return 0;
end
PAGE createPage()^ is
PAGE temp^ := free^;
if temp^ != NULL then
free^ := free.link[0]^;
int i := 0;
while i < nDATA do
temp.data[i] := 0;
temp.link[i]^ := NULL;
inc i;
end
temp.link[i]^ := NULL;
return temp^;
end
return NULL;
end
void deletePage(PAGE page^) is
page.link[0]^ := free^;
free^ := page^;
end
PAGE root^ := NULL;
int split(PAGE page^^, int i) is
int result := MOVE_UP;
PAGE p1^ := page.link[i]^;
if page.nData < nDATA then
int k := page.nData;
while k > i do
page.data[k] := page.data[k - 1];
dec k;
end
int m := page.nData + 1;
while m > i + 1 do
page.link[m]^ := page.link[m - 1]^;
dec m;
end
inc page.nData;
page.data [i] := p1 .data[0];
page.link [i]^ := p1 .link[0]^;
page.link [i + 1]^ := p1 .link[1]^;
deletePage(p1^);
result := OK;
else
PAGE p2^ := createPage()^;
if p2^ = NULL then
return NO_MEMORY;
end
select
case i < nDATA / 2:
int k := nDATA / 2;
int m := 0;
while k < nDATA do
p2.data[m] := page.data[k];
p2.link[m]^ := page.link[k]^;
inc m;
inc k;
end
p2 .link[m]^ := page.link[k]^;
p2 .nData := m;
int n := nDATA / 2;
while n > i do
page.data[n] := page.data[n - 1];
page.link[n]^ := page.link[n - 1]^;
dec n;
end
page.data[i] := p1.data[0];
page.link[i]^ := p1.link[0]^;
page.link[i + 1]^ := p1.link[1]^;
page.nData := nDATA / 2;
p1.data[0] := page.data[nDATA / 2];
case i = nDATA / 2:
int k := nDATA / 2;
int m := 0;
while k < nDATA do
p2.data[m] := page.data[k];
p2.link[m]^ := page.link[k]^;
inc m;
inc k;
end
p2 .link[m]^ := page.link[k]^;
p2 .nData := m;
page.link[i]^ := p1.link[0]^;
//INFO Overwrite
p2 .link[0]^ := p1.link[1]^;
page.nData := nDATA / 2;
default:
int k := nDATA / 2 + 1;
int m := 0;
while k < i do
p2.data[m] := page.data[k];
p2.link[m]^ := page.link[k]^;
inc m;
inc k;
end
p2.data[m] := p1 .data[0];
p2.link[m]^ := p1 .link[0]^;
inc m;
int n := m;
while k < page.nData do
p2.data[m] := page.data[k];
p2.link[m]^ := page.link[k]^;
inc m;
inc k;
end
p2 .link[m]^ := page.link[k]^;
//INFO Overwrite
p2.link[n]^ := p1 .link[1]^;
p2.nData := m;
page.nData := nDATA / 2;
p1.data[0] := page.data[nDATA / 2];
end
p1.link[0]^ := page^;
p1.link[1]^ := p2^;
p1.nData := 1;
page^ := p1^;
end
return result;
end
int insert(PAGE page^^, int data) is
if page^ = NULL then
page^ := createPage()^;
if page^ = NULL then
return NO_MEMORY;
end
page.nData := 1;
page.data[0] := data;
page.link[0]^ := NULL;
page.link[1]^ := NULL;
return MOVE_UP;
else
int i := 0;
int j := page.nData;
while i < j do
int m := (i + j) /2;
int c := comp(data, page.data[m]);
select
case c = 0:
return DUP;
case c < 0:
j := m;
default:
i := m + 1;
end
end
int result := insert(page.link[i]^^, data);
if result > OK then
result := split(page^^, i);
end
return result;
end
end
int balance(PAGE page^, int i) is
select
case i = page.nData:
PAGE p1^ := page.link[i - 1]^;
PAGE p2^ := page.link[i]^;
if p1.nData + p2.nData + 1 <= nDATA then
int j := p1.nData;
p1.data[j]:= page.data[i - 1];
inc j;
int k := 0;
while k < p2.nData do
p1.data[j] := p2.data[k];
p1.link[j]^ := p2.link[k]^;
inc j;
inc k;
end
p1.link[j]^ := p2.link[k]^;
p1.nData := j;
dec page.nData;
deletePage(p2^);
if page.nData >= nDATA /2 then
return OK;
else
return BALANCE;
end
else
int j := p2.nData + 1;
p2.link[j]^ := p2.link[j - 1]^;
dec j;
while j > 0 do
p2.data[j] := p2.data[j - 1];
p2.link[j]^ := p2.link[j - 1]^;
dec j;
end
p2 .data[j] := page.data[i - 1];
p2 .link[j]^ := p1 .link[p1.nData]^;
page.data[i - 1] := p1 .data[p1.nData - 1];
inc p2.nData;
dec p1.nData;
return OK;
end
default:
PAGE p1^ := page.link[i]^;
PAGE p2^ := page.link[i + 1]^;
if p1.nData + p2.nData + 1 <= nDATA then
int j := p1.nData;
p1.data[j]:= page.data[i];
inc j;
int k := 0;
while k < p2.nData do
p1.data[j] := p2.data[k];
p1.link[j]^ := p2.link[k]^;
inc j;
inc k;
end
p1.link[j]^ := p2.link[k]^;
p1.nData := j;
deletePage(p2^);
page.data[i] := page.data[i + 1];
inc i;
while i + 1 < page.nData do
page.data[i] := page.data[i + 1];
page.link[i]^ := page.link[i + 1]^;
inc i;
end
page.link[i]^ := page.link[i + 1]^;
dec page.nData;
if page.nData >= nDATA /2 then
return OK;
else
return BALANCE;
end
else
int j := p1.nData;
p1 .data[j] := page.data[i];
inc j;
p1 .link[j]^ := p2 .link[0]^;
inc p1.nData;
page.data[i] := p2 .data[0];
int k := 0;
while k + 1 < p2.nData do
p2.data[k] := p2.data[k + 1];
p2.link[k]^ := p2.link[k + 1]^;
inc k;
end
p2.link[k]^ := p2.link[k + 1]^;
dec p2.nData;
return OK;
end
end
end
int delete(PAGE page^^, int data, int isRoot) is
if page^ = NULL then
return NOT_FOUND;
else
int i := 0;
int j := page.nData;
while i < j do
int m := (i + j) /2;
int c := comp(data, page.data[m]);
select
case c = 0:
select
case page.link[m]^ = NULL:
int k := m;
while k + 1 < page.nData do
page.data[k] := page.data[k + 1];
page.link[k]^ := page.link[k + 1]^;
inc k;
end
page.link[k]^ := page.link[k + 1]^;
page.nData := k;
if page.nData < nDATA / 2 then
if page.nData = 0 & isRoot != 0 then
page^ := NULL;
return OK;
else
return BALANCE;
end
end
return OK;
default:
PAGE p2^ := page.link[m]^;
while p2.link[p2.nData]^ != NULL do
p2^ := p2.link[p2.nData]^;
end
page.data[m] := p2.data[p2.nData - 1];
data := p2.data[p2.nData - 1];
i := m;
exit
end
case c < 0:
j := m;
default:
i := m + 1;
end
end
int result := delete(page.link[i]^^, data, 0);
if result > OK then
result := balance(page^, i);
end
if result > OK then
if page.nData = 0 & isRoot != 0 then
page^ := page.link[0]^;
result := OK;
end
end
return result;
end
end
Поддержание сбалансированности обычного двоичного дерева тоже возможно.
По-видимому, самый первый алгоритм был предожен Адельсоном-Вельским
и Ландисом (Г. М. Адельсон-Вельский, Е. М. Ландис, Один алгоритм организации
информации, Докл. АН СССР, 1962, том 146, номер 2, 263–266). Идея алгоритма
состоит в принятии допустимости приблизительной сбалансированности дерева.
Высоты правой и левой ветвей любого поддерева не обязаны совпадать,
но не должны отличатся более, чем на единицу.
Ниже приведен очень многословный, но, возможно, простой для понимания
вариант реализации. В комментариях приведены картинки всех возможных
преобразований поддеревьев. Узлы обозначены латинскими буквами,
поддеревья - греческими (al - alpha, bt - beta и т.д.). Знаки вопроса
означают, что высота одного из поддеревьев может быть на единицу меньше,
чем это изображено.
Можно заметить, что функции балансировки дерева при удалении
мало отличаются от функций балансировки дерева при вставке и можно
использовать только одну пару.
Компилятор - Context3, ревизия не ниже 76. Версия 00.01.00 не может быть
использована из-за ошибки в реализации оператора switch.
struct NODE
int data;
int balance;
NODE left^;
NODE right^;
end
define nNODE 0x80000;
NODE nodes[nNODE];
NODE free^ := NULL;
void initNodes() is
int i := nNODE;
while i > 0 do
dec i;
nodes[i].right^ := free^;
free^ := nodes[i]^;
end
end
int comp(int p1, int p2) is // функция сравнения ключей
select
case p1 < p2:
return -1;
case p1 > p2:
return 1;
end
return 0;
end
NODE createNode()^ is
NODE temp^ := free^;
if temp^ != NULL then
free^ := free.right^;
return temp^;
end
return NULL;
end
void deleteNode(NODE node^) is
node.right^ := free^;
free^ := node^;
end
NODE root^ := NULL;
int balanceLeft (NODE node^^) is
NODE x^ := node^;
switch x.balance of
case 1:
x.balance := 0;
return 0;
case 0:
x.balance := -1;
return 1;
default:
NODE y^ := x.left^;
switch y.balance of
case -1:
/* x(-1-old, -2-new) //al < y < bt < x < gm
/ \
y(-1)\
/ \ gm
/ bt
al
|
v
y
/ \
/ x
/ / \
al bt gm*/
//NODE al^ := y.left^;
NODE bt^ := y.right^;
//NODE gm^ := x.right^;
node^ := y^;
y.balance := 0;
y.right^ := x^;
x.balance := 0;
x.left^ := bt^;
return 0;
case 0:
/* x(-1-old, -2-new) //al < y < bt < x < gm
/ \
y(0) gm
/ \
al bt*/
/*y.balance = 0 возможно только при отсутствии увеличения высоты дерева (в этом
случае функция балансировки не вызывается) или при добавлении нового узла
(al = bt = NULL, в этом случае старое значение x.balance не может быть -1).
return 0;*/
/*Если же не принимать в расчет приведенное соображение,
то можно написать следующее:*/
/* x(-1-old, -2-new) //al < y < bt < x < gm
/ \
y(0) gm
/ \
al bt
|
v
y
/ \
/ x
/ / \
al / gm
bt*/
//NODE al^ := y.left^;
NODE bt^ := y.right^;
//NODE gm^ := x.right^;
node^ := y^;
y.balance := 1;
y.right^ := x^;
x.balance := -1;
x.left^ := bt^;
return 1;
default:
/* x(-1-old, -2-new) //al < y < bt < z < gm < x < dl
/ \
y(1) \
/ \ \
/ z(?) \
/ / \ dl
al ? ? //al length unchanged
bt gm
|
v
z
/ \
/ \
/ \
y x
/ \ / \
/ ? ? \
al bt gm dl*/
//NODE al^ := y.left^;
NODE z^ := y.right^;
NODE bt^ := z.left^;
NODE gm^ := z.right^;
//NODE dl^ := z.right^;
node^ := z^;
z.left^ := y^;
z.right^ := x^;
y.right^ := bt^;
x.left^ := gm^;
switch z.balance of
case -1:
z.balance := 0;
y.balance := 0;
x.balance := 1;
case 0:
z.balance := 0;
y.balance := 0;
x.balance := 0;
default:
z.balance := 0;
y.balance := -1;
x.balance := 0;
end
return 0;
end
end
end
int balanceRight(NODE node^^) is
NODE x^ := node^;
switch x.balance of
case -1:
x.balance := 0;
return 0;
case 0:
x.balance := 1;
return 1;
default:
NODE y^ := x.right^;
switch y.balance of
case 1:
/* x(1-old, 2-new) //al < x < bt < y < gm
/ \
/ y(1)
al / \
bt \
gm
|
v
y
/ \
x \
/ \ \
al bt gm*/
//NODE al^ := x.left^;
NODE bt^ := y.left^;
//NODE gm^ := y.right^;
node^ := y^;
y.balance := 0;
y.left^ := x^;
x.balance := 0;
x.right^ := bt^;
return 0;
case 0:
/* x(1-old, 2-new) //al < x < bt < z < gm < y < dl
/ \
al y(0)
/ \
bt gm*/
/*y.balance = 0 возможно только при отсутствии увеличения высоты дерева (в этом
случае функция балансировки не вызывается) или при добавлении нового узла
(bt = gm = NULL, в этом случае старое значение x.balance не может быть 1).
return 0;*/
/*Если же не принимать в расчет приведенное соображение,
то можно написать следующее:*/
/* x(1-old) //al < x < bt < y < gm
/ \
/ y(1)
al / \
bt \
gm
|
v
y
/ \
x \
/ \ \
al \ gm
bt*/
//NODE al^ := x.left^;
NODE bt^ := y.left^;
//NODE gm^ := y.right^;
node^ := y^;
y.balance := -1;
y.left^ := x^;
x.balance := 1;
x.right^ := bt^;
return 1;
default:
/* x(1-old, 2-new) //al < x < bt < z < gm < y < dl
/ \
/ y(-1-new)
/ / \
/ z(?)\
al / \ \
? ? dl
bt gm
|
v
z
/ \
/ \
/ \
x y
/ \ / \
/ ? ? \
al bt gm dl*/
//NODE al^ := x.left^;
NODE z^ := y.left^;
NODE bt^ := z.left^;
NODE gm^ := z.right^;
//NODE dl^ := y.right^;
node^ := z^;
z.left^ := x^;
z.right^ := y^;
x.right^ := bt^;
y.left^ := gm^;
switch z.balance of
case -1:
z.balance := 0;
x.balance := 0;
y.balance := 1;
case 0:
z.balance := 0;
x.balance := 0;
y.balance := 0;
default:
z.balance := 0;
x.balance := -1;
y.balance := 0;
end
return 0;
end
end
end
int insert(NODE node^^, int data) is
if node^ = NULL then
NODE temp^ := createNode()^;
if temp^ = NULL then
return -1;
end
temp.data := data;
temp.balance := 0;
temp.left^ := NULL;
temp.right^ := NULL;
node^ := temp^;
return 1;
else
select
case comp(data, node.data) = 0:
return -1;
case comp(data, node.data) < 0:
int result := insert(node.left^^, data);
if result > 0 then
result := balanceLeft (node^^);
end
return result;
default:
int result := insert(node.right^^, data);
if result > 0 then
result := balanceRight(node^^);
end
return result;
end
end
end
int balanceLeftOnDel(NODE node^^)
NODE x^ := node^;
switch x.balance of
case -1:
x.balance := 0;
return -1;
case 0:
x.balance := 1;
return 0;
default:
NODE y^ := x.right^;
switch y.balance of
case 1:
/* x(1-old, 2-new) //al < x < bt < y < gm
/ \
/ y(1)
al / \
bt \
gm
|
v
y
/ \
x \
/ \ \
al bt gm*/
//NODE al^ := x.left^;
NODE bt^ := y.left^;
//NODE gm^ := y.right^;
node^ := y^;
y.balance := 0;
y.left^ := x^;
x.balance := 0;
x.right^ := bt^;
return -1;
case 0:
/* x(1-old, 2-new) //al < x < bt < y < gm
/ \
/ y(0-new)
al / \
/ \
bt gm
|
v
y
/ \
x \
/ \ \
al \ gm
bt*/
//NODE al^ := x.left^;
NODE bt^ := y.left^;
//NODE gm^ := y.right^;
node^ := y^;
y.balance := -1;
y.left^ := x^;
x.balance := 1;
x.right^ := bt^;
return 0;
/* x(1-old, 2-new) //al < x < bt < y < gm < z < dl
/ \
/ y(0-new)
/ / \
/ / z(?)
al / / \
/ ? ?
bt gm dl
|
v
y
/ \
/ \
/ \
/ \
x z
/ \ / \
/ \ ? ?
al \ gm dl
bt
//NODE al^ := x.left^;
NODE bt^ := y.left^;
NODE z^ := y.right^;
//NODE gm^ := z.left^;
//NODE dl^ := z.right^;
node^ := y^;
y.balance := -1;
y.left^ := x^;
//y.right^ := z^;
x.balance := 1;
x.right^ := bt^;
return 0;*/
default:
/* x(1-old, 2-new) //al < x < bt < z < gm < y < dl
/ \
/ y(-1-new)
/ / \
/ z(?)\
al / \ \
? ? dl
bt gm
|
v
z
/ \
/ \
/ \
x y
/ \ / \
/ ? ? \
al bt gm dl*/
//NODE al^ := x.left^;
NODE z^ := y.left^;
NODE bt^ := z.left^;
NODE gm^ := z.right^;
//NODE dl^ := y.right^;
node^ := z^;
z.left^ := x^;
z.right^ := y^;
x.right^ := bt^;
y.left^ := gm^;
switch z.balance of
case -1:
z.balance := 0;
x.balance := 0;
y.balance := 1;
case 0:
z.balance := 0;
x.balance := 0;
y.balance := 0;
default:
z.balance := 0;
x.balance := -1;
y.balance := 0;
end
return -1;
end
end
end
int balanceRightOnDel(NODE node^^)
NODE x^ := node^;
switch x.balance of
case 1:
x.balance := 0;
return -1;
case 0:
x.balance := -1;
return 0;
default:
NODE y^ := x.left^;
switch y.balance of
case -1:
/* x(-1-old, -2-new) //al < y < bt < x < gm
/ \
y(-1)\
/ \ gm
/ bt
al
|
v
y
/ \
/ x
/ / \
al bt gm*/
//NODE al^ := y.left^;
NODE bt^ := y.right^;
//NODE gm^ := x.right^;
node^ := y^;
y.balance := 0;
y.right^ := x^;
x.balance := 0;
x.left^ := bt^;
return -1;
case 0:
/* x(-1-old, -2-new) //al < y < bt < x < gm
/ \
y(0) \
/ \ gm
/ \
al bt
|
v
y
/ \
/ x
/ / \
al / gm
bt*/
//NODE al^ := y.left^;
NODE bt^ := y.right^;
//NODE gm^ := x.right^;
node^ := y^;
y.balance := 1;
y.right^ := x^;
x.balance := -1;
x.left^ := bt^;
return 0;
/* x(-1-old, -2-new) //al < z < bt < y < gm < x < dl
/ \
y(0) \
/ \ \
z(?) \ \
/ \ \ dl
? ? \
al bt gm
|
v
y
/ \
/ \
/ \
/ \
z x
/ \ / \
? ? / \
al bt / dl
gm
NODE z^ := y.left^;
//NODE al^ := z.left^;
//NODE bt^ := z.right^;
NODE gm^ := y.right^;
//NODE dl^ := x.right^;
node^ := y^;
y.balance := 1;
//y.left^ := z^;
y.right^ := x^;
x.balance := -1;
x.left^ := gm^;
//x.right := dl^;
return 0;*/
default:
/* x(-1-old, -2-new) //al < y < bt < z < gm < x < dl
/ \
y(1) \
/ \ \
/ z(?) \
/ / \ dl
al ? ?
bt gm
|
v
z
/ \
/ \
/ \
y x
/ \ / \
/ ? ? \
al bt gm dl*/
//NODE al^ := y.left^;
NODE z^ := y.right^;
NODE bt^ := z.left^;
NODE gm^ := z.right^;
//NODE dl^ := x.right^;
node^ := z^;
z.left^ := y^;
z.right^ := x^;
y.right^ := bt^;
x.left^ := gm^;
switch z.balance of
case -1:
z.balance := 0;
y.balance := 0;
x.balance := 1;
case 0:
z.balance := 0;
y.balance := 0;
x.balance := 0;
default:
z.balance := 0;
y.balance := -1;
x.balance := 0;
end
return -1;
end
end
end
int delete(NODE node^^, int data) is
if node^ = NULL then
return 1;
else
select
case comp(data, node.data) = 0:
select
case node.balance < 0:
NODE max^ := node.left^;
while max.right^ != NULL do
max^ := max.right^;
end
node.data := max.data;
int result := delete(node.left^^, max.data);
if result < 0 then
result := balanceLeftOnDel(node^^);
end
return result;
case node.right^ != NULL:
NODE min^ := node.right^;
while min.left^ != NULL do
min^ := min.left^;
end
node.data := min.data;
int result := delete(node.right^^, min.data);
if result < 0 then
result := balanceRightOnDel(node^^);
end
return result;
default:
deleteNode(node^);
//INFO Omitted
node^ := NULL;
return -1;
end
case comp(data, node.data) < 0:
int result := delete(node.left^^, data);
if result < 0 then
result := balanceLeftOnDel(node^^);
end
return result;
default:
int result := delete(node.right^^, data);
if result < 0 then
result := balanceRightOnDel(node^^);
end
return result;
end
end
end