Сортирање бинарног стабла

Сортирање бинарног стабла је алгоритам за сортирање који гради бинарно стабло претраге од елемената које је потребно сортирати, а затим пролази кроз стабло тако да на крају елементи буду сортирани. Највише се употребљава за сортирање елемената приликом учитавања из неке датотеке. Неколико других алгоритама сортирања би морало да учита елементе у неку привремену структуру, док код сортирања бинарног стабла учитавање у структуру података већ сортира елементе.

Ефикасност Додавање елемената у бинарно стабло претраге је просечно , што значи да се додавање 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) у најгорем случају.

Референце

Литература

Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати овде Алгоритми и структуре података - Мило Томашевић

Спољашње везе -{Binary Tree Java Applet and Explanation}- -{Tree Sort of a Linked List}- -{Tree Sort in C++}-

Категорија:Алгоритми сортирања