Algorytmy i struktury danych · Junior · Pytanie 51 z 75
Co się stanie, jeśli wstawisz po kolei 1, 2, 3, 4, 5 do prostego BST bez balansowania?
- 1Drzewo samo się zbalansuje
- 2Wstawianie się nie uda, bo wartości muszą być losowe
- ✓Poprawna odpowiedź: Drzewo stanie się łańcuchem, a operacje spadną do O(n)
Wyjaśnienie
Każda nowa wartość jest większa od wszystkich poprzednich i idzie w prawo, więc drzewo zamienia się w listę. Drzewa samobalansujące (AVL, czerwono-czarne) obracają węzły, aby utrzymać wysokość O(log n).