Drzewa AVL - wprowadzenie do balansowania

1. Problem ze zwykłym BST

1.1. BST może degenerować:

1.2. Zbalansowane BST:

Problem: Jak automatycznie utrzymać balans?

2. Czym jest drzewo AVL?

AVL Tree to samobalansujące drzewo BST wynalezione przez Adelson-Velsky i Landis (1962).

2.1. Warunek AVL:

Dla każdego węzła:

|wysokość(lewe) - wysokość(prawe)| ≤ 1

Balance Factor (BF) = wysokość(lewe) - wysokość(prawe)

Dozwolone wartości BF: -1, 0, 1

2.2. Przykłady:

✅ To jest AVL (BF ∈ {-1, 0, 1}):

        10 (BF=0)
       /  \
      5    15 (BF=0)
     / \
    3   7

BF(10) = height(5) - height(15) = 2 - 1 = 1 ✅
BF(5) = height(3) - height(7) = 0 - 0 = 0 ✅
BF(15) = 0 - 0 = 0 ✅

❌ To NIE jest AVL (BF = 2):

      10 (BF=2)
     /
    5
   /
  3

BF(10) = 2 - 0 = 2 ❌ (|BF| > 1)

3. Implementacja węzła AVL

4. Rotacje – podstawa balansowania

Gdy BF staje się > 1 lub < -1, wykonujemy rotacje.

4.1. Rotacja w prawo (Right Rotation):

     y                    x
    / \                  / \
   x   C     →          A   y
  / \       Right           / \
 A   B      Rotation       B   C

Używana gdy: BF(y) > 1 (lewe ciężkie)

4.2. Implementacja rotacji w prawo:

4.3. Rotacja w lewo (Left Rotation):

   x                      y
  / \                    / \
 A   y       →          x   C
    / \     Left       / \
   B   C   Rotation   A   B

Używana gdy: BF(x) < -1 (prawe ciężkie)

4.4. Implementacja rotacji w lewo:

5. Cztery przypadki niezbalansowania

5.1. Case 1: Left-Left (LL) – Rotacja w prawo

     30 (BF=2)          20
    /                  /  \
   20        →        10   30
  /         Right
 10        Rotation

Warunek: BF(node) > 1 AND BF(node.left) ≥ 0

Naprawa: Jedna rotacja w prawo

5.2. Case 2: Right-Right (RR) – Rotacja w lewo

 10 (BF=-2)           20
   \                 /  \
    20      →       10   30
     \     Left
      30   Rotation

Warunek: BF(node) < -1 AND BF(node.right) ≤ 0

Naprawa: Jedna rotacja w lewo

5.3. Case 3: Left-Right (LR) – Podwójna rotacja

     30 (BF=2)         30              20
    /                 /               /  \
   10        →       20      →       10   30
     \     Left     /       Right
      20   Rotation 10     Rotation

Warunek: BF(node) > 1 AND BF(node.left) < 0

Naprawa: 1. Rotacja w lewo na lewym dziecku 2. Rotacja w prawo na węźle

5.4. Case 4: Right-Left (RL) – Podwójna rotacja

 10 (BF=-2)         10                20
   \                  \              /  \
    30      →          20     →     10   30
   /       Right        \    Left
  20      Rotation       30  Rotation

Warunek: BF(node) < -1 AND BF(node.right) > 0

Naprawa: 1. Rotacja w prawo na prawym dziecku 2. Rotacja w lewo na węźle

6. Balansowanie węzła

7. Wstawianie do AVL

7.1. Wizualizacja wstawiania:

Wstaw: [10, 20, 30]

Krok 1: Wstaw 10
    10

Krok 2: Wstaw 20
    10
      \
       20

Krok 3: Wstaw 30
    10 (BF=-2)
      \
       20
         \
          30

❌ Niezbalansowane! RR case

Rotacja w lewo na 10:
      20
     /  \
    10   30

✅ Zbalansowane!

Końcowe AVL:
      20
     /  \
    10   30

8. Usuwanie z AVL

9. Wyszukiwanie w AVL

10. Przykład kompletny

11. Wizualizacja AVL

Przykładowy wynik:

`-- 30 (h=2, BF=0)
    |-- 20 (h=1, BF=0)
    |   |-- 10 (h=0, BF=0)
    |   |   |-- None
    |   |   `-- None
    |   `-- 25 (h=0, BF=0)
    |       |-- None
    |       `-- None
    `-- 50 (h=0, BF=0)
        |-- None
        `-- None

12. Złożoność operacji AVL

12.1. Gwarantowana złożoność:

Operacja	AVL Tree	BST (zbal.)	BST (najgorszy)
Wyszukiwanie	O(log n) ✅	O(log n)	O(n) ❌
Wstawianie	O(log n) ✅	O(log n)	O(n) ❌
Usuwanie	O(log n) ✅	O(log n)	O(n) ❌
Wysokość	O(log n) ✅	O(log n)	O(n) ❌

