Сорт дерева - Tree sort

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

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

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

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

Добавление одного элемента в двоичное дерево поиска занимает в среднем 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 ²) .

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