Сортировка с помощью двоичного дерева — Pascal(Паскаль)
Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. 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 /* 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()); >>
Похожие записи/страницы:
Источник
Сортировка с помощью двоичного дерева
Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort ) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например с файла, сокета или консоли).
Алгоритм
1. Построение двоичного дерева.
2. Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.
Эффективность
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)). Соответственно, для n объектов сложность будет составлять O(n log(n)), что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n), что может привести к общей сложности порядка O(n²).
При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.
Примеры реализации
В простой форме функционального программирования на Haskell данный алгоритм будет выглядеть так:
data Tree a = Leaf | Node (Tree a) a (Tree a) insert :: Ord a => a -> Tree a -> Tree a insert x Leaf = Node Leaf x Leaf insert x (Node t y t') | x insert x (Node t y t') | x > y = Node t y (insert x t') flatten :: Tree a -> [a] flatten Leaf = [] flatten (Node t x t') = flatten t ++ [x] ++ flatten t' treesort :: Ord a => [a] -> [a] treesort = flatten . foldr insert Leaf
#include #include #include template typename Iterator> void binary_tree_sort(Iterator begin, Iterator end) std::multisettypename std::iterator_traitsIterator>::value_type> tree(begin, end); std::copy(tree.begin(), tree.end(), begin); >; Пример создания бинарного дерева и сортировки на языке 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 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 ); > >; public 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()); > >
См. также
Источник
Анализ алгоритма сортировки бинарным деревом поиска
Первая мысль, которая возникает при начальном знакомстве с этим методом — сильная зависимость структуры дерева от входных данных. Если данные абсолютно случайны (например, массив формировался при помощи датчика случайных чисел), то дерево получится достаточно плотным, как на рисунке 4.5. При построении такого дерева можно значительно выиграть во времени на сокращении количества сравнений при поиске места для каждого нового листа. В самом лучшем случае потребуется log2n сравнений на каждый добавляемый элемент, следовательно, временная сложность построения дерева из n элементов составит O(nlogn).
Но если входная последовательность уже была отсортирована, то дерево выродится в линейный список (перемещаясь по дереву, будем двигаться все время по одной ветви). Сам процесс построения вырожденного дерева потребует столько же времени, сколько и простые методы сортировки — O(n 2 ). Для того, чтобы исключить возможность получения вырожденного дерева или дерева с низкой плотностью, можно хорошенько «перемешать» исходные данные перед тем, как их сортировать, но на это опять потребуется лишнее время.
Такое поведение алгоритма следует оценить как неестественное. Устойчивости также нет. Есть и еще один крупный недостаток этого метода — большие требования к памяти под дерево. Кроме места под значения элементов требуется память на 2 указателя для каждого из них.
В силу этих недостатков данный способ не находит практического применения в тех случаях, когда требуется просто отсортировать массив или список в оперативной памяти. Но не нужно забывать, что основное назначение бинарного дерева поиска — быстрый поиск данных. Поэтому, если бинарное дерево поиска строилось непосредственно при считывании данных с диска, чтобы затем использовать его для задач поиска, то это наилучший способ получить данные в отсортированном виде.
Подробно реализацию бинарного дерева поиска рассмотрим в следующей главе. Наибольшего внимания из древовидных методов заслуживает пирамидальная сортировка, поэтому рассмотрим ее подробнее.
4.3.2. Пирамидальная сортировка
В алгоритме пирамидальной сортировки используется специальная структура данных — пирамида (иногда её также называют кучей, англ. heap). Пирамидой называется двоичное дерево, в вершинах которого размещаются заданные нам элементы. При этом должны выполняться следующие требования:
- все уровни, за исключением последнего, должны быть заполнены полностью
- последний уровень (т.е. уровень листьев дерева) может быть заполнен частично, но обязательно слева направо без пропусков
- основное свойство пирамиды: ни один элемент в пирамиде не может быть больше своего родителя
Очевидно, что на вершине пирамиды находится наибольший её элемент.
Для представления пирамиды в памяти удобно использовать массив, при этом пирамида хранится в массиве следующим образом. Сыновья элемента с индексом i будут иметь индексы i*2+1 и i*2+2, а его родитель — индекс (i-1)/2 (напомним, что в языке C++ массивы начинаются с нуля, а при делении двух целых чисел дробная часть отбрасывается). Так, для вышеприведённого рисунка пирамида будет храниться в массиве следующим образом:
Источник