АВЛ дерево поиска

Структура данных непосредственно AVL-дерева представляет собой бинарное дерево поиска, где один узел дерева хранит информацию об одном авиарейсе. Ключом элемента является вторая половина номера авиарейса, состоящая из трех цифр.

Структура данных flight содержит следующие поля:

//Структура, включающая все данные об авиарейсе.

struct flight.

{.

string fnum; //Номер авиарейса (обязательно 10 символов).

string fcom; //Название авиакомпании.

string fin; //Пункт отправления.

string fto; //Пункт прибытия.

string fdate; //Дата отправления.

string ftime; //Время прибытия.

int qfree; //Количество свободных мест.

int qtotal; //Количество всех мест.

int key; //Код авиарейса (для дерева).

flight* left; //Указатель на левый элемент.

flight* right; //Указатель на правый элемент.

int height; //Высота поддерева.

//Конструктор структуры flight.

flight (string nu, string co, string in, string to, string da, string ti, int qt, int k).

{.

fnum = nu;

fcom = co;

fin = in;

fto = to;

fdate = da;

ftime = ti;

qtotal = qt;

qfree = qt;

key = k;

left = right = 0;

height = 0;

}.

};

Добавление нового элемента в дерева производится рекурсивно по принципу, ключевое_поле > =поле_в_узле => вызывается функция с указателем на правого потомка узла, ключевое_полевызывается функция с указателем на левого потомка.

Обход дерева осуществляется в соответствии с номером задания, т. е. в данном случае используется обратный обход дерева.

Например обход используется для удаления объектов:

void fdelall (flight* cur).

{.

if (cur).

{.

fdelallr (cur->right);

fdelallr (cur->left);

delete cur;

}.

}.

Необходимый элемент дерева, балансировка, реализована в данном проекте следующим образом.

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

flight* fbalance (flight* p).

{.

ffixheight (p); //Коррекция высот вершин.

//Если разница поддеревьев равна 2.

if (fbalancefactor (p)==2).

{.

if (fbalancefactor (p->right) < 0).

p->right = frr (p->right);

return frl (p);

}.

//Если разница поддеревьев равна -2.

if (fbalancefactor (p)==-2).

{.

if (fbalancefactor (p->left) > 0).

p->left = frl (p->left);

return frr (p);

}.

return p; // балансировка не нужна.

}.

Если баланс фактор узла равен двойке, то задействуется функция правого поворота узла дерева, затем левого. В противном случае функции вызываются в обратном порядке.

//Функция, осуществляющая правый поворот вокруг p.

flight* frr (flight* p).

{.

flight* q = p->left; //Вспомогательный указатель для осуществления вращения.

//Вращение.

p->left = q->right;

q->right = p;

//Коррекция высот вершин, которые подверглись вращению.

ffixheight (p);

ffixheight (q);

return q; //Возвращение новой вершины.

}.

//Функция, осуществляющая левый поворот вокруг p.

flight* frl (flight* q).

{.

flight* p = q->right; //Вспомогательный указатель для осуществления вращения.

//Вращение.

q->right = p->left;

p->left = q;

//Коррекция высот вершин, которые подверглись вращению.

ffixheight (q);

ffixheight (p);

return p; //Возвращение новой вершины.

}.

Баланс фактор высчитывается следующей функцией:

//Функция, вычисляющая balance factor заданного узла (и работает только с ненулевыми указателями).

int fbalancefactor (flight* p).

{.

return fheight (p->right)-fheight (p->left);

}.

В начале работы функции выполняется пересчет высоты дерева. Пересчет выполняется при каждой итерации балансировки. Пересчет выполняется следующей функцией:

void ffixheight (flight* p).

{.

unsigned char hl = fheight (p->left);

unsigned char hr = fheight (p->right);

p->height = (hl>hr?hl:hr)+1;

}.

Высота наследников узла высчитывается следующим образом. Функция усложнена для предотвращения выпадения null pointer exception.

unsigned char fheight (flight* p).

{.

return p? p->height:0;

}.

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

Структура данных Registr содержит следующие поля:

//Структура, включающая в себя данные о билетах.

struct ticket.

{.

psng* pas; //Указатель на пассажира, купившего билет.

flight* fli; //Указатель на авиарейс, на который был куплен билет.

int tnum; //Номер билета.

bool frag; //Флаг продажи [1] - билет действующий [0] - билет был возвращен.

ticket* next; //Указатель на следующий элемент по очереди.

ticket* sloy; //Указатель на следующий элемент по слою.

//Конструктор структуры ticket.

ticket (psng* p, flight* f, bool fr).

{.

pas = p;

fli = f;

tnum = tikn;

frag=fr;

//Увеличение номера следующего билета.

tikn++;

next = sloy = 0;

}.

};

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

Добавление элемента происходит таким образом:

//Функция добавления билета в список (tnw — указатель на новый элемент на добавление).

bool tadd (ticket* tnw).

{.

//Если поля пассажира или авиарейса пусты.

if ((!tnw->pas)||(!tnw->fli)).

return 1;

//Если список пустой.

if (!tfirst).

tfirst=tnw;

//Если в списке есть первый элемент.

else.

{.

tnw->next=tfirst;

tfirst=tnw;

}.

//Если билет действующий, уменьшение свободных мест самолета.

if (tnw->frag).

tnw->fli->qfree—;

//Перераспределение указателей.

tfix ();

return 0;

}.

Удаление так же проводится нерекурсивно.