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.[1][2] 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.
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
urediDodavanje 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
uredi- inorder - ispisuje se levo poddrvo, koren, desno poddrvo
- preorder - ispisuje koren, levo poddrvo, desno poddrvo
- postorder - ispisuje se levo poddrvo, desno poddrvo, koren
- inversorder - ispisuje se desno poddrvo, koren, levo poddrvo
Primer
urediSledeć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(n2) u najgorem slučaju.
Reference
uredi- ^ „Sorting algorithms | Martin Broadhurst” (na jeziku: engleski). Arhivirano iz originala 20. 09. 2013. g. Pristupljeno 2020-04-03.
- ^ „Tree Sort - TutorialsPoint.dev”. Tutorialspoint.Dev (na jeziku: engleski). Arhivirano iz originala 25. 01. 2021. g. Pristupljeno 2020-04-03.
Literatura
uredi- 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)
- Algoritmi i strukture podataka - Milo Tomašević
Spoljašnje veze
uredi- 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)