Drzewa AVL: Czynnik Równowagi, Który Nigdy Nie Przekracza ±2

Drzewo binarne wyszukiwania z obietnicą

Proste drzewo binarne wyszukiwania (BST) zapewnia O(log n) operację wyszukiwania tylko wtedy, gdy pozostaje w miarę zbalansowane; jeśli wprowadzamy klucze w posortowany sposób do niezbalansowanego BST, degeneruje się ono w listę powiązaną, z O(n) operacją wyszukiwania. Drzewo AVL, nazwane na cześć jego wynalazców z 1962 roku – Georgy'ego Adelson-Velsky’ego i Eugeniusza Landisa – było pierwszą strukturą danych, która gwarantowała O(log n) wysokość niezależnie od kolejności przychodzenia kluczy, poprzez egzekwowanie prostego prawa zachowania po każdym wstawieniu i usunięciu: dla każdego węzła wysokość jego lewego i prawego poddrzewa może się różnić maksymalnie o 1.

Współczynnik równowagi

Każedy węzeł śledzi (lub może obliczać) współczynnik równowagi: różnicę wysokości prawego poddrzewa i lewego poddrzewa. Legalny węzeł AVL ma współczynnik równowagi wynoszący -1, 0 lub +1. Wstawienie lub usunięcie klucza powoduje zmianę współczynnika równowagi każdego przodka na ścieżce z powrotem do korzenia; jeśli współczynnik równowagi jakiegokolwiek przodka osiągnie wartość -2 lub +2, drzewo przestaje być zgodne z zasadami AVL w tym węźle i musi zostać natychmiast naprawione, przed powrotem z operacji, poprzez rotację.

Jednolite i podwójne obroty

Istnieją dokładnie cztery kształty niebalance, a każdy z nich posiada stałe, mechaniczne rozwiązanie. Niebalance w lewo-lewo (wprowadzony do lewego poddrzewa lełego dziecka) jest naprawiana przez pojedynczy obrót w prawo; niebalance w prawo-prawo przez pojedynczy obrót w lewo. Przypadki mieszane – lewo-prawe (wprowadzony do prawego poddrzewa lełego dziecka) i prawe-lewo – wymagają dwóch obrotów po kolei, najpierw wyprostowania wewnętrznego zygzakuna w pochylenie jednokierunkowe, a następnie zastosowania pasującego pojedynczego obrotu:

// pojedynczy obrót w prawo, naprawiający niebalance w lewo-lewo na węźle z, dziecko y = z.left rotateRight(z): y = z.left z.left = y.right y.right = z aktualizuj wysokości z, a następnie y return y // y jest nowym korzeniem poddrzewa // przypadek lewo-prawe: dwa obroty fixLeftRight(z): z.left = rotateLeft(z.left) // najpierw wyprostuj zygzakun return rotateRight(z) // następnie zastosuj pasujący pojedynczy obrót A obrót to mała, stałoczasowa reorganizacja wskaźników – nigdy nie dotyka więcej niż kilkudziesięciu węzłów – a po wstawieniu potrzeba najwyżej jednego obrotu (jednego lub podwójnego) aby przywrócić równowagę całego drzewa, ponieważ naprawa najniższego niezbalansowanego przodka przywraca wysokość, którą oczekiwał jego własny rodzic. Usuwanie jest mniej łaskowe: może wymagać obrotów na każdym poziomie w drodze powrotnej do korzenia aż po O(log n) obrotów w najgorszym przypadku, ponieważ usunięcie węzła może zmniejszyć wysokość poddrzewa w sposób, który powoduje rozprzestrzenianie się niezbalansowania w górę.

// single right rotation, fixing a left-left imbalance at node z, child y = z.left
rotateRight(z):
  y = z.left
  z.left = y.right
  y.right = z
  update heights of z, then y
  return y                      // y is the new subtree root

// left-right case: two rotations
fixLeftRight(z):
  z.left = rotateLeft(z.left)   // straighten the zigzag first
  return rotateRight(z)          // then apply the matching single rotation

Why bother, when red-black trees also guarantee O(log n)?

AVL drzewa utrzymują bardziej ściśle zbieżność symetrii niż czerwono-czarne drzewa — wysokość AVL drzewa nigdy nie przekracza około 1.44*log2(n), zauważnie bliżej teoretycznego minimum log2(n) niż luźny zakres czerwonego-czarnego drzewa o wartości około 2*log2(n) — co sprawia, że wyszukiwania AVL są szybsze w praktyce dla obciążonych wyszukiwaniami zadań. Kosztem jest to, że drzewa AVL zbilansowują się bardziej agresywnie i dlatego wykonują więcej rotacji średnio na każde wstawienie lub usunięcie, co sprawia, że czerwono-czarne drzewa są częściej używane domyślne w implementacjach bibliotek ogólnego przeznaczenia (wiele standardowych map i zbiorów bibliotecznych ich używa) a drzewa AVL spotykają się z większym wykorzystaniem w strukturach skoncentrowanych na odczycie, takich jak indeksy bazy danych i plików systemowych, gdzie dodatkowe dyscyplina równowagi wypłaca się za każdym razem, gdy drzewo jest przeszukiwane.

Frequently asked questions

Wypróbuj na żywo

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