Drzewa Binarne Wyszukiwania Dwoinkowe: Wstawianie, Wyszukiwanie i Utrzymywanie Równowagi AVL

Jedna niezmiennaość, trzy operacje

Drzewo binarne wyszukiwania (BST) przechowuje klucze zgodnie z jedną niezmienną: dla każdego węzła, wszystko w jego lewej poddrzewie jest mniejsze, a wszystko w jego prawej poddrzewie jest większe. Ta niezmienna sama w sobie wystarcza do wykonania wyszukiwania, wstawiania i usuwania wszystkich zgodnie z tym samym wzorem — porównaj klucz docelowy z bieżącym węzłem i rekurencyjnie przeszukuj lewo lub prawo — przekształcając to, co w przeciwnym razie byłoby liniową analizą, w ścieżkę w dół drzewa.

search(node, key):
  if node is null: return not found
  if key == node.key: return node
  if key < node.key: return search(node.left, key)
  else:                return search(node.right, key)
insert: search until you fall off the tree, attach a new leaf there
delete: 0 or 1 child -> splice node out; 2 children -> replace with in-order successor

Złożoność zależy w całości od kształtu drzewa

Wszystkie trzy operacje kosztują O(h), gdzie h oznacza wysokość drzewa. Dla idealnie zbalansowanego drzewa z n kluczami, h = O(log n), więc wyszukiwanie, wstawianie i usuwanie są wszystkie logarytmiczne. Jednak BST zbudowany przez wstawianie kluczy już posortowane degeneruje się w prostą łańcuchową strukturę, z h = n − 1: drzewo staje się strukturalnie listą powiązaną, a każda operacja kosztuje O(n). Inwersja BST gwarantuje poprawność; nie gwarantuje ona równowagi.

In-order przemieszczenie odzyskuje posortowany porządek za darmo

Odwiedzanie BST w kolejności in-order (lewe poddrzewo, węzeł, prawe poddrzewo, rekurencyjnie) zawsze daje klucze w rosnącym, posortowanym porządku, bezpośredni wynik z zasady wyszukiwania. To jeden z powodów, dla których warto używać BST zamiast tabeli hash, gdy potrzebujesz zapytań o zakres lub iteracji posortowanej: tabela hash zapewnia średnio O(1) wyszukiwanie, ale nie gwarantuje porządku, a zbalansowany BST oferuje O(log n) wyszukiwanie i uzyskanie posortowanego wyniku jako efekt uboczny.

Drzewa AVL: Balansowanie przez rotację

Drzewo AVL (Adelson-Velsky i Landis, 1962) przywraca gwarancję logarytmiczną poprzez egzekwowanie pewnej cechy równowagi po każdym wstawieniu i usunięciu: dla każdego węzła różnica wysokości jego poddrzew lewego i prawego nie przekracza 1. Gdy operacja narusza tę cechę, drzewo wykonuje rotację - lokalną restrukturyzację kilku wskaźników, która przywraca równowagę bez łamania właściwości drzewa poszukiwania.

prawy obrót wokół węzła y (naprawia niezbalansowanie lewo-lewe): y x / \ / \ x C -> A y / \ / \ A B B C (lewy obrót jest lustrzanym odbiciem) Ponieważ rotacja jedynie przekształca stałą liczbę wskaźników, a maksymalnie jeden niezbalansowanie wymaga naprawy na drodze powrotnej do korzenia, każde wstawienie lub usunięcie kosztuje O(log n) dla wyszukiwania plus w najgorszym przypadku O(log n) dla ponownego zbilansowania. Drzewa AVL utrzymują wysokość w granicach około 1,44 log2(n), bardziej precyzyjne ograniczenie niż drzewo czerwono-czarne, które nieco luźniej balansuje i wykonuje mniej rotacji na aktualizację.

right rotation around node y (fixes left-left imbalance):
      y                x
     / \                / \
    x   C     ->      A   y
   / \                    / \
  A   B                  B   C
(a left rotation is the mirror image)

Dlaczego utrzymywanie równowagi jest tego wart

Cała zaleta BST (drzewa binarne wyszukiwania) w porównaniu z prostym, posortowanym tablicą to O(log n) operacji wstawiania i usuwania zamiast O(n) przesunięć. Ta zaleta znika natychmiast, gdy drzewo jest dozwolone do degeneracji. Warianty samowzrostowe – AVL, czerwono-czarne, drzewa splayowe – wszystkie istnieją, aby zapewnić gwarancję O(log n) dla każdej sekwencji operacji, a nie tylko w sprzyjających warunkach, kosztem współczynnika równowagi dla każdego węzła i okazjonalnych rotacji.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Binary Search Tree i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.