Dlaczego drzewa wyszukiwania binarnego?

Question

Czytałem drzewo wyszukiwania binarnego i myślałem, że dlaczego potrzebujemy BST w ogóle? Wszystkie rzeczy, o ile wiem, mogą być również osiągnięte przy użyciu prostych uporządkowanych tablic. Dla np. - Aby zbudować BST z n elementami, potrzebujemy czasu n*O(log n), tj. O(nlog n), a czas wyszukiwania to O(log n). Ale można to osiągnąć za pomocą tablicy. Możemy mieć posortowaną tablicę (wymaga czasu O(nlog n)), a czas wyszukiwania w tym jest również O(log n), tj. Wyszukiwanie binarne algo. Dlaczego w ogóle potrzebujemy innej struktury danych? Czy są jakieś inne zastosowania/zastosowania BST, które czynią je tak wyjątkowymi?

--Ravi

Answer 1

Tablice są świetne, jeśli mówisz o napisaniu raz, czytaj wiele razy rodzaj interakcji. Dzieje się tak, gdy przystępujesz do wstawiania, zamiany i usuwania, w których BST naprawdę zaczyna świecić w porównaniu do tablicy. Ponieważ są oparte na węzłach, a nie oparte na ciągłym kawałku pamięci, koszt przeniesienia elementu do kolekcji lub z kolekcji jest szybki, przy jednoczesnym zachowaniu sortowanej natury kolekcji.

Pomyśl o tym, podobnie jak różnicę w wstawianiu między połączonymi listami a tablicami. Jest to nadmierne uproszczenie, ale podkreśla aspekt przewagi, który zauważyłem powyżej.

Answer 2

Co powiecie na posortowany czas wstawiania?

Answer 3

W programowaniu graficznym, jeśli masz rozszerzony obiekt (tj. Który reprezentuje interwał w każdym wymiarze, a nie tylko punkt), możesz dodać je do najmniejszego poziomu drzewa binarnego (zazwyczaj oktree), w którym pasują do siebie w całości.

Jeśli nie obliczysz wstępnie drzewa/listy sortowanej, losowy czas wstawienia (O) na liście może być zbyt długi. Czas wstawiania w drzewie z drugiej strony to tylko O ​​(log (n)).

Answer 4

Wyobraź sobie, że masz tablicę z milionem elementów.

chcesz wstawić element na miejscu 5.

Więc wstaw na końcu tablicy, a następnie sortowania.

Powiedzmy, że tablica jest pełna; to jest O (nlog n), czyli 1 000 000 * 6 = 6 000 000 operacji.

Wyobraź sobie, że masz zbalansowane drzewo.

To jest O (log n), plus bit do równoważenia = 6 + bit, nazywamy to 10 operacjami.

Po prostu wydałeś 6 000 000 operacji sortowania swojej tablicy. Następnie chcesz znaleźć tego elementu. Co robisz? wyszukiwanie binarne - O (log n) - które jest dokładnie tak samo jak to, co zamierzasz zrobić, gdy przeszukasz drzewo!

Teraz wyobraź sobie, że chcesz przydzielić - kolejny element.

Twoja tablica jest pełna! co robisz? ponownie przydzielić tablicę za pomocą n dodatkowych elementów i zapamiętywać tę partię? naprawdę chcesz pamiętać 4mb?

W drzewie wystarczy dodać kolejny element ...