Древесная сортировка (TreeSort)Использует
Двоичные (бинарные) деревья, в которых для каждого предшественника выполнено следующее правило: левый преемник всегда меньше, а правый преемник всегда больше или равен предшественнику.
При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом вставляя на место: если элемент >= корня - он идет в правое поддерево, сравниваем его уже с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить.
Если мы будем рекурсивно обходить дерево по правилу "левый сын -> родитель -> правый сын", то, записывая все встречающиеся элементы в массив, мы получим упорядоченное в порядке возрастания множество. Hа этом и основана идея сортировки деревом.
Более подробно правило обхода можно сформулировать так: обойти левое поддерево -> вывести корень -> обойти правое поддерево, где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается с узлом-родителем и выдает очередной элемент, если у узла нет сыновей.
Const n = 8;
Type
TType = Integer;
arrType = Array[1 .. n] Of TType;
Const
a: arrType =
(44, 55, 12, 42, 94, 18, 6, 67);
(* Сортировка с помощью бинарного дерева *)
Type
PTTree = ^TTree;
TTree = Record
a: TType;
left, right: PTTree;
End;
{ Добавление очередного элемента в дерево }
Function AddToTree(root: PTTree; nValue: TType): PTTree;
Begin
(* При отсутствии преемника создать новый элемент *)
If root = nil Then Begin
root := New(PTTree);
root^.a := nValue;
root^.left := nil;
root^.right := nil;
AddToTree := root; Exit
End;
If root^.a < nValue Then
root^.right := AddToTree(root^.right, nValue)
Else
root^.left := AddToTree(root^.left, nValue);
AddToTree := root
End;
(* Заполнение массива *)
Procedure TreeToArray(root: PTTree; Var a: arrType);
Const maxTwo: Integer = 1;
Begin
(* При отсутствии преемников рекурсия остановится *)
If root = nil Then Exit;
(* Левое поддерево *)
TreeToArray(root^.left, a);
a[maxTwo] := root^.a; Inc(maxTwo);
(* Правое поддерево *)
TreeToArray(root^.right, a);
Dispose(root)
End;
(* Собственно процедура сортировки *)
Procedure SortTree(Var a: arrType; n: Integer);
Var
root: PTTree;
i: Integer;
Begin
root := nil;
For i := 1 To n Do
root := AddToTree(root, a[i]);
TreeToArray(root, a)
End;
Var i: Integer;
Begin
WriteLn('До сортировки:')
For i := 1 To n Do Write(a[i]:4);
WriteLn;
SortTree(a, n);
WriteLn('После сортировки:')
For i := 1 To n Do Write(a[i]:4);
WriteLn
End.
Общее быстродействие метода O(n*logn). Поведение неестественно, устойчивости, вообще говоря, нет.
Основной недостаток этого метода - большие требования к памяти под дерево. Очевидно, нужно
n места под ключи и, кроме того, память на 2 указателя для каждого из них.
Поэтому TreeSort обычно применяют там, где:
- построенное дерево можно с успехом применить для других задач;
- данные уже построены в "дерево";
- данные можно считывать непосредственно в дерево. Hапример, при потоковом вводе с консоли или из файла.
Т.е. там, где не требуется дополнительной памяти...