Сортирање бинарног стабла
![]() | |
Класа | Алгоритам сортирања |
---|---|
Структура података | Низ |
Најгора перформанца | O(n²) (не балансирано) O(n log n) (балансирано) |
Најбоља перформанца | O(n log n) |
Просечна перформанца | O(n log n) |
Најгора просторна комплексност | Θ(n) |
Сортирање бинарног стабла је алгоритам за сортирање који гради бинарно стабло претраге од елемената које је потребно сортирати, а затим пролази кроз стабло тако да на крају елементи буду сортирани.[1][2] Највише се употребљава за сортирање елемената приликом учитавања из неке датотеке. Неколико других алгоритама сортирања би морало да учита елементе у неку привремену структуру, док код сортирања бинарног стабла учитавање у структуру података већ сортира елементе.
Ефикасност
[уреди | уреди извор]Додавање елемената у бинарно стабло претраге је просечно O(log n), што значи да се додавање n елемената извршава у O(n log n), из тога следи да је ово алгоритам брзог сортирања. Али додавање елемената у небалансирајуће бинарно стабло је O(n) у најгорем случају: када стабло представља повезану листу елемената. У овом случају, најгори случај би дао време сортирања O(n²). Овај најгори случај се јавља кад алгоритам ради на већ сортираном стаблу или на скоро сортираном стаблу. Време сортирања од O(log n) се може постићи кад измешамо низ, али ово не помаже ако су сви елементи једнаки.
Најгори случај се може поправити користећи самобалансирајуће бинарно стабло претраге. Користећи овакву врсту стабла, алгоритам има брзину O(n log n) у најгорем случају. Када користимо самобалансирајуће стабло као бинарно стабло претраге, резултирајући алгоритам има додатно својство, а то је адаптивно сортирање, што значи да ради брже од O(n log n) за елементе који су скоро сортирани.
Начини сортирања
[уреди | уреди извор]- inorder - исписује се лево поддрво, корен, десно поддрво
- preorder - исписује корен, лево поддрво, десно поддрво
- postorder - исписује се лево поддрво, десно поддрво, корен
- inversorder - исписује се десно поддрво, корен, лево поддрво
Пример
[уреди | уреди извор]Следећи псеудокод алгоритма за сортирање уз помоћ бинарног стабла прима низ упоредивих објеката (елемената) и исписује их у растућем поретку:
STRUCTURE BinaryTree
BinaryTree:LeftSubTree
Object:Node
BinaryTree:RightSubTree
END STRUCTURE
PROCEDURE Insert(BinaryTree:searchTree, Object:item)
IF searchTree 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)
END IF
END IF
END PROCEDURE
PROCEDURE InOrder(BinaryTree:searchTree)
IF searchTree IS NULL THEN
EXIT PROCEDURE
ELSE
InOrder(searchTree.LeftSubTree)
PRINT searchTree.Node
InOrder(searchTree.RightSubTree)
END IF
END PROCEDURE
PROCEDURE TreeSort(Array:items)
BinaryTree:searchTree
FOR EACH individualItem IN items
Insert(searchTree, individualItem)
END FOR
InOrder(searchTree)
END PROCEDURE
У једноставној форми функционалног програмирања алгоритам (у Haskеl програмском језику) би изгледао нешто слично следећем коду:
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
insert x (Node 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 . foldеr insert Leaf
Треба напоменути да, у примеру изнад, алгоритам уметања и уклањања елемената имају временску сложеност O(n2) у најгорем случају.
Референце
[уреди | уреди извор]- ^ „Sorting algorithms | Martin Broadhurst” (на језику: енглески). Архивирано из оригинала 20. 09. 2013. г. Приступљено 2020-04-03.
- ^ „Tree Sort - TutorialsPoint.dev”. Tutorialspoint.Dev (на језику: енглески). Архивирано из оригинала 25. 01. 2021. г. Приступљено 2020-04-03.
Литература
[уреди | уреди извор]- Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати овде Архивирано на сајту Wayback Machine (18. октобар 2016)
- Алгоритми и структуре података - Мило Томашевић
Спољашње везе
[уреди | уреди извор]- Binary Tree Java Applet and Explanation
- Tree Sort of a Linked List Архивирано на сајту Wayback Machine (24. март 2013)
- Tree Sort in C++ Архивирано на сајту Wayback Machine (20. септембар 2013)