Sortiranje binarnog stabla

Sortiranje binarnog stabla je algoritam za sortiranje koji gradi binarno stablo pretrage od elemenata koje je potrebno sortirati, a zatim prolazi kroz stablo tako da na kraju elementi budu sortirani. Najviše se upotrebljava za sortiranje elemenata prilikom učitavanja iz neke datoteke. Nekoliko drugih algoritama sortiranja bi moralo da učita elemente u neku privremenu strukturu, dok kod sortiranja binarnog stabla učitavanje u strukturu podataka već sortira elemente.

Sortiranje binarnog stabla

Klasa	Algoritam sortiranja
Struktura podataka	Niz
Najgora performanca	O(n²) (ne balansirano) O(n log n) (balansirano)
Najbolja performanca	O(n log n)
Prosečna performanca	O(n log n)
Najgora prostorna kompleksnost	Θ(n)

Efikasnost

Dodavanje elemenata u binarno stablo pretrage je prosečno O(log n), što znači da se dodavanje n elemenata izvršava u O(n log n), iz toga sledi da je ovo algoritam brzog sortiranja. Ali dodavanje elemenata u nebalansirajuće binarno stablo je O(n) u najgorem slučaju: kada stablo predstavlja povezanu listu elemenata. U ovom slučaju, najgori slučaj bi dao vreme sortiranja O(n²). Ovaj najgori slučaj se javlja kad algoritam radi na već sortiranom stablu ili na skoro sortiranom stablu. Vreme sortiranja od O(log n) se može postići kad izmešamo niz, ali ovo ne pomaže ako su svi elementi jednaki.

Najgori slučaj se može popraviti koristeći samobalansirajuće binarno stablo pretrage. Koristeći ovakvu vrstu stabla, algoritam ima brzinu O(n log n) u najgorem slučaju. Kada koristimo samobalansirajuće stablo kao binarno stablo pretrage, rezultirajući algoritam ima dodatno svojstvo, a to je adaptivno sortiranje, što znači da radi brže od O(n log n) za elemente koji su skoro sortirani.

Načini sortiranja

1. inorder - ispisuje se levo poddrvo, koren, desno poddrvo
2. preorder - ispisuje koren, levo poddrvo, desno poddrvo
3. postorder - ispisuje se levo poddrvo, desno poddrvo, koren
4. inversorder - ispisuje se desno poddrvo, koren, levo poddrvo

Primer

Sledeći pseudokod algoritma za sortiranje uz pomoć binarnog stabla prima niz uporedivih objekata (elemenata) i ispisuje ih u rastućem poretku:

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

U jednostavnoj formi funkcionalnog programiranja algoritam (u Haskel programskom jeziku) bi izgledao nešto slično sledećem kodu:

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

Treba napomenuti da, u primeru iznad, algoritam umetanja i uklanjanja elemenata imaju vremensku složenost O(n²) u najgorem slučaju.

Literatura

1. Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, knjigu možete pogledati ovde Arhivirano na sajtu Wayback Machine (18. oktobar 2016)
2. Algoritmi i strukture podataka - Milo Tomašević

Spoljašnje veze

• Binary Tree Java Applet and Explanation
• Tree Sort of a Linked List Arhivirano na sajtu Wayback Machine (24. mart 2013)
• Tree Sort in C++ Arhivirano na sajtu Wayback Machine (20. septembar 2013)