Drzewo binarne wyszukiwań (BST)

1. Czym jest BST?

BST (Binary Search Tree) to drzewo binarne z specjalną właściwością dotyczącą uporządkowania:

Właściwość BST:

Dla każdego węzła: - Lewa poddrzewo zawiera wartości mniejsze - Prawa poddrzewo zawiera wartości większe

Wizualizacja:

        10
       /  \
      5    15
     / \   / \
    3   7 12  20

✅ To jest BST:
- Lewa od 10: {5, 3, 7} < 10
- Prawa od 10: {15, 12, 20} > 10
- Lewa od 5: {3} < 5
- Prawa od 5: {7} > 5

        10
       /  \
      15   5

❌ To NIE jest BST:
- 15 > 10 ale jest po lewej!

2. Implementacja węzła BST

3. Wstawianie do BST

3.1. Algorytm:

Jeśli drzewo puste → nowy węzeł staje się korzeniem
Porównaj z obecnym węzłem:
Jeśli mniejszy → idź w lewo
Jeśli większy → idź w prawo
Powtarzaj aż znajdziesz puste miejsce

3.2. Implementacja rekurencyjna:

3.3. Implementacja iteracyjna:

3.4. Wizualizacja wstawiania:

Wstaw: [10, 5, 15, 3, 7]

Krok 1: Wstaw 10
    10

Krok 2: Wstaw 5 (5 < 10 → lewo)
    10
   /
  5

Krok 3: Wstaw 15 (15 > 10 → prawo)
    10
   /  \
  5    15

Krok 4: Wstaw 3 (3 < 10 → lewo, 3 < 5 → lewo)
      10
     /  \
    5    15
   /
  3

Krok 5: Wstaw 7 (7 < 10 → lewo, 7 > 5 → prawo)
      10
     /  \
    5    15
   / \
  3   7

4. Wyszukiwanie w BST

4.1. Algorytm:

Porównaj z obecnym węzłem:
Jeśli równy → znaleziono!
Jeśli mniejszy → szukaj w lewym poddrzewie
Jeśli większy → szukaj w prawym poddrzewie
Powtarzaj

4.2. Implementacja rekurencyjna:

4.3. Implementacja iteracyjna:

4.4. Znajdowanie węzła:

5. Minimum i maksimum w BST

5.1. Minimum – najbardziej lewy węzeł:

5.2. Maksimum – najbardziej prawy węzeł:

5.3. Minimum/maksimum w poddrzewie:

6. Usuwanie z BST

6.1. Trzy przypadki:

Przypadek 1: Liść (bez dzieci)

      10              10
     /  \            /  \
    5    15    →    5    15
   / \             /
  3   7           3

Usuń 7 – po prostu usuń węzeł

Przypadek 2: Jeden potomek

      10              10
     /  \            /  \
    5    15    →    3    15
   /
  3

Usuń 5 – zastąp rodzicem dziecka (3)

Przypadek 3: Dwoje dzieci

      10              10
     /  \            /  \
    5    15    →    7    15
   / \   /         /     /
  3   7 12        3     12

Usuń 5 – zastąp następnikiem (7 = min z prawego poddrzewa)

6.2. Implementacja:

6.3. Alternatywna strategia – poprzednik:

7. Przechodzenie BST (In-Order)

In-order dla BST daje posortowaną kolejność!

8. Sprawdzanie poprawności BST

9. Wysokość BST

10. Zliczanie węzłów

11. Następnik i poprzednik

11.1. Następnik (successor):

11.2. Poprzednik (predecessor):

12. Zakres wartości (Range Query)

13. k-ty najmniejszy element

14. Złożoność operacji BST

14.1. Dla zbalansowanego BST:

Operacja	Złożoność czasowa
Wyszukiwanie	O(log n) ✅
Wstawianie	O(log n) ✅
Usuwanie	O(log n) ✅
Minimum/Max	O(log n)
In-order	O(n)

