Контрольные вопросы

1. Какова оценка времени поиска записи в сортированной таблице?

2. Какие проблемы вызывают операции вставки и удаления для сортированной таблицы?

3. Какова нижняя граница времени работы сортировки, основанной на сравнениях ключей?

4. Перечислите известные вам методы внутренней сортировки.

5. Дайте описание алгоритмов внутренней сортировки, имеющих время работы порядка

6. В чем заключается принципиальное отличие внешней сортировки от внутренней?

7. Опишите метод, позволяющий порождать сортированные отрезки длины большей, чем объем оперативной памяти, отведенной для этого.

8. За счет чего удается избежать операций копирования при использовании Фибоначчиева слияния?

9. Каким методом может быть выполнена внешняя сортировка данных без использования дополнительных файлов?

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

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

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

struct NODE {

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

NODE *Left, *Right;

};

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

}

return x;

}

Рис 41. Результат вставки ключей в бинарное дерево

На рис. 41 изображен результат работы алгоритма.

Операция удаления узла. Сначала заметим, что обход бинарного дерева в обратном порядке даёт сортированную последо­ва­тель­ность. Все замечательные свойства древовидной таблицы связаны с этим обстоятельством. При удалении узла необходимо сохранить порядок следования узлов в обратном порядке. Легко удалить лист или узел, у которого пуста правая или левая связь. В общем случае одно из возможных решений таково: удалить следующий в обратном порядке узел, левая связь которого пуста, а затем вернуть его на место узла, который действительно требуется удалить. Ниже приведен текст функции, удаляющей узел, содержащий запись с целым ключом Key. Здесь предполагается, что дерево имеет голову, и, что само дерево является левым поддеревом головы. Голова содержит максимально возможное значение ключа. В случае успеха функция возвращает true.

struct NODE {