Двоичные деревья и B-деревья
Задача поиска данных в большом массиве (или файле) возникает очень часто (во всех
приложениях, работающих с базами данных, но не только в них). Если массив упорядочен,
можно использовать метод деления отрезка пополам. Для этого нужно приблизительно Log(N)
сравнений - совсем немного. Но если тебуется вставлять новые данные и удалять имеющиеся,
затраты на поддержание порядка могут быть непомерны - в худшем случае для вставки и для
удаления потребуется N операций. Если не поддерживать порядок данных - непомерны будут
затраты на поиск. Кроме того, для разных целей может быть нужен разный порядок данных,
а физический порядок всего один. Решение состоит в поддержке индексов - дополнительных
упорядоченных структур данных, содержащих ключи и ссылки на основные данные. Порядок
самих данных при этом не играет никакой роли. Индексный поиск может быть столь же
эффективен, как и поиск методом деления деления в упорядоченном массиве, плюс к этому
вставки и удаления также могут выполняться быстро. Существует несколько способов
построения индексов. Во-первых, это так называемые B-деревья. В определенном смысле
B-дерево - обобщение двоичного дерева - простой конструкции, не обладающей, однако,
гарантированной эффективностью. B-дерево - не единственнная эффективная конструкция
индекса. Можно упомянуть красно-черные деревья - еще одно усовершенствование двоичных
деревьев (в настоящее время у меня нет соответствующего примера).
Из соображений простоты начать лучше именно с двоичных деревьев. Всюду ниже (также для
простоты) предполагается, что индексируемые данные находятся в оперативной памяти и в
индексе содержатся только ссылки на эти данные.
Двоичное дерево - структура данных, состоящая из узлов, каждый из которых
содержит ключ и две ссылки на поддеревья - левое и правое. Все ключи в левом
поддереве меньше ключа в узле, все ключи в правом поддереве - больше. Требование
точного неравенства ключей естественно, т.к. даже ести реальные ключи могут повторяться,
уникальность достигается расширением ключа номером (смещением, адресом) элемента данных.
Процедуры вставки и удаления ключей достаточно просты:
<![CDATA[
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) ссылки) и усложнить
функции вставки/удаления. Новый ключ всегда добавляется в нижнюю страницу, если
страница переполняется, она делится на две и средний ключ переносится на вышележащую
страницу. Если и эта страница переполняется, она тоже делится на две. В худшем
случае корневая страница будет поделена на две и будет создан новый корень,
содержащий единственный ключ. Высота дерева при этом увеличится на единицу. При
удалении наоборот, если страница становится заполненной менее чем наполовину, она
либо дополняется ключом из соседней страницы, либо две страницы объединяются (при
этом один ключ берется из вышележащей страницы):
<![CDATA[
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 и повторять этот фрагмент еще раз нет смысла,
поиск ключей из заданного диапазона немного сложнее, но все равно он значительно
проще вставки/удаления:
<![CDATA[
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-дерево [почти] не зависит от порядка меток.
Сайт создан в системе
uCoz