Drzewa Binarne Wyszukiwania

3.1 Definicja drzewa binarnego wyszukiwania (BST)

Drzewo binarne wyszukiwania (BST) to drzewo binarne, które ma następujące właściwości:

• Dla każdego węzła, jego lewe poddrzewo zawiera tylko węzły z kluczami mniejszymi od klucza tego węzła.
• Dla każdego węzła, jego prawe poddrzewo zawiera tylko węzły z kluczami większymi od klucza tego węzła.
• Oba poddrzewa każdego węzła również są drzewami binarnymi wyszukiwania.

Przykład BST:

BST to skrót od Binary Search Tree – dosłownie „Binarne Drzewo Wyszukiwania”. To w zasadzie organizacja danych w formie „drzewa”, które umożliwia bardzo szybkie wyszukiwanie. Struktura drzewa to w zasadzie ukryte/sprytne sortowanie elementów.

Przejście w porządku centralnym (in-order traversal)

Zadanie przejścia — w określony sposób uformować listę węzłów (lub danych z węzłów, to kwestia terminologii i ma praktyczne znaczenie). Przejście centralne (symetryczne) to takie, przy którym korzeń drzewa znajduje się pomiędzy wynikami odpowiednich przejść lewego i prawego poddrzewa.

Razem z właściwością drzewa binarnego wyszukiwania (o nierównościach, zob. teorię) to mówi, że przejście w porządku centralnym drzewa binarnego wyszukiwania stworzy nam posortowaną listę węzłów — super! Oto jak będzie wyglądać przejście zdefiniowanego wcześniej drzewa:

3.2 Zasady działania i właściwości BST

Zasady działania:

• Organizacja danych: BST organizuje dane tak, aby zapewnić efektywne wyszukiwanie, wstawianie i usuwanie elementów.
• Struktura rekurencyjna: Każdy węzeł w BST podlega tym samym zasadom co korzeń drzewa, co czyni strukturę rekurencyjną.
• Równoważenie: Aby zapewnić optymalną wydajność, BST powinno być zrównoważone, czyli wysokość lewego i prawego poddrzewa powinna być w miarę możliwości równa.

Właściwości BST:

• Porządek: W każdej chwili można przejść przez drzewo w porządku "in-order" (lewe poddrzewo → bieżący węzeł → prawe poddrzewo), aby uzyskać wszystkie elementy w posortowanym porządku.
• Czas operacji:
  • Średni czas operacji wyszukiwania, wstawiania i usuwania wynosi O(log n), gdzie n — liczba węzłów.
  • W najgorszym przypadku (jeśli drzewo nie jest zrównoważone) czas operacji może wynieść O(n).
• Unikalne klucze: Wszystkie klucze w BST muszą być unikalne, aby zachować porządek.

3.3 Podstawowe operacje

1. Wstawianie (Insertion):

Zasada działania:

• Zaczynamy od korzenia.
• Porównujemy klucz nowego węzła z kluczem bieżącego węzła.
• Jeśli nowy klucz jest mniejszy, przechodzimy do lewego poddrzewa, jeśli większy — do prawego.
• Powtarzamy proces, dopóki nie znajdziemy odpowiedniego miejsca do wstawienia nowego węzła (czyli lewy lub prawy potomek nie istnieje).

Algorytm:

1. Jeśli drzewo jest puste, nowy węzeł staje się korzeniem.
2. W przeciwnym razie rekurencyjnie znajdujemy odpowiednie miejsce i dodajemy nowy węzeł.

2. Usuwanie (Deletion):

Zasada działania:

• Znajdź węzeł do usunięcia.
• Rozważ trzy przypadki:
• Węzeł jest liściem (nie ma dzieci): po prostu usuń węzeł.
• Węzeł ma jedno dziecko: zastąp węzeł jego dzieckiem.
• Węzeł ma dwoje dzieci: znajdź najmniejszy węzeł w prawym poddrzewie (lub największy w lewym), skopiuj jego wartość do usuwanego węzła i rekurencyjnie usuń najmniejszy węzeł w prawym poddrzewie.

Algorytm:

1. Znajdź węzeł z danym kluczem.
2. W zależności od przypadku wykonaj odpowiednie usunięcie i przearanżowanie węzłów.

3. Wyszukiwanie (Search):

Zasada działania:

• Zaczynamy od korzenia.
• Porównujemy klucz szukanego węzła z kluczem bieżącego węzła.
• Jeśli klucz się zgadza, zwracamy węzeł.
• Jeśli klucz jest mniejszy, przechodzimy do lewego poddrzewa, jeśli większy — do prawego.
• Powtarzamy proces, dopóki nie znajdziemy węzła z szukanym kluczem lub nie osiągniemy końca drzewa (wtedy węzeł nie został znaleziony).

Algorytm:

1. Jeśli drzewo jest puste lub klucz węzła zgadza się z szukanym, zwracamy węzeł.
2. Jeśli klucz szukanego węzła jest mniejszy, rekurencyjnie szukamy w lewym poddrzewie.
3. Jeśli klucz szukanego węzła jest większy, rekurencyjnie szukamy w prawym poddrzewie.

3.4 Przykłady zadań rozwiązywanych za pomocą BST

1. Wyszukiwanie elementu w dynamicznym zbiorze

Należy utrzymać zbiór liczb, do którego można dodawać nowe elementy, usuwać istniejące i szybko sprawdzać, czy dane liczba znajduje się w zbiorze.

Rozwiązanie z użyciem BST:

• Wstawianie nowych elementów do drzewa.
• Usuwanie istniejących elementów.
• Wyszukiwanie elementów w drzewie.

Przykład użycia:

Utrzymanie listy zarejestrowanych użytkowników w systemie, gdzie użytkownicy mogą być dodawani i usuwani, a system musi szybko weryfikować, czy użytkownik jest zarejestrowany.

2. Znajdowanie minimalnego i maksymalnego elementu

Należy szybko znajdować minimalne i maksymalne wartości w zbiorze danych.

Rozwiązanie z użyciem BST:

• Minimalny element znajduje się w najbardziej lewym węźle drzewa.
• Maksymalny element znajduje się w najbardziej prawym węźle drzewa.

Przykład użycia:

Utrzymanie systemu śledzenia cen akcji, gdzie trzeba szybko znajdować minimalną i maksymalną cenę w danym momencie.

3. Sprawdzanie równowagi wyrażenia

Dano matematyczne wyrażenie, trzeba sprawdzić jego równowagę pod względem liczby nawiasów otwierających i zamykających.

Rozwiązanie z użyciem BST:

Używamy BST do przechowywania stanów pośrednich sprawdzania równowagi nawiasów.

Przykład użycia:

Parsowanie i kompilacja kodu, gdzie trzeba sprawdzać poprawność zamieszczenia nawiasów w wyrażeniach.

4. Budowanie słownika

Należy stworzyć strukturę danych do przechowywania słownika, w którym słowa mogą być dodawane, usuwane i szybko znajdywane.

Rozwiązanie z użyciem BST:

• Słowa dodawane są do drzewa w porządku alfabetycznym.
• Wyszukiwanie słów odbywa się po kluczach.

Przykład użycia:

System autokorekty tekstu, gdzie trzeba szybko znajdować i poprawiać słowa.