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

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

Тип алгоритма сортировки

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

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

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

Добавление одного элемента в бинарное дерево поиска в среднем является процессом $O (log n)$ (в нотации big 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 Объект : Узел BinaryTree : RightSubTree ПРОЦЕДУРА Вставить ( BinaryTree : searchTree , Объект : элемент ) ЕСЛИ searchTree . Node ЕСТЬ NULL ТО УСТАНОВИТЬ searchTree . Node К элементу ИНАЧЕ ЕСЛИ элемент МЕНЬШЕ searchTree . Node ТО Вставить ( searchTree . LeftSubTree , элемент ) ИНАЧЕ Вставить ( searchTree . RightSubTree , элемент ) ПРОЦЕДУРА InOrder ( BinaryTree : searchTree ) ЕСЛИ searchTree . Node ЕСТЬ NULL ТО ВЫЙТИ ИЗ ПРОЦЕДУРЫ ИНАЧЕ InOrder ( searchTree . LeftSubTree ) ВЫДАТЬ searchTree . Узел InOrder ( searchTree . RightSubTree ) ПРОЦЕДУРА TreeSort ( Коллекция : элементы ) BinaryTree : searchTree ДЛЯ КАЖДОГО отдельного элемента IN элементы Вставить ( searchTree , individualItem ) InOrder ( searchTree )

В простой форме функционального программирования алгоритм (на языке Haskell ) будет выглядеть примерно так:

 данные Дерево a = Лист | Узел ( Дерево a ) a ( Дерево a )            вставка :: Ord a => a -> Дерево a -> Дерево a вставка x Лист = Узел Лист x Лист вставка x ( Узел t y s ) | x <= y = Узел ( вставка x t ) y s | x > y = Узел t y ( вставка x s )                                                выравнивание :: Дерево a -> [ a ] выравнивание Лист = [] выравнивание ( Узел t x s ) = выравнивание t ++ [ x ] ++ выравнивание s                       Treesort :: Ord a => [ a ] -> [ a ] Treesort = Flatten . папка вставка Лист

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

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

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

Ссылки

^ Маклаки, Кит; Барбер, Ангус (1986). "Сортировка двоичного дерева". Сортировочные процедуры для микрокомпьютеров . Basingstoke: Macmillan. ISBN 0-333-39587-5. OCLC 12751343.

[McLuckie_Barber_p.-1] Маклаки, Кит; Барбер, Ангус (1986). "Сортировка двоичного дерева". Сортировочные процедуры для микрокомпьютеров . Basingstoke: Macmillan. ISBN 0-333-39587-5. OCLC 12751343.