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

Из Википедије, слободне енциклопедије
Сортирање бинарног стабла
Binary tree sort(2).png
Класа Алгоритам сортирања
Структура података Низ
Најгора перформанца

O(n²) (не балансирано)

O(n log n) (балансирано)
Најбоља перформанца O(n log n)
Просечна перформанца O(n log n)
Најгора просторна комплексност Θ(n)

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

Ефикасност[уреди]

Додавање елемената у бинарно претраживачком стаблу је 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

У једноставној форми функционалног програмирања алгоритам (у Haskell језику) би изгледао нешто слично следећем коду:

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) у најгорем случају.

Референце[уреди]

Литература[уреди]

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

Спољашње везе[уреди]