[AdSense-B]
Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока (например, файла, сокета или консоли).
Алгоритм
- Построение двоичного дерева.
- Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.
Эффективность
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка . Соответственно, для n объектов сложность будет составлять
, что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать
, что может привести к общей сложности порядка
.
При физическом развёртывании древовидной структуры в памяти требуется не менее чем ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.
Примеры реализации
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()); } }