AVL gwarantuje O(log n) – nawet w najgorszym przypadku!

12.2. Analiza wysokości:

Dla n węzłów, wysokość AVL:

h ≤ 1.44 × log₂(n)

Przykłady: - n = 1000 → h ≤ 14 - n = 1 000 000 → h ≤ 29

13. Liczba rotacji

13.1. Przy wstawianiu:

Maksymalnie 1 rotacja (pojedyncza lub podwójna)!

13.2. Przy usuwaniu:

Maksymalnie O(log n) rotacji (w ścieżce do korzenia).

14. AVL vs zwykły BST

15. Zastosowania AVL

15.1. Bazy danych – indeksy

AVL do indeksowania kolumn w bazach danych:
- Gwarantowane O(log n) wyszukiwanie
- Efektywne range queries

15.2. Systemy plików

Organizacja katalogów i plików:
- Szybki dostęp do plików
- Dynamiczne dodawanie/usuwanie

15.3. Słowniki z gwarancją wydajności

16. Porównanie AVL z innymi strukturami

16.1. AVL vs Red-Black Tree:

Aspekt	AVL Tree	Red-Black Tree
Balansowanie	Bardziej rygorystyczne	Luźniejsze
Wysokość	~1.44 log n	~2 log n
Wyszukiwanie	Szybsze ✅	Wolniejsze
Wstawianie	Wolniejsze	Szybsze ✅
Rotacje (ins)	Max 1	Max 2
Rotacje (del)	Max O(log n)	Max 3

Wybór: - AVL → więcej wyszukiwań (bazy danych) - Red-Black → więcej wstawień/usunięć (std::map w C++)

16.2. AVL vs Hash Table:

Operacja	AVL Tree	Hash Table
Wyszukiwanie	O(log n)	O(1) ✅
Wstawianie	O(log n)	O(1) ✅
Uporządkowanie	TAK ✅	NIE
Range Query	TAK ✅	NIE
Pamięć	O(n)	O(n)

Wybór: - AVL → potrzebna kolejność lub range queries - Hash → tylko wyszukiwanie (najszybsze)

17. Optymalizacje

17.1. Przechowywanie BF zamiast wysokości:

17.2. Lazy balancing:

Nie balansuj natychmiast, ale po wielu operacjach
Kompromis: wydajność vs gwarancje

18. Podsumowanie

AVL Tree:

Samobalansujące drzewo BST
Warunek AVL: |BF| ≤ 1 dla każdego węzła
BF = height(left) - height(right)

Operacje:

Operacja	Złożoność	Uwagi
Wyszukiwanie	O(log n) ✅	Gwarantowane!
Wstawianie	O(log n) ✅	Max 1 rotacja
Usuwanie	O(log n) ✅	Max O(log n) rotacji
Wysokość	≤ 1.44 log n	Bardzo płaskie

Rotacje:

LL (Left-Left): Rotacja w prawo
RR (Right-Right): Rotacja w lewo
LR (Left-Right): Rotacja w lewo + w prawo
RL (Right-Left): Rotacja w prawo + w lewo

Zalety: - ✅ Gwarantowane O(log n) dla wszystkich operacji - ✅ Bardzo płaskie (h ≤ 1.44 log n) - ✅ Lepsze dla częstych wyszukiwań - ✅ Deterministyczna wydajność

Wady: - ❌ Więcej rotacji przy wstawianiu/usuwaniu - ❌ Bardziej skomplikowana implementacja - ❌ Większy narzut pamięci (height/BF) - ❌ Wolniejsze wstawianie niż Red-Black

Kiedy używać: - ✅ Częste wyszukiwania (bazy danych, indeksy) - ✅ Potrzebna gwarancja O(log n) - ✅ Range queries (uporządkowane dane) - ✅ Krytyczne aplikacje (czas rzeczywisty)

Kiedy NIE używać: - ❌ Więcej wstawień/usunięć (użyj Red-Black) - ❌ Tylko wyszukiwanie (użyj Hash Table) - ❌ Małe dane (zwykły BST wystarczy)

Kluczowa obserwacja:

Cztery przypadki balansowania:

LL → Rotacja w prawo
RR → Rotacja w lewo
LR → Rotacja w lewo (dziecko) + w prawo (rodzic)
RL → Rotacja w prawo (dziecko) + w lewo (rodzic)

Co dalej warto poznać:

Red-Black Trees – alternatywne balansowanie (std::map, Java TreeMap)
B-drzewa – dla systemów plików i baz danych
Splay Trees – samooptymalizujące drzewa
Treap – randomizowane drzewa BST
2-3 Trees – poprzednik B-drzew