Fiszki do Binarne drzewo poszukiwań
Binarne Drzewo Poszukiwań: Opracowanie dla Studentów Informatyki
Dotknij, aby odwrócić · Przesuń, aby nawigować
Drzewa binarne
14 fiszek
Fiszka 1
Pytanie: Jaka jest kolejność odwiedzania węzłów w przechodzeniu typu post-order?
Odpowiedź: Lewe poddrzewo → Prawe poddrzewo → Węzeł
Fiszka 2
Pytanie: Podaj przykład sekwencji post-order dla drzewa: korzeń 50, lewe dziecko 20, prawe 70. Lewe dziecko 20 ma lewe dziecko 10 i prawe 30. Prawe dziecko 70
Odpowiedź: 10, 30, 20, 60, 80, 70, 50
Fiszka 3
Pytanie: Jakie jest znaczenie wysokości drzewa (`h`) dla wydajności operacji w BST?
Odpowiedź: Wysokość drzewa `h` ma kluczowe znaczenie dla wydajności operacji w BST, ponieważ złożoność czasowa operacji wyszukiwania, wstawiania i usuwania wynos
Fiszka 4
Pytanie: Jaka jest złożoność czasowa operacji w najlepszym przypadku (drzewo wyważone) dla BST?
Odpowiedź: W najlepszym przypadku (drzewo wyważone) wysokość `h` jest proporcjonalna do logarytmu naturalnego z liczby węzłów `n` (`h ≈ log₂ n`), co oznacza, że
Fiszka 5
Pytanie: Co to jest drzewo zdegenerowane i jaki ma wpływ na wydajność operacji w BST?
Odpowiedź: Drzewo zdegenerowane to takie, które przypomina listę liniową (np. gdy elementy są wstawiane w ściśle rosnącej/malejącej kolejności). W tym przypadku
Fiszka 6
Pytanie: Jaki jest cel wyważania drzewa?
Odpowiedź: Celem wyważania drzewa jest modyfikacja jego struktury w taki sposób, aby jego wysokość była jak najmniejsza, zbliżona do `log₂ n`.
Fiszka 7
Pytanie: Jakie specjalne typy BST automatycznie utrzymują równowagę?
Odpowiedź: Drzewa AVL i drzewa czerwono-czarne automatycznie utrzymują równowagę, gwarantując logarytmiczną złożoność czasową.
Fiszka 8
Pytanie: Jaka jest złożoność czasowa operacji wyszukiwania, wstawiania i usuwania w BST?
Odpowiedź: `O(h)`
Fiszka 9
Pytanie: Jaka jest złożoność czasowa przechodzenia drzewa (wszystkie typy) w BST?
Odpowiedź: `O(n)`
Fiszka 10
Pytanie: Jaki jest jeden z częstych błędów studentów dotyczący właściwości BST?
Odpowiedź: Błędne rozumienie właściwości BST, np. mylenie kolejności kluczy w lewym i prawym poddrzewie.