Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока (например, файла, сокета или консоли).
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O ( l o g ( n ) ) {displaystyle O(log(n))} . Соответственно, для n объектов сложность будет составлять O ( n l o g ( n ) ) {displaystyle O(n,log(n))} , что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать O ( n ) {displaystyle O(n)} , что может привести к общей сложности порядка O ( n 2 ) {displaystyle O(n^{2})} .
При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4 n {displaystyle 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 <= y = Node (insert x t) y t' 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
Реализация на C++14:
#include <memory> #include <cassert> #include <algorithm> #include <vector> #include <iostream> using namespace std; // класс, представляющий бинарное дерево class BinaryTree { protected: // узел бинарного дерева struct BinaryTreeNode { shared_ptr<BinaryTreeNode> left, right; // левое и правое поддерево int key; // ключ }; shared_ptr<BinaryTreeNode> m_root; // корень дерева protected: // рекурсивная процедура вставки ключа // cur_node — текущий узел дерева, с которым сравнивается вставляемый узел // node_to_insert — вставляемый узел void insert_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const shared_ptr<BinaryTreeNode>& node_to_insert) { assert(cur_node != nullptr); // сравнение bool insertIsLess = node_to_insert->key < cur_node->key; if(insertIsLess) { // вставка в левое поддерево if(cur_node->left == nullptr) cur_node->left = node_to_insert; else insert_recursive(cur_node->left, node_to_insert); } else { // вставка в правое поддерево if(cur_node->right == nullptr) cur_node->right = node_to_insert; else insert_recursive(cur_node->right, node_to_insert); } } public: void insert(int key) { shared_ptr<BinaryTreeNode> node_to_insert(new BinaryTreeNode); node_to_insert->key = key; if(m_root == nullptr) { m_root = node_to_insert; return; } insert_recursive(m_root, node_to_insert); } public: typedef function<void(int key)> Visitor; protected: // рекурсивная процедура обхода дерева // cur_node — посещаемый в данный момент узел void visit_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const Visitor& visitor) { assert(cur_node != nullptr); // сначала посещаем левое поддерево if(cur_node->left != nullptr) visit_recursive(cur_node->left, visitor); // посещаем текущий элемент visitor(cur_node->key); // посещаем правое поддерево if(cur_node->right != nullptr) visit_recursive(cur_node->right, visitor); } public: void visit(const Visitor& visitor) { if(m_root == nullptr) return; visit_recursive(m_root, visitor); } }; int main() { BinaryTree tree; // добавление элементов в дерево vector<int> data_to_sort = {10, 2, 7, 3, 14, 7, 32}; for(int value : data_to_sort) { tree.insert(value); } // обход дерева tree.visit([](int visited_key) { cout<<visited_key<<" "; }); cout<<endl; // результат выполнения: 2 3 7 7 10 14 32 return 0; }
Пример создания бинарного дерева и сортировки на языке 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()); } }
Читайте также
Почему женщины так любят, когда им дарят розы
Веками розы считались символом любви и красоты. И нет ничего
Идеальное сочетание стиля и качества: CROCOTARI — сумки и рюкзаки из натуральной и эко кожи
В мире моды всегда ценятся предметы, которые сочетают в себе
Преимущества аренды зала для проведения дня рождения
Большие светодиодные экраны и видеостены: эффективный способ привлечения внимания
Отдых на Мальдивах: релаксация в раю
Как сделать Декларацию соответствия на обувь?
Практически любая обувь, попадающая на прилавки магазинов, предварительно проходит обязательную
Для ведения определённых видов деятельности, компаниям необходимо получать лицензию. Самостоятельно
Барная карта: навигатор для вашего гостя
Барная карта – ключевой элемент любого заведения, где должное внимание
Особенности лечения молочных зубов
Родители редко приводят к стоматологам детей с проблемами молочных зубов.
Сатин: особенности, применение и уход
Сатин — одна из популярных и востребованных тканей на рынке
Шопинг-антистресс: интернет-магазин брендовой одежды VIPAVENUE
Как восстановить работу пылесоса
Пылесос – незаменимый помощник в борьбе с пылью и грязью
Как Лила (древняя индийская игра) помогает решать жизненные проблемы
Mocheqi Musk — бренд профессиональной косметики для волос
Mocheqi Musk (Мачеки Маск) — это бренд профессиональной косметики, специализирующийся
Закодироваться от курения: новые методы борьбы со вредной привычкой
Курение является одной из самых распространенных и опасных привычек современного