Двоичные деревья и B-деревья
Задача поиска данных в большом массиве (или файле) возникает очень часто (во всех приложениях, работающих с базами данных, но не только в них). Если массив упорядочен, можно использовать метод деления отрезка пополам. Для этого нужно приблизительно Log(N) сравнений - совсем немного. Но если тебуется вставлять новые данные и удалять имеющиеся, затраты на поддержание порядка могут быть непомерны - в худшем случае для вставки и для удаления потребуется N операций. Если не поддерживать порядок данных - непомерны будут затраты на поиск. Кроме того, для разных целей может быть нужен разный порядок данных, а физический порядок всего один. Решение состоит в поддержке индексов - дополнительных упорядоченных структур данных, содержащих ключи и ссылки на основные данные. Порядок самих данных при этом не играет никакой роли. Индексный поиск может быть столь же эффективен, как и поиск методом деления деления в упорядоченном массиве, плюс к этому вставки и удаления также могут выполняться быстро. Существует несколько способов построения индексов. Во-первых, это так называемые B-деревья. В определенном смысле B-дерево - обобщение двоичного дерева - простой конструкции, не обладающей, однако, гарантированной эффективностью. B-дерево - не единственнная эффективная конструкция индекса. Можно упомянуть красно-черные деревья - еще одно усовершенствование двоичных деревьев (в настоящее время у меня нет соответствующего примера).
Из соображений простоты начать лучше именно с двоичных деревьев. Всюду ниже (также для простоты) предполагается, что индексируемые данные находятся в оперативной памяти и в индексе содержатся только ссылки на эти данные.
Двоичное дерево - структура данных, состоящая из узлов, каждый из которых содержит ключ и две ссылки на поддеревья - левое и правое. Все ключи в левом поддереве меньше ключа в узле, все ключи в правом поддереве - больше. Требование точного неравенства ключей естественно, т. к. даже ести реальные ключи могут повторяться, уникальность достигается расширением ключа номером (смещением, адресом) элемента данных. Процедуры вставки и удаления ключей достаточно просты:
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 PP2:
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 C0:
@P=@Node[P].pLeft;
case C=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) ссылки) и усложнить функции вставки/удаления. Новый ключ всегда добавляется в нижнюю страницу, если страница переполняется, она делится на две и средний ключ переносится на вышележащую страницу. Если и эта страница переполняется, она тоже делится на две. В худшем случае корневая страница будет поделена на две и будет создан новый корень, содержащий единственный ключ. Высота дерева при этом увеличится на единицу. При удалении наоборот, если страница становится заполненной менее чем наполовину, она либо дополняется ключом из соседней страницы, либо две страницы объединяются (при этом один ключ берется из вышележащей страницы):
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 PP2:
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 I0:
J=K;
case SPath[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 P0Path[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
if pLink<=M then
int I=M;
int J=0;
while IPath[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=0 then
I=M+1;
J=0;
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 I0:
J=K;
case S=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].pLink1 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 MnDATA 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=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=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
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=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
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 I0 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-дерево [почти] не зависит от порядка меток.
