Частично упорядоченное дерево, исключение элемента

Рисунок3.17. Частично упорядоченное дерево, исключение элемента

Упорядоченность дерева восстановлена, но нарушено условие его сбалансированности, так как свободное место находится не в конце дерева. Для восстановления сбалансированности последний элемент дерева переносится на освободившееся место, а затем "всплывает" по тому же алгоритму, который применялся при вставке. Результат такой балансировки показан на рис.3.17.б.

Прежде, чем описывать программный пример, иллюстрирующий сортировку частично упорядоченным деревом - пример 3.13, обратим внимание читателей на способ, которым в нем дерево представлено в памяти. Это способ представления двоичных деревьев в статической памяти (в одномерном массиве), который может быть применен и в других задачах. Элементы дерева располагаются в соседних слотах памяти по уровням. Самый первый слот выделенной памяти занимает вершина. Следующие 2 слота - элементы второго уровня, следующие 4 слота - третьего и т.д. Дерево с рис.3.17.б, например, будет линеаризовано таким образом:

12 16 28 20 35 30 32 58

В таком представлении отпадает необходимость хранить в составе узла дерева указатели, так как адреса потомков могут быть вычислены. Для узла, представленного элементом массива с индексом i индексы его левого и правого потомков будут 2*i и 2*i+1 соответственно. Для узла с индексом i индекс его предка будет i div 2.

После всего вышесказанного алгоритм программного примера 3.13 не нуждается в особых пояснениях. Поясним только структуру примера. Пример оформлен в виде законченного программного модуля, который будет использован и в следующем примере. Само дерево представлено в массиве tree, переменная nt является индексом первого свободного элемента в массиве. Входные точки модуля:

процедура InitST - инициализация модуля, установка начального значения nt;
функция InsertST - вставка в дерево нового элемента; функция возвращает false, если в дереве нет свободного места, иначе - true;
функция DeleteST - выборка из дерева минимального элемента; функция возвращает false, если дерево пустое, иначе - true;
функция CheckST - проверка состояния дерева: ключ минимального элемента возвращается в выходном параметре, но элемент не исключается из дерева; а возвращаемое значение функции - 0 - если дерево пустое, 1 - если дерево заполнено не до конца, 2 - если дерево заполнено до конца.

Кроме того в модуле определены внутренние программные единицы:

функция Down - обеспечивает спуск свободного места из вершины пирамиды в ее основание, функция возвращает индекс свободного места после спуска;
процедура Up - обеспечивающая всплытие элемента с заданного места.

{===== Программный пример 3.13 =====} { Сортировка частично упорядоченным деревом } Unit SortTree; Interface Procedure InitSt; Function CheckST(var a : integer) : integer; Function DeleteST(var a : integer) : boolean; Function InsertST(a : integer) : boolean; Implementation Const NN=16; var tr : array[1..NN] of integer; { дерево } nt : integer; { индекс последнего эл-та в дереве } {** Всплытие эл-та с места с индексом l **} Procedure Up(l : integer); var h : integer; { l - индекс узла, h - индекс его предка } x : integer; begin h:=l div 2; { индекс предка } while h > 0 do { до начала дерева } if tr[l] < tr[h] then begin { ключ узла меньше, чем у предка } x:=tr[l]; tr[l]:=tr[h]; tr[h]:=x; { перестановка } l:=h; h:=l div 2; { предок становится текущим узлом } end else h:=0; { конец всплытия } end; { Procedure Up } {** Спуск свободного места из начала дерева **} Function Down : integer; var h, l : integer; { h - индекс узла, l - индекс его потомка } begin h:=1; { начальный узел - начало дерева } while true do begin l:=h*2; { вычисление индекса 1-го потомка } if l+1

Если применять сортировку частично упорядоченным деревом для упорядочения уже готовой последовательности размером N, то необходимо N раз выполнить вставку, а затем N раз - выборку. Порядок алгоритма - O(N*log2(N)), но среднее значение количества сравнений примерно в 3 раза больше, чем для турнирной сортировки. Но сортировка частично упорядоченным деревом имеет одно существенное преимущество перед всеми другими алгоритмами. Дело в том, что это самый удобный алгоритм для "сортировки on-line", когда сортируемая последовательность не зафиксирована до начала сортировки, а меняется в процессе работы и вставки чередуются с выборками. Каждое изменение (добавление/удаление элемента) сортируемой последовательности потребует здесь не более, чем 2*log2(N) сравнений и перестановок, в то время, как другие алгоритмы потребуют при единичном изменении переупорядочивания всей последовательности "по полной программе".

Типичная задача, которая требует такой сортировки, возникает при сортировке данных на внешней памяти (файлов). Первым этапом такой сортировки является формирование из данных файла упорядоченных последовательностей максимально возможной длины при ограниченном объеме оперативной памяти. Приведенный ниже программный пример (пример 3.14) показывает решение этой задачи.

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

{===== Программный пример 3.14 =====} { Формирование отсортированных последовательностей в файле } Uses SortTree; var x : integar; { считанное число } y : integer; { число в вершине дерева } old : integer; { последнее выведенное число } inp : text; { входной файл } out : text; { выходной файл } bf : boolean; { признак начала вывода последовательности } bx : boolean; { рабочая переменная } begin Assign(inp,'STX.INP'); Reset(inp); Assign(out,'STX.OUT'); Rewrite(out); InitST; { инициализация сортировки } bf:=false; { вывод последовательности еще не начат } while not Eof(inp) do begin ReadLn(inp,x); { считывание числа из файла } { если в дереве есть свободное место - включить в дерево } if CheckST(y)