Witam,
Mam do rozwiązania takie zadanie:
Zaproponuj algorytm znajdowania bezpośredniego następnika elementu w drzewie BST. Oszacuj koszt tego algorytmu.
Czy rozwiązanie może polegać na tym, że wyszukuję po prostu dany element i wypisuję jego następnik(i) ?
Chodzi mi o jakieś wskazówki.
Za odpowiedzi z góry dziękuję. :)
Zależy od drzewka. Jeśli masz tam wskazania na parenta to możesz iść sobie w górę a potem skręcić w odpowiedniej chwili. Jeśli drzewko jest klasyczne, to zwykły algorytm szukania następnika.
A czy to nie jest tak, że następnikiem elementu x w drzewie BST jest następny element sczytując elementy z drzewa metodą INORDER ?
@Dudson jest, ale inorder-traverse to jest O(n) a szukanie konkretnego węzła to O(logn). Jaki więc sens traversować? ;)
http://qmatica.com/DataStructures/Trees/BST.html
http://people.ksp.sk/~kuko/bak/big/
pobaw się tym ;)