Сортировка с помощью двоичного дерева — Pascal(Паскаль)

[AdSense-B]

Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока (например, файла, сокета или консоли).

Алгоритм

Построение двоичного дерева.
Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.

Эффективность

Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка $O(log(n))$ . Соответственно, для n объектов сложность будет составлять $O(n\,log(n))$ , что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать $O(n)$ , что может привести к общей сложности порядка $O(n^{2})$ .

При физическом развёртывании древовидной структуры в памяти требуется не менее чем $4n$ ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.

Примеры реализации

program project1;
type
  TData  = integer;
  TTree = ^Tree;
  Tree = record
    Data : TData;
    Left, Right : TTree;
  end;
procedure AddToTree(var T : TTree; aData : TData);
begin
  If T=nil then begin
    New(T);
    T^.Data:=aData;
    T^.Left:=nil; T^.Right:=nil;
  end else If T^.Data>=aData then AddToTree(T^.Right,aData)
  else AddToTree(T^.Left,aData);
end;
procedure PrintTr(T : TTree);
begin
  If T = nil then exit;
  PrintTr(T^.Left);
  write(T^.Data:4);
  PrintTr(T^.Right);
end;
function HightTr(aTree : TTree) : integer;
var MaxL : integer;
procedure Uroven(aTree : TTree; L : integer);
begin
  if aTree = nil then exit;
  If L > MaxL then MaxL := L;
  Uroven(aTree^.Left,L+1);
  Uroven(aTree^.Right,L+1);
end;
begin
  MaxL := 0;
  Uroven(aTree,0);
  HightTr := MaxL;
end;
var
  n, i : integer;
  a : TData;
  T : TTree;
begin
  write('Number of Nodes in tree : '); readln(n);
  T := nil; randomize;
  for i := 1 to n do begin
    a := random(51)-25;
    write(a:4);
    AddToTree(T,a);
  end;
  writeln(#10,#13,'Infix Order :');
  PrintTr(T);
  writeln;
  writeln('Hight Tree : ',HightTr(T));
  readln;
end.

Пример создания бинарного дерева и сортировки на языке Java:

// Скомпилируйте и введите java TreeSort
class Tree {
   public Tree left;            // левое и правое поддеревья и ключ
   public Tree right;
   public int key;

   public Tree(int k) {        // конструктор с инициализацией ключа
      key = k;
   }

/*  insert (добавление нового поддерева (ключа))
    сравнить ключ добавляемого поддерева (К) с ключом корневого узла (X).
    Если K>=X, рекурсивно добавить новое дерево в правое поддерево.
    Если K<X, рекурсивно добавить новое дерево в левое поддерево.
    Если поддерева нет, то вставить на это место новое дерево
*/
   public void insert( Tree aTree) {
     if ( aTree.key < key )
        if ( left != null ) left.insert( aTree );
        else left = aTree;
     else
        if ( right != null ) right.insert( aTree );
        else right = aTree;
   }

/*  traverse (обход)
    Рекурсивно обойти левое поддерево.
    Применить функцию f (печать) к корневому узлу.
    Рекурсивно обойти правое поддерево.
*/
   public void traverse(TreeVisitor visitor) {
      if ( left != null) 
            left.traverse( visitor );

      visitor.visit(this);

      if ( right != null ) 
            right.traverse( visitor );
   }
}
interface TreeVisitor {
  public void visit(Tree node);
};

class KeyPrinter  implements TreeVisitor {
  public void visit(Tree node) {
      System.out.println( " " + node.key );
  }
};
class TreeSort {
  public static void main(String args[]) {
     Tree myTree;
     myTree = new Tree( 7 );       // создать дерево (с ключом)
     myTree.insert( new Tree( 5 ) );  // присоединять поддеревья
     myTree.insert( new Tree( 9 ) );
     myTree.traverse(new KeyPrinter());
  }
}