INF.04Algorytmika i Struktury Danych
Binarne Drzewo Poszukiwań (BST)
Hierarchiczna struktura danych, w której każdy węzeł ma co najwyżej dwoje dzieci, a wartości w lewym poddrzewie są mniejsze, zaś w prawym większe od węzła.
Własność BST:
Dla każdego węzła X:
- Wszystkie klucze w lewym poddrzewie są mniejsze od klucza X.
- Wszystkie klucze w prawym poddrzewie są większe od klucza X.
Przechodzenie drzewa (Tree Traversal):
- In-order (L-K-P: lewe, korzeń, prawe): Odwiedza elementy w porządku rosnącym!
- Pre-order (K-L-P: korzeń, lewe, prawe): Najpierw bieżący węzeł, potem dzieci (przydatne do kopiowania drzewa).
- Post-order (L-P-K: lewe, prawe, korzeń): Najpierw dzieci, na końcu węzeł (używane przy usuwaniu drzewa z pamięci).
Złożoność operacji (wyszukiwanie, wstawianie, usuwanie):
- Średnia: O(log n) (dla drzew zrównoważonych, np. AVL, Red-Black Tree).
- Pesymistyczna: O(n) (gdy drzewo zdegeneruje się do listy liniowej).
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Binarne Drzewo Poszukiwań (BST) lub rozpocznij trening.