Сортировка дерева

Сортировка дерева

Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	O ( n² ) (несбалансированный) O ( n log n ) (сбалансированный)
Лучшая производительность	О ( п журнал п )
Средняя производительность	О ( п журнал п )
Наихудшая пространственная сложность	Θ( п )
Оптимальный	Да, если сбалансировано

Сортировка дерева — это алгоритм сортировки , который строит двоичное дерево поиска из элементов, подлежащих сортировке, а затем обходит дерево ( по порядку ), чтобы элементы выходили в отсортированном порядке. Его типичное использование — сортировка элементов онлайн : после каждой вставки набор видимых на данный момент элементов доступен в отсортированном порядке.

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

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

Добавление одного элемента в двоичное дерево поиска в среднем занимает процесс O (log n ) (в большой записи O ). Добавление n элементов — это процесс O ( n log n ) , что делает сортировку дерева процессом «быстрой сортировки». Добавление элемента в несбалансированное двоичное дерево требует времени O ( n ) в худшем случае: когда дерево напоминает связанный список ( вырожденное дерево ). Это приводит к тому, что в худшем случае время для этого алгоритма сортировки составит O ( n ²) . Этот худший случай возникает, когда алгоритм работает с уже отсортированным набором или с набором, который почти отсортирован, перевернут или почти перевернут. Однако ожидаемое время O ( n log n ) может быть достигнуто путем перетасовки массива, но это не помогает для одинаковых элементов.

В худшем случае поведение можно улучшить, используя самобалансирующееся двоичное дерево поиска . Используя такое дерево, алгоритм имеет производительность O ( n log n ) в худшем случае, что делает его оптимальным по степени для сортировки сравнением . Однако алгоритмы сортировки дерева требуют выделения отдельной памяти для дерева, в отличие от алгоритмов на месте, таких как быстрая сортировка или пирамидальная сортировка . На большинстве распространенных платформ это означает, что динамическую память необходимо использовать , что значительно снижает производительность по сравнению с быстрой сортировкой и пирамидальной сортировкой. . При использовании дерева расширения в качестве двоичного дерева поиска полученный алгоритм (называемый splaysort ) обладает дополнительным свойством адаптивной сортировки , а это означает, что время его работы быстрее, чем O ( n log n ) для входных данных, которые почти отсортированы.

Пример

Следующий алгоритм сортировки дерева в псевдокоде принимает коллекцию сопоставимых элементов и выводит элементы в порядке возрастания:

 STRUCTURE BinaryTree
     BinaryTree:LeftSubTree
     Object:Node
     BinaryTree:RightSubTree
 
 PROCEDURE Insert(BinaryTree:searchTree, Object:item)
     IF searchTree.Node IS NULL THEN
         SET searchTree.Node TO item
     ELSE
         IF item IS LESS THAN searchTree.Node THEN
             Insert(searchTree.LeftSubTree, item)
         ELSE
             Insert(searchTree.RightSubTree, item)
 
 PROCEDURE InOrder(BinaryTree:searchTree)
     IF searchTree.Node IS NULL THEN
         EXIT PROCEDURE
     ELSE
         InOrder(searchTree.LeftSubTree)
         EMIT searchTree.Node
         InOrder(searchTree.RightSubTree)
 
 PROCEDURE TreeSort(Collection:items)
     BinaryTree:searchTree
    
     FOR EACH individualItem IN items
         Insert(searchTree, individualItem)
    
     InOrder(searchTree)

В простой форме функционального программирования алгоритм (на 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 s)
     | x <= y = Node (insert x t) y s
     | x > y  = Node t y (insert x s)

 flatten :: Tree a -> [a]
 flatten Leaf = []
 flatten (Node t x s) = flatten t ++ [x] ++ flatten s

 treesort :: Ord a => [a] -> [a]
 treesort = flatten . foldr insert Leaf

В приведенной выше реализации и алгоритм вставки, и алгоритм извлечения имеют O ( n ²) наихудших сценариев.

Внешние ссылки

• Java-апплет двоичного дерева и пояснения на Wayback Machine (архивировано 29 ноября 2016 г.)
• Древовидная сортировка связанного списка
• Древовидная сортировка в C++