Древовидные таблицы

Явное использование структуры бинарного дерева позволяет быстро вставлять и удалять записи и производить эффективный поиск, и особенно целесообразно для организации динамических таблиц, подверженных частым вставкам и удалениям.

Рассмотрим простой метод построения дерева. Первую запись с ключом К₁поместим в корень дерева. Второй ключ К₂ сравним с К₁. Если К₂ < К₂, поместим его в левое поддерево, а если К₂ ³ К₁, то в правое поддерево. В общем случае, когда требуется поместить в дерево i-йключ, поступаем так: сравниваем К_i с ключами, начиная с корня. Если К_i меньше очередного ключа, то переходим к левому сыну, в противном случае – к правому, а если соответствующий сын отсутствует, то это и есть место, куда нужно вставить ключ K_i. Пусть структура узла дерева:

struct NODE {

void *Record; // указатель на запись таблицы

NODE *Left, *Right;

};

Пусть int Cmp(const void *Record1, const void *Record2) –функция, выполняющая сравнение ключей записей *Record1 и *Record2.Функция традиционно возвращает значения <0,0,>0 соответственно в случаях ключ1<ключ2, ключ1=ключ2иключ1>ключ2.

Функция, выполняющая вставку новой записи в древовидную таблицу, приведена ниже:

const int LEFT=0;

const int RIGHT=1;

//----------------------------------

NODE *InsertRecord(NODE *Root, void *NewRecord){

NODE *x,*Cur,*Next;

int WhatSon; // каким сыном устанавливать новую запись –

// - левым (LEFT) или правым (RIGHT)

int CmpKeys; // результат сравнения ключей

x=new NODE;

x->Record=NewRecord;

Cur=Root;

// поиск места вставки

for(;;){

CmpKeys=Cmp(NewRecord,Cur->Record);

switch(CmpKeys){

case –1:

WhatSon=LEFT;

Next=Cur->Left;

Break;

case 0:

case 1:

WhatSon=RIGHT;

Next=Cur->Right;

Break;

}

if(Next==NULL){

Break;

}

Cur=Next;

}

if(WhatSon==LEFT){

Cur->Left=x;

} else {

Cur->Right=x;

}