Явное использование структуры бинарного дерева позволяет быстро вставлять и удалять записи и производить эффективный поиск, и особенно целесообразно для организации динамических таблиц, подверженных частым вставкам и удалениям.
Рассмотрим простой метод построения дерева. Первую запись с ключом К1поместим в корень дерева. Второй ключ К2 сравним с К1. Если К2 < К2, поместим его в левое поддерево, а если К2 ³ К1, то в правое поддерево. В общем случае, когда требуется поместить в дерево i-йключ, поступаем так: сравниваем Кi с ключами, начиная с корня. Если Кi меньше очередного ключа, то переходим к левому сыну, в противном случае – к правому, а если соответствующий сын отсутствует, то это и есть место, куда нужно вставить ключ Ki. Пусть структура узла дерева:
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)
