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

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

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

Класа	Алгоритам сортирања
Структура података	Низ
Најгора перформанца	O(n²) (не балансирано) O(n log n) (балансирано)
Најбоља перформанца	O(n log n)
Просечна перформанца	O(n log n)
Најгора просторна комплексност	Θ(n)

Ефикасност

Додавање елемената у бинарно стабло претраге је просечно O(log n), што значи да се додавање n елемената извршава у O(n log n), из тога следи да је ово алгоритам брзог сортирања. Али додавање елемената у небалансирајуће бинарно стабло је O(n) у најгорем случају: када стабло представља повезану листу елемената. У овом случају, најгори случај би дао време сортирања O(n²). Овај најгори случај се јавља кад алгоритам ради на већ сортираном стаблу или на скоро сортираном стаблу. Време сортирања од O(log n) се може постићи кад измешамо низ, али ово не помаже ако су сви елементи једнаки.

Најгори случај се може поправити користећи самобалансирајуће бинарно стабло претраге. Користећи овакву врсту стабла, алгоритам има брзину O(n log n) у најгорем случају. Када користимо самобалансирајуће стабло као бинарно стабло претраге, резултирајући алгоритам има додатно својство, а то је адаптивно сортирање, што значи да ради брже од O(n log n) за елементе који су скоро сортирани.

Начини сортирања

1. inorder - исписује се лево поддрво, корен, десно поддрво
2. preorder - исписује корен, лево поддрво, десно поддрво
3. postorder - исписује се лево поддрво, десно поддрво, корен
4. 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(n²) у најгорем случају.

Литература

1. Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати овде Архивирано на сајту Wayback Machine (18. октобар 2016)
2. Алгоритми и структуре података - Мило Томашевић

Спољашње везе

• Binary Tree Java Applet and Explanation
• Tree Sort of a Linked List Архивирано на сајту Wayback Machine (24. март 2013)
• Tree Sort in C++ Архивирано на сајту Wayback Machine (20. септембар 2013)