Wysokość: O(log n)

14.2. Dla zdegenerowanego BST (jak lista):

Operacja	Złożoność czasowa
Wyszukiwanie	O(n) ❌
Wstawianie	O(n) ❌
Usuwanie	O(n) ❌

Wysokość: O(n) – jak lista!

14.3. Złożoność pamięciowa:

BST: O(n) – przechowuje n węzłów
Rekurencja: O(h) – głębokość stosu, gdzie h = wysokość

15. Wizualizacja BST

Wynik:

`-- 10
    |-- 5
    |   |-- 3
    |   |   |-- None
    |   |   `-- None
    |   `-- 7
    |       |-- None
    |       `-- None
    `-- 15
        |-- 12
        |   |-- None
        |   `-- None
        `-- 20
            |-- None
            `-- None

16. Zastosowania BST

16.1. Dynamiczny zbiór z szybkim wyszukiwaniem

16.2. Sortowanie (Tree Sort)

Złożoność: O(n log n) średnio, O(n²) najgorszy (zdegenerowane)

16.3. Słowniki i mapy

17. Porównanie z innymi strukturami

17.1. BST vs tablica posortowana:

Operacja	BST (zbal.)	Tablica posort.
Wyszukiwanie	O(log n)	O(log n) ✅
Wstawianie	O(log n) ✅	O(n)
Usuwanie	O(log n) ✅	O(n)
Min/Max	O(log n)	O(1) ✅

BST lepsze dla częstych wstawień/usunięć.

17.2. BST vs tablica haszująca:

Operacja	BST (zbal.)	Hash Table
Wyszukiwanie	O(log n)	O(1) ✅
Wstawianie	O(log n)	O(1) ✅
Usuwanie	O(log n)	O(1) ✅
Uporządkowanie	TAK ✅	NIE
Range Query	TAK ✅	NIE

BST lepsze gdy potrzebna jest kolejność lub zapytania zakresowe.

18. Podsumowanie

BST (Binary Search Tree):

Drzewo binarne z właściwością uporządkowania
Lewa < Środek < Prawa
Zbalansowane: O(log n) dla operacji ✅
Zdegenerowane: O(n) – jak lista ❌

Operacje:

Operacja	Zbalansowane	Zdegenerowane
Wyszukiwanie	O(log n) ✅	O(n) ❌
Wstawianie	O(log n) ✅	O(n) ❌
Usuwanie	O(log n) ✅	O(n) ❌
Min/Max	O(log n)	O(n)
In-order	O(n)	O(n)

Zalety: - Efektywne wyszukiwanie/wstawianie/usuwanie (dla zbalansowanych) - In-order daje posortowaną kolejność ✅ - Dynamiczna struktura (elastyczny rozmiar) - Naturalne dla danych hierarchicznych

Wady: - Może zdegenerować do listy O(n) ❌ - Wymaga balansowania dla gwarantowanej wydajności - Bardziej złożone niż tablice - Większy narzut pamięci (wskaźniki)

Kiedy używać: - ✅ Częste wyszukiwania, wstawiania, usunięcia - ✅ Potrzebna jest kolejność (sortowanie) - ✅ Zapytania zakresowe (range queries) - ✅ Dynamiczny rozmiar danych

Kiedy NIE używać: - ❌ Dane niewielkie (tablica prostsza) - ❌ Tylko wyszukiwanie (tablica haszująca O(1)) - ❌ Brak gwarancji balansowania (użyj AVL/Red-Black)

Kluczowa obserwacja:

Co dalej warto poznać:

Przechodzenie drzew – in-order, pre-order, post-order, BFS
Drzewa AVL – samobalansujące BST, gwarantowane O(log n)
Drzewa Red-Black – alternatywne balansowanie
B-drzewa – dla baz danych i systemów plików
Kopce binarne – dla kolejek priorytetowych