Цифровая сортировка базы данных "Жизнь замечательных людей", страница 2

2.3. Двоичное Б – дерево.

ДБД  - частный случай Б – деревьев порядка m (в нашем случае m = 1).

Б – деревья обадают свойствами:

-  в каждой вершине (странице) хранится k – элементов данных;

d1<d2<d3…<dk и k+1 – указатель p0,p1,…,pk

указатель хранит либо 0, либолибо адрес вершины, все элементы которой упорядочены;

-  для каждой вершины, кроме корня,

m<=k<=2*m

для корня    

1<=k<=2*m

-  все листья дерева расположены на одном уровне;

-  если спроецирровать все вершины дерева на 1 уровень, то мы получим упорядоченную последовательность;

Б – деревья большого порядка m предназначены для работы с крупномасштабными данными.

Вообще, структура двоичного Б – дерева следующая:

каждая вершина  содержит 1 или 2 элемента и соответственно 2 или 3                             указателя. Здесь, в сравнении с обычным Б – деревом, мы отказались от представления страницы в виде массиве.

Используем списочную структуру. Внутри страницы организуется список из 1-го или 2-х элементов. Объединяем ссылки на потомков со ссылками горизонтальными.

Порядок дерева (m=1) позволяет отслеживать разницу между горизонтальными и вертикальными ссылками с помощью логических переменных.

Фактически, элементы такого дерева самостоятельны и страницы сохраняются условно.

Оценка высоты ДБД:

h<log(n+1).

В худшем случае, время поиска в  ДБД превышает высоту в 2 раза:                L<2*log(n+1)

(Например, у АВЛ – деревьев L=1.44*log(n))

Применение Б – деревьев предпочтительнее,  когда добавление новых вершин происходит чаще, чем поиск, поскольку построение такого дерева сравнительно несложное.

3. Текст программы

uses crt;

const

n=4000;

type

{------------------------------------}

zapis=record

avtor:array[1..12] of char;

zaglavie:array[1..32] of char;

izdanie:array[1..16] of char;

god:word;

page_number:word;

end;

{------------------------------------}

ple=^predpriyatie;

predpriyatie = record

next:ple;

case word of

1: (data:zapis);

2: (digit:array[1..sizeof(zapis)] of byte);

end;

{------------------------------------}

pv=^vertex;

vertex = record

data:zapis;

bal:integer;

right:pv;

left:pv;

end;

{------------------------------------}

mas=array[1..n] of ple;

mas2=array[1..8] of char;

type

elem=array[1..80] of char;

const

smes_x=20;

smes_y=10;

smes_str=1;

max_punktov=10;

function viv(y:integer;col:integer;pn:integer):integer;

var

punkt:array[1..max_punktov] of elem;

i,j,k,k1,sch,pv:integer;

zn:integer;

ch:char;

nm:string[20];

tlf:longint;

begin

textbackground(col);

gotoxy(smes_x,y+smes_y);

writeln(punkt[pn]);

end;

function menu(beg:integer;nd:integer;_color:integer;ink:integer):integer;

var

i,zn,tek,old:integer;

ch:char;

begin

textcolor(ink);

viv(beg*smes_str,_color,beg);

for i:=beg+1 to nd do viv(i*smes_str,0,i);

tek:=beg;old:=beg;

while(true) do

begin

ch:=readkey;

if (ch=#72) then begin if (tek>beg)then

begin old:=tek;dec(tek);end;end;

if (ch=#80)then begin if (tek<nd) then begin old:=tek;inc(tek);end;end;

if (ch=#27) then break;

if (ch=#13) then break;

if (tek>=beg) and (tek<=nd) then viv(tek*smes_str,_color,tek);

if (old>=beg) and (old<=nd) and (tek<>old) then viv(old*smes_str,0,old);

end;

zn:=tek;

textcolor(7);

end;

{------------------------------------}

function compare(a1:zapis;a2:zapis):integer;

var

i:integer;

check:integer;

begin

i:=1;

check:=0;

while true do

begin

if i>3 then break;

if (a1.avtor[i]>a2.avtor[i]) then

begin

check:=1;

break;

end

ELSE

if a1.avtor[i]<a2.avtor[i] then

begin

check:=-1;

break;

end

ELSE

if (a1.avtor[i+1]>a2.avtor[i+1]) then

begin

check:=1;

break;

end

ELSE

if a1.avtor[i+1]<a2.avtor[i+1] then

begin

check:=-1;

break;

end

ELSE

if a1.avtor[i+2]>a2.avtor[i+2] then

begin

check:=1;

break;

end

ELSE

if a1.avtor[i+2]<a2.avtor[i+2] then

begin

check:=-1;

break;

end;

i:=i+1;

end;

compare:=check;

end;

{----------------------------------------------------------------}

procedure ZAGRUZKA (name_file:string;var head:ple;var sch:longint);

var

f:file of zapis;

p:ple;

i:integer;

begin

i:=0;

assign(f,name_file);

reset(f);

while(not(eof(f))) do