Równoważenie drzew: drzewa AVL

4.1 Problemy niezrównoważonych drzew

W tradycyjnych (niezrównoważonych) drzewach, podczas dodawania elementów mogą pojawiać się nieprzyjemne efekty.

1. Zwiększenie wysokości drzewa:

W niezrównoważonych drzewach wysokość może osiągać n (gdzie n — liczba węzłów), co prowadzi do degradacji wydajności.

Czas wykonywania podstawowych operacji (wyszukiwanie, wstawianie, usuwanie) w najgorszym przypadku staje się O(n).

2. Nierównomierne rozłożenie węzłów:

W niezrównoważonych drzewach niektóre poddrzewa mogą zawierać znacznie więcej węzłów niż inne, co prowadzi do nieefektywnego wykorzystania pamięci i wydłużenia czasu przetwarzania.

3. Pogorszenie czasu wykonywania operacji:

W niezrównoważonych drzewach operacje wyszukiwania, wstawiania i usuwania wymagają więcej czasu z powodu zwiększonej wysokości drzewa.

Przykład niezrównoważonego drzewa:

W tym przykładzie drzewo faktycznie zamienia się w listę jednokierunkową, a czas wykonywania operacji staje się liniowy.

4.2 Definicja drzewa AVL i jego właściwości

Drzewo AVL (nazwane na cześć swoich wynalazców, Adelsona-Velskiego i Landisa) — to typ zrównoważonego binarnego drzewa wyszukiwania, w którym dla każdego węzła różnica wysokości jego lewego i prawego poddrzewa nie przekracza 1.

Właściwości drzewa AVL:

1. Zrównoważenie:

Różnica wysokości lewego i prawego poddrzewa dowolnego węzła nie przekracza 1.

To zapewnia wysokość drzewa O(log n), gdzie n — liczba węzłów, co gwarantuje efektywne wykonywanie operacji wyszukiwania, wstawiania i usuwania.

2. Binarne drzewo wyszukiwania:

Drzewo AVL posiada wszystkie właściwości binarnego drzewa wyszukiwania: dla każdego węzła wszystkie klucze w lewym poddrzewie są mniejsze od klucza węzła, a wszystkie klucze w prawym poddrzewie są większe od klucza węzła.

3. Automatyczne równoważenie:

Po każdej operacji wstawiania lub usuwania wykonywana jest równoważenie drzewa w celu zachowania jego właściwości.

4.3 Przykłady równoważenia drzew

Rotacje to operacje, które są wykonywane w celu przywrócenia równowagi w drzewie AVL po wstawieniu lub usunięciu węzłów. Istnieją cztery rodzaje rotacji: lewa, prawa, lewo-prawe i prawo-lewe.

1. Lewa rotacja (Left Rotation):

W lewej rotacji węzeł x przesuwa się w górę, a jego prawy węzeł potomny y staje się jego rodzicem. Lewe poddrzewo y staje się prawym poddrzewem x.

2. Prawa rotacja (Right Rotation):

W prawej rotacji węzeł x przesuwa się w górę, a jego lewy węzeł potomny y staje się jego rodzicem. Prawe poddrzewo y staje się lewym poddrzewem x.

3. Lewo-prawe rotacja (Left-Right Rotation):

Najpierw wykonywana jest lewa rotacja na lewym węźle potomnym, a następnie prawa rotacja na samym węźle.

4. Prawo-lewe rotacja (Right-Left Rotation):

Najpierw wykonywana jest prawa rotacja na prawym węźle potomnym, a następnie lewa rotacja na samym węźle.

4.4 Podstawowe operacje w drzewach AVL

Podstawowe operacje w drzewach AVL obejmują wstawianie, usuwanie i wyszukiwanie.

Wstawianie (Insertion)

Trzeba wstawić nowy węzeł w drzewo AVL i zrównoważyć go, jeśli to konieczne.

Kroki:

1. Wstawianie węzła:
   • Zaczynamy od korzenia drzewa i rekurencyjnie znajdujemy odpowiednie miejsce dla nowego węzła, porównując jego wartość z aktualnymi węzłami.
   • Wstawiamy nowy węzeł w znalezione miejsce, jak w zwykłym binarnym drzewie wyszukiwania.
2. Aktualizacja wysokości:
   • Po wstawieniu aktualizujemy wysokości wszystkich węzłów na drodze od nowego węzła do korzenia.
3. Równoważenie drzewa:
   • Sprawdzamy równowagę każdego węzła na drodze od nowego węzła do korzenia.
   • Jeśli równowaga któregoś węzła jest zaburzona (różnica wysokości lewego i prawego poddrzewa większa niż 1), wykonujemy odpowiednią rotację, aby przywrócić równowagę.

Przykład:

2. Usuwanie (Deletion)

Trzeba usunąć węzeł z drzewa AVL i zrównoważyć go, jeśli to konieczne.

Kroki:

1. Wyszukiwanie i usuwanie węzła:

• Zaczynamy od korzenia drzewa i rekurencyjnie znajdujemy węzeł do usunięcia.
• Usuwamy węzeł jak w zwykłym binarnym drzewie wyszukiwania:
• Jeśli węzeł jest liściem, po prostu go usuwamy.
• Jeśli węzeł ma jednego potomka, zamieniamy węzeł jego potomkiem.
• Jeśli węzeł ma dwóch potomków, znajdujemy najmniejszy węzeł w prawym poddrzewie (lub największy w lewym), kopiujemy jego wartość do usuwanego węzła i rekurencyjnie usuwamy najmniejszy węzeł w prawym poddrzewie.

2. Aktualizacja wysokości:

• Po usunięciu aktualizujemy wysokości wszystkich węzłów na drodze od usuniętego węzła do korzenia.

3. Równoważenie drzewa:

• Sprawdzamy równowagę każdego węzła na drodze od usuniętego węzła do korzenia.
• Jeśli równowaga któregoś węzła jest zaburzona, wykonujemy odpowiednią rotację, aby przywrócić równowagę.

Przykład:

3. Wyszukiwanie (Search)

Trzeba znaleźć węzeł z zadanym wartością w drzewie AVL.

Kroki:

1. Rekurencyjne wyszukiwanie:

• Zaczynamy od korzenia drzewa i rekurencyjnie porównujemy wyszukiwaną wartość z aktualnymi węzłami.
• Jeśli wartość jest mniejsza od aktualnego węzła, przechodzimy do lewego poddrzewa.
• Jeśli wartość jest większa od aktualnego węzła, przechodzimy do prawego poddrzewa.
• Jeśli wartość jest równa aktualnemu węzłowi, zwracamy ten węzeł.

Przykład: