Drzewa poszukiwań: BST, AVL i czerwono-czarne

Tablica mieszająca daje dostęp w czasie stałym, ale gubi porządek. Wyszukiwanie binarne porządek wykorzystuje, ale wymaga tablicy, w której każde wstawienie kosztuje przesunięcie ogona. Drzewo poszukiwań binarnych rozwiązuje dokładnie ten konflikt: trzyma dane uporządkowane i pozwala je wstawiać bez przesuwania czegokolwiek.

Zasada jest jednozdaniowa: w każdym węźle wszystko z lewej strony jest mniejsze, wszystko z prawej większe. Szukanie polega na schodzeniu w dół – jedno porównanie na poziom.

Kiedy drzewo jest drzewem

Piętnaście losowych liczb, wysokość cztery, kilkadziesiąt porównań. Wygląda dokładnie tak, jak w podręczniku: każde zejście o poziom odrzuca połowę kandydatów, więc szukanie kosztuje O(log n).

A teraz przełącz listę dane na posortowane i uruchom ponownie.

Drzewo znika. Zostaje lista: każdy kolejny element jest większy od wszystkiego, co już jest w środku, więc ląduje w prawym poddrzewie – zawsze. Wysokość rośnie do 15, a licznik porównań pokazuje 105, czyli n(n−1)/2. To ta sama liczba, którą w pierwszej części serii o sortowaniu wykonywało sortowanie bąbelkowe i to ten sam mechanizm, który psuje quicksort na danych posortowanych. Struktura danych obiecująca O(log n) daje O(n) – na wejściu, które w praktyce zdarza się częściej niż losowe, bo dane bardzo często przychodzą już uporządkowane (klucze z bazy, znaczniki czasu, identyfikatory rosnące).

# Python
class Node:
    __slots__ = ("value", "left", "right")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def insert(node, value):
    """Zwykłe BST: schodzimy w dół, aż trafimy na puste miejsce."""
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node


def contains(node, value):
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False

Rotacja, czyli jak prostuje się drzewo

Ratunek nazywa się równoważeniem: po każdym wstawieniu sprawdzamy, czy poddrzewa nie różnią się zanadto wysokością, i jeśli tak – wykonujemy rotację. Rotacja to lokalna operacja na trzech wskaźnikach, która zmienia kształt drzewa, nie ruszając porządku.

# Python
def rotate_right(node):
    """Lewe dziecko idzie w górę, węzeł staje się jego prawym dzieckiem."""
    pivot = node.left
    node.left = pivot.right
    pivot.right = node
    refresh_height(node)
    refresh_height(pivot)
    return pivot          # nowy korzeń tego poddrzewa

Zaznacz teraz w animacji pole równoważenie (AVL) przy danych posortowanych.

Te same piętnaście liczb, ta sama kolejność – i wysokość 4 zamiast 15, czyli dokładnie minimum teoretyczne dla piętnastu węzłów. Licznik rotacji pokazuje, ile razy drzewo musiało się wyprostować po drodze.

AVL kontra czerwono-czarne

Obie struktury robią to samo (utrzymują wysokość O(log n)), ale różnią się tym, jak bardzo są rygorystyczne:

• AVL (Adelson-Wielski i Landis, 1962) wymaga, by wysokości poddrzew każdego węzła różniły się najwyżej o 1. Drzewo jest przez to bardzo płaskie, więc wyszukiwanie jest szybsze – kosztem częstszych rotacji przy wstawianiu i usuwaniu.
• Drzewo czerwono-czarne dopuszcza, by jedna gałąź była nawet dwa razy dłuższa od drugiej. Jest mniej płaskie, ale modyfikacje są tańsze, bo rzadziej trzeba przebudowywać strukturę.

Stąd podział w praktyce: gdzie dominują odczyty, opłaca się AVL; gdzie miesza się odczyty z zapisami, wygrywa drzewo czerwono-czarne. I dlatego to właśnie ono siedzi w bibliotekach standardowych: TreeMap i TreeSet w Javie, std::map i std::set w C++, a od Javy 8 również w kubełkach HashMap – jako awaryjny plan na wypadek zbyt wielu kolizji, o którym była mowa we wpisie o atakach przez złożoność.

Po co drzewo, skoro słownik jest szybszy

To jest pytanie, które trzeba sobie zadać, bo O(log n) przegrywa z O(1) na każdym slajdzie. Odpowiedź brzmi: drzewo odpowiada na pytania, których słownik nie rozumie.

• Zakres. „Wszystkie zamówienia z ostatnich siedmiu dni” – w drzewie schodzisz do początku przedziału i idziesz w prawo. W tablicy mieszającej trzeba przejrzeć wszystko.
• Sąsiedztwo. „Najbliższa wolna godzina po 14:00”, „pierwszy klient o nazwisku po Kowalskim” – to zapytanie o następnik, które drzewo realizuje w O(log n).
• Kolejność. Przejście in-order zwraca dane posortowane bez sortowania. To ta sama sztuczka, którą sortowanie drzewiaste wykorzystuje jako algorytm.
• Minimum i maksimum – zawsze na skraju, w O(log n), bez przeglądania.

W Pythonie nie ma wbudowanego drzewa (moduł bisect na liście załatwia wiele z tych przypadków przy niewielkiej liczbie modyfikacji), ale w Javie, C++ czy C# wybór między HashMap a TreeMap to dokładnie ta decyzja: czy pytasz o pojedyncze klucze, czy o ich sąsiedztwo.

Podsumowanie

Drzewo poszukiwań to odpowiedź na pytanie „jak trzymać dane w porządku, skoro cały czas się zmieniają”. Płacisz logarytmem zamiast stałej, dostajesz zakresy, sąsiedztwo i kolejność.

Ale samo drzewo binarne nie wystarczy – trzeba jeszcze pilnować, żeby nie zamieniło się w listę. Zobaczyliśmy dziś, jak łatwo to się dzieje: wystarczy podać dane w kolejności rosnącej, czyli w tej, w której najczęściej przychodzą z prawdziwego systemu.

W następnej części zobaczymy, co się z tym pomysłem dzieje, gdy dane przestają mieścić się w pamięci – i dlaczego indeks w bazie danych, choć jest drzewem, wygląda zupełnie inaczej niż to z dzisiejszej animacji.