Дерево рода является алгоритм сортировки , который строит дерево двоичного поиска из элементов, подлежащих сортировке, а затем обходит дерево ( в-порядке ) , так что элементы выходят в отсортированном порядке. Его типичное использование - сортировка элементов в режиме онлайн : после каждой вставки набор видимых до сих пор элементов становится доступным в отсортированном порядке.
Класс | Алгоритм сортировки |
---|---|
Структура данных | Множество |
Наихудшая производительность | O ( n ²) (несимметричный) O ( n log n ) (сбалансированный) |
Лучшая производительность | O ( n log n ) [ необходима ссылка ] |
Средняя производительность | 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 ) для входных данных, которые почти отсортированы.
Пример
Следующий алгоритм сортировки дерева в псевдокоде принимает набор сопоставимых элементов и выводит элементы в порядке возрастания:
СТРУКТУРА BinaryTree BinaryTree : LeftSubTree Объект : Node BinaryTree : RightSubTree ПРОЦЕДУРА Insert ( BinaryTree : searchTree , Object : item ) ЕСЛИ searchTree . Node IS NULL THEN SET searchTree . Узел В пункте ELSE IF пункт IS МЕНЬШЕ , ЧЕМ searchTree . Узел THEN Insert ( searchTree . LeftSubTree , элемент ) ELSE Insert ( searchTree . RightSubTree , элемент ) ПРОЦЕДУРА InOrder ( BinaryTree : searchTree ) ЕСЛИ searchTree . Узел ЕСТЬ NULL ТОГДА ВЫЙТИ ПРОЦЕДУРА ELSE InOrder ( searchTree . LeftSubTree ) EMIT searchTree . Узел InOrder ( searchTree . RightSubTree ) ПРОЦЕДУРА TreeSort ( Коллекция : элементы ) BinaryTree : searchTree ДЛЯ КАЖДОЙ individualItem В элементов Вставка ( searchTree , individualItem ) InOrder ( searchTree )
В простой форме функционального программирования алгоритм (в Haskell ) будет выглядеть примерно так:
дерево данных a = Leaf | Узел ( Дерево a ) a ( Дерево a ) insert :: Ord a => a -> Tree a -> Tree a insert x Leaf = Node Leaf x Leaf insert x ( Узел t y s ) | x <= y = Узел ( вставить x t ) y s | x > y = узел t y ( вставить x s ) flatten :: Tree a -> [ a ] flatten Leaf = [] flatten ( Node t x s ) = flatten t ++ [ x ] ++ сгладить s Treesort :: Ord => [ ] -> [ ] Treesort = Flatten . складная вставка Leaf
В приведенной выше реализации и алгоритм вставки, и алгоритм поиска имеют наихудшие сценарии O ( n ²) .
Внешние ссылки
- Java-апплет двоичного дерева и объяснение на Wayback Machine (архивировано 29 ноября 2016 г.)
- Древовидная сортировка связанного списка
- Сортировка дерева в C ++