Biorąc pod uwagę zestaw danych w drzewie wyszukiwania binarnego, jak liczby od 1 do 10, możliwe jest istnienie wielu zbalansowanych drzewek wyszukiwania binarnego?Czy jest możliwe posiadanie wielu ważnych BST dla danego zestawu danych?
Czy jest tylko jeden, unikalny zrównoważony BST dla tego zestawu danych?
Dzięki
Wszystko zależy od konkretnego binarnej strukturze danych drzewo używany algorytm wstawiania kryteria bilansowania i kolejność wkładania, ale tak - to możliwe, aby mieć wiele odpowiednik i ważny BSTS zbilansowane pod kątem podana sekwencja wartości.
Na przykład, to ważne Red/Black Tree gdzie liczby 1-10 zamieszczono w porządku rosnącym:
Z drugiej strony jest ważne AVL Tree, gdzie liczby 1-10 wstawiono dokładnie w takiej samej kolejności jak w czerwony/czarny Drzewo:
oczywiste jest, że drzewa nie są dokładnie takie same - ale porządkuje d właściwości bilansowania utrzymują się dla obu.
Więc powiedzmy, że korzystałem z drzewa AVL, czy byłoby wiele drzewek AVL dla tego samego zestawu liczb? Jeśli tak, czy kolejność wstawiania akcji powoduje powstanie tych różnych drzew? – user2305684
@ user2305684 jeśli ograniczymy drzewo do konkretnej implementacji, tak, nadal możemy uzyskać różne wyniki w zależności od kolejności wstawień. Ale możemy być pewni, że jeśli elementy zostaną wstawione w tej samej kolejności dla tej samej struktury danych i algorytmu, wynikowe drzewo będzie takie samo –