12.4.2. Сортировка частично упорядоченным деревом
Дерево называется частично упорядоченным, если для каждого узла справедливо следующее утверждение: значение ключа, записанное в узле, меньше, чем ключи его потомков. Для полностью упорядоченного дерева имеются требования к соотношению между ключами потомков, для данного дерева таких требований нет. Кроме того, частично сбалансированное дерево должно быть абсолютно сбалансированным. Это означает не только то, что длины путей к любым двум листьям различаются не более чем на 1, но и то, что при добавлении нового элемента в дерево предпочтение всегда отдается левой ветви, пока это не нарушает сбалансированность.
Например, последовательность чисел: 3 20 12 58 35 30 32 28 будет представлена в виде дерева, показанного на рис. 12.15.
Рис. 12.15. Частично упорядоченное дерево
Для такого дерева можно ввести понятия "начала" и "конца". Началом, естественно, будет считаться вершина пирамиды, а концом — крайний левый элемент в самом нижнем ряду (на рис. 12.15 это 58).
Для сортировки этим методом должны быть определены две операции: вставка в дерево нового элемента и выборка из дерева минимального элемента; причем выполнение любой из этих операций не должно нарушать ни сформулированной выше частичной упорядоченности дерева, ни его сбалансированности.
Алгоритм вставки состоит в следующем. Новый элемент вставляется на первое свободное место за концом дерева, на рис. 12.15 это место обозначено "пустым" узлом. Если ключ вставленного элемента меньше, чем ключ его предка, то предок и вставленный элемент меняются местами. Ключ вставленного элемента теперь сравнивается с ключом его предка на новом месте и т.д. Сравнения заканчиваются, когда ключ нового элемента окажется больше ключа предка или когда новый элемент станет корнем дерева. Дерево, показанное на рис. 12.15, построено именно последовательным включением в него чисел из приведенного ряда. Если включить, например, еще число 16, то дерево примет вид, представленный на рис. 12.16. Узлы, значения которых перемещались, выделены.
Рис. 12.16. Вставка узла в частично упорядоченное дерево
Процедура выборки элемента несколько сложнее. Очевидно, что минимальный элемент находится в вершине. После выборки за освободившееся место устраивается состязание между потомками, и в вершину перемещается потомок с наименьшим значением ключа. За освободившееся место перемещенного потомка состязаются его потомки и т.д., пока свободное место не опустится до листа дерева. Состояние дерева после выборки из него минимального числа (3) показано на рис. 12.17а.
Рис.12.17. Удаление из частично упорядоченного дерева и балансировка
Упорядоченность дерева восстановлена, но нарушено условие его сбалансированности, так как свободное место находится не в конце дерева. Для восстановления сбалансированности последний элемент дерева переносится на освободившееся место, а затем "всплывает" по тому же алгоритму, который применялся при вставке. Результат такой балансировки показан на рис. 12.17(б).
Теперь рассмотрим способ представления дерева в памяти. Дерево хранится в одномерном массиве. Узлы дерева располагаются в элементах массива по уровням. Первый элемент массива занимает вершина. Следующие 2 элемента — узлы второго уровня, следующие 4 элемента — третьего и т.д. Дерево, представленное на рис. 12.17(б), будет линеаризовано таким образом: 12 16 28 20 35 30 32 58.
При таком представлении отпадает необходимость хранить в составе узла дерева указатели, так как адреса потомков могут быть вычислены. Для узла, представленного элементом массива с индексом i, индексы его левого и правого потомков будут 2×i и 2×i+1 соответственно. Для узла с индексом i индекс его предка равен i div 2.
Модуль, позволяющий работать с частично упорядоченным деревом, приведен в листинге 12. 13.
Дерево представлено в массиве tree, переменная LastT является индексом первого свободного элемента в массиве. В модуле содержатся:
процедура InitST установка начального значения LastT;
функция InsertST — вставка в дерево нового элемента; функция возвращает false, если в дереве нет свободного места, иначе — true;
функция DeleteST — выборка из вершины дерева минимального элемента; функция возвращает false, если дерево пустое, иначе — true;
функция CheckST — проверка состояния дерева: ключ минимального элемента возвращается в выходном параметре, но элемент не исключается из дерева; а возвращаемое значение функции — empty, если дерево пустое; part — если дерево заполнено частично; full — если дерево заполнено до конца;
функция Down — обеспечивает спуск свободного места из вершины дерева в нижний уровень, функция возвращает индекс свободного места после спуска;
процедура Up, обеспечивающая всплытие элемента с заданного места.
Листинг 12.13. Частично упорядоченное дерево. Вставка и удаление
unit UntTree;
interface
const NTree=16;
type TKey = integer;
TNode = record
key: TKey;
xN,yN: integer; // координаты узла на канве
end;
TTree = array[1..NTree] of TNode;
StateTree = (empty, full, part); // дерево пустое, полное, частично заполненное
var tree : TTree; { дерево }
LastT : integer; // индекс последнего эл-та в дереве
procedure InitSt;
function CheckST(var tr: TTree; var a: TKey): StateTree;
function InsertST(var tr: TTree; a: TKey): boolean;
function DeleteST(var tr: TTree; var a: TKey): boolean;
implementation
procedure Up(var tr: TTree; l: integer);
// Всплытие эл-та с места с индексом l
var h : integer; // l - индекс узла, h - индекс его предка
x : integer;
begin
h:=l div 2; // индекс предка
while h>0 do // до начала дерева
if tr[l].key<tr[h].key then begin // ключ узла меньше, чем у предка
x:=tr[l].key; tr[l].key:=tr[h].key; tr[h].key:=x; // перестановка
l:=h; h:=l div 2; // предок становится текущим узлом
end
else h:=0; // конец всплытия
end;
function Down(var tr: TTree): integer;
// Спуск свободного места из начала дерева
var h,l: integer; // h - индекс узла, l - индекс его потомка
begin
h:=1; // начальный узел - начало дерева
while true do
begin
l:=h*2; // вычисление индекса 1-го потомка
if l+1<=LastT then
begin // у узла есть 2-й потомок
if tr[l].key <= tr[l+1].key then begin // 1-й меньше 2-го
tr[h].key:=tr[l].key; // 1-й переносится в текущ.узел
h:=l; // 1-й становится текущим узлом
end
else begin // 2-й потомок меньше 1-го
tr[h].key:=tr[l+1].key; // 2-й переносится в текущ.узел
h:=l+1; // 2-й становится текущим узлом
end;
end
else
if l=LastT then begin// 1-й потомок есть, 2-го нет
tr[h].key:=tr[l].key; // 1-й переносится в текущ.узел
Down:=l; Exit; // спуск закончен
end
else begin // потомков нет - спуск закончен
Down:=h; Exit;
end;
end; // while
end;
// Инициализация сортировки деревом
procedure InitSt;
begin
LastT:=0;
end;
function CheckST(var tr: TTree; var a: TKey): StateTree;
//function CheckST(var t: TTree; var a: TKey): StateTree;
// Проверка состояния дерева
begin
a:=tr[1].key; // выборка эл-та из начала
case LastT of // формирование возвращаемого значения функции
0: { дерево пустое } CheckSt:=empty;
NTree: { дерево полное } CheckSt:=full;
else { дерево частично заполнено } CheckSt:=part;
end;
end;
function InsertST(var tr: TTree; a: TKey): boolean;
// Вставка эл-та a в дерево
begin
if LastT=NTree then { дерево заполнено - отказ } Result:=false
else begin // в дереве есть место
inc(LastT); tr[LastT].key:=a; // запись в конец дерева
Up(tr, LastT); // всплытие
Result:=true;
end;
end;
function DeleteST(var tr: TTree; var a: TKey): boolean;
// Выборка элемента из дерева
var n : integer;
begin
if LastT=0 then { дерево пустое - отказ } Result:=false
else begin // дерево не пустое
a:=tr[1].key; // выборка элемента из начала
n:=Down(tr); // спуск свободного места в позицию n
if n<LastT then begin
// если свободное место спустилось не в конец дерева
// элемент из конца переносится на своб.место
tr[n].key:=tr[LastT].key;
Up(tr,n); // всплытие
end;
dec(LastT);
Result:=true;
end;
end;
end.
end.
Типичная задача, для которой сортировка частично упорядоченным деревом наиболее подходящая, возникает при сортировке файлов. Первым этапом такой сортировки является формирование из данных исходного файла упорядоченных последовательностей максимально возможной длины — так называемых серий — при ограниченном объеме оперативной памяти. Сформированные серии последовательно записываются в выходной файл.
Алгоритм формирования серий следующий. Считывается последовательность чисел, записанная во входном файле, и числа по мере считывания включаются в дерево. Когда дерево оказывается заполненным, очередное считанное из файла число сравнивается с последним числом, выведенным в выходной файл. Если считанное число не меньше последнего выведенного, но меньше числа, находящегося в вершине дерева, то в выходной файл выводится считанное число. Если считанное число не меньше последнего выведенного, и не меньше числа, находящегося в вершине дерева, то в выходной файл выводится число, выбираемое из дерева, а считанное число заносится в дерево. Наконец, если считанное число меньше последнего выведенного, то поэлементно выбирается и выводится все содержимое дерева, и формирование новой последовательности начинается с записи в пустое дерево считанного числа.
Проект работы с частично упорядоченным деревом позволяет моделировать создание серий. Форма проекта представлена на рис. 12.18.
Рис. 12.18. Форма проекта работы с частично упорядоченным деревом
На форме выставлены компоненты:
компонент Edit для ввода очередного значения;
кнопка Вставить новое значение, нажатие которой приводит к вставке нового значения в дерево с его последующей балансировкой;
кнопка Удалить корень, при нажатии на которую значение из корня дерева переносится на форму, создавая серию. Если серия заканчивается, то новая серия начинает выводиться на форме ниже первой.
Дерево, нарисованное на форме, построено в результате включения последовательности чисел: 3 20 12 58 35 30 32 28.
Если шесть раз нажить кнопку Удалить корень, а потом вставить еще четыре числа: 2 13 7 15, то дерево и серии будут такими, как показано на рис. 12.19а.
Рис. 12.19. Формирование серий частично упорядоченным деревом
Результат удаления еще пяти значений, вставки пяти чисел: 3 6 2 1 и 67, и удаления трех значений из корня показан на рис. 12.19(б).
Необходимые данные и обработчики кнопок формы приведены в листинге 12.14. Процедура рисования дерева при таком представлении чрезвычайно проста: требуется только один проход по массиву.
Листинг 12.14. Формирование серий и рисование частично упорядоченного дерева
const diametr = 25; // диаметр рисуемого узла
yRoot = 70; // y-координата корня
var
Form1: TForm1;
x,y: integer; // координаты узла дерева
radius: integer; // радиус узла
shift: integer; // x-расстояние между узлами-результатами
yLevel: integer; // y-координата для вывода результатов
tail : TKey; // последнее значение в серии
implementation
{$R *.DFM}
procedure TForm1.DrawNode(x,y: integer; s: String; rez: Boolean);
var len, xPlus: integer;
begin
len:=Length(s);
xPlus:=len*3;
with Form1.canvas do begin
brush.Style:=bsSolid;
if rez then Brush.Color:=cl3DLight // цвет серий
else Brush.Color:=clBtnFace; // цвет узлов дерева
MoveTo(x,y);
Ellipse(x,y,x+diametr,y+diametr);
TextOut(x+diametr div 2-xPlus ,y+diametr div 5,s);
end;
end;
procedure TForm1.DrawBranch(xP,yP,x,y: integer);
// рисование ветви от предка (xP,yP) к потомку (x,y)
begin
with Form1.canvas do begin
brush.Style:=bsSolid;
Brush.Color:=clBlack;
MoveTo(xP+radius,yP+diametr);
LineTo(x+radius,y)
end
end;
procedure TForm1.DrawTree(t: TTree);
var i,j,k : integer;
x0,y0 : integer; // x- и y-расстояния между узлами на канве
begin
j:=1; // число узлов на уровне
i:=1; // количество нарисованных узлов
x0:= Width; y:=yRoot+3*diametr; y0:=45;
while (i<=LastT) do begin // цикл по всем узлам дерева
k:=1;
x0:=Width div (j+1); // x-расстояние между узлами
x:=x0;
while (k<=j)and (i<=LastT) do begin // цикл по узлам на уровне
Form1.DrawNode(x,y,IntToStr(tree[i].key),false);
tree[i].xN:=x; tree[i].yN:=y; // запомнить координаты узла
if (i div 2)>0 then // если предок есть, рисуем ветвь
Form1.DrawBranch(tree[i div 2].xN,tree[i div 2].yN,x,y);
inc(i); inc(k);
x:=x+x0; // сдвиг узла по горизонтали
end;
j:=2*j; // число узлов на следующем уровне
y:=y+y0; // сдвиг уровня
end;
end;
procedure TForm1.BtnInsertClick(Sender: TObject);
var i: TKey;
begin
i:=StrToInt(EdtIn.Text);
with canvas do begin
Brush.Style:=bsSolid;
Brush.Color:=clBtnFace;
FillRect(Rect(0,yLevel+diametr,Width,Height));
end;
if InsertST(tree, i) then
// рисование дерева
Form1.DrawTree(tree)
else ShowMessage('Дерево заполнено');
EdtIn.SetFocus;
end;
procedure TForm1.BtnDelClick(Sender: TObject);
var i: TKey;
k: integer;
begin
if DeleteST(tree, i) then begin
if i<tail then begin
// подготовка геометрии для вывода новой серии
shift:=radius; yLevel:=yLevel+diametr+5;
end;
tail:=i; // запомнить последнее значение серии
// очистка канвы и рисование
with canvas do begin
DrawNode(shift,yLevel, IntToStr(i), true);
for k:=1 to 5 do begin
// мигание указательной линии
MoveTo((Width div 2)+radius, yRoot+3*diametr);
Brush.Style:=bsSolid;
Brush.Color:=clRed;
Sleep(100);
LineTo(shift+radius, yLevel+diametr);
Brush.Style:=bsSolid;
Brush.Color:=clBtnFace;
MoveTo((Width div 2)+radius, yRoot+3*diametr);
LineTo(shift+radius, yLevel+diametr);
end;
shift:=shift+diametr+3;
Brush.Style:=bsSolid;
Brush.Color:=clBtnFace;
FillRect(Rect(0,yLevel+diametr,Width,Height));
DrawTree(tree)
end;
end
else ShowMessage('Дерево пусто!');
EdtIn.SetFocus;
end;
Если применять сортировку частично упорядоченным деревом для упорядочения уже готовой последовательности размером N, то необходимо N раз выполнить вставку, а затем N раз — выборку. Порядок алгоритма: N×log2N, но среднее значение количества сравнений примерно в 3 раза больше, чем для турнирной сортировки. Но сортировка частично упорядоченным деревом имеет одно существенное преимущество перед всеми другими алгоритмами. Дело в том, что это самый удобный алгоритм для сортировки on-line, когда сортируемая последовательность не зафиксирована до начала сортировки, а меняется в процессе работы, и вставки чередуются с выборками. Каждое изменение (добавление или удаление элемента) сортируемой последовательности потребует здесь не более чем 2×log2N сравнений и перестановок, в то время как другие алгоритмы потребуют при единичном изменении переупорядочивания всей последовательности "по полной программе".