Drzewo wyszukiwania binarnego (BST) z przykładem

Co to jest drzewo wyszukiwania binarnego?

Drzewo Poszukiwań Binarnych (BST) to zaawansowany algorytm służący do analizy węzła, jego lewej i prawej gałęzi, modelowanych w strukturze drzewa, oraz zwracania wartości. BST został opracowany w oparciu o architekturę podstawowego algorytmu wyszukiwania binarnego, dzięki czemu umożliwia szybsze wyszukiwanie, wstawianie i usuwanie węzłów. Dzięki temu program jest niezwykle szybki i dokładny.

Atrybuty drzewa wyszukiwania binarnego

BST składa się z wielu węzłów i zawiera następujące atrybuty:

• Węzły drzewa są reprezentowane w relacji nadrzędny-podrzędny.
• Każdy węzeł nadrzędny może mieć zero węzłów podrzędnych lub maksymalnie dwa podwęzły lub poddrzewa po lewej i prawej stronie.
• Każde poddrzewo, znane również jako drzewo wyszukiwania binarnego, ma podgałęzie po prawej i lewej stronie.
• Wszystkie węzły są połączone parami klucz-wartość.
• Klucze węzłów znajdujących się w lewym poddrzewie są mniejsze od kluczy ich węzła nadrzędnego.
• Podobnie klucze węzłów znajdujących się w prawym poddrzewie są większe od kluczy ich węzła nadrzędnego.

1. Istnieje węzeł główny lub poziom nadrzędny 11. Pod nim znajdują się węzły/gałęzie lewe i prawe z własnymi wartościami kluczy.
2. Prawe poddrzewo ma wartości kluczy większe niż węzeł nadrzędny.
3. Lewe poddrzewo ma mniejsze wartości kluczy niż węzeł nadrzędny.

Dlaczego potrzebujemy drzewa wyszukiwania binarnego?

• Dwa najważniejsze czynniki, które sprawiają, że drzewo poszukiwań binarnych jest optymalnym rozwiązaniem każdego problemu ze świata rzeczywistego, to szybkość i dokładność.
• Dzięki temu, że wyszukiwanie binarne odbywa się w formacie rozgałęzionym z relacjami rodzic-dziecko, algorytm wie, w którym miejscu drzewa należy przeszukać elementy. Zmniejsza to liczbę porównań klucz-wartość, które program musi wykonać, aby zlokalizować żądany element.
• Dodatkowo, jeśli przeszukiwany element jest większy lub mniejszy od węzła nadrzędnego, węzeł wie, po której stronie drzewa ma szukać. Dzieje się tak, ponieważ lewe poddrzewo jest zawsze mniejsze od węzła nadrzędnego, a prawe poddrzewo ma wartości zawsze równe lub większe od węzła nadrzędnego.
• BST jest powszechnie używany do implementacji złożonych wyszukiwań, solidnej logiki gier, działań z funkcją automatycznego uzupełniania i grafiki.
• Algorytm efektywnie obsługuje operacje takie jak wyszukiwanie, wstawianie i usuwanie.

Rodzaje drzew binarnych

Trzy rodzaje drzew binarnych to:

• Pełne drzewo binarne: Wszystkie poziomy w drzewie są pełne, z możliwym wyjątkiem ostatniego poziomu. Podobnie, wszystkie węzły są pełne, kierując się najdalej w lewo.
• Pełne drzewo binarne: Wszystkie węzły mają 2 węzły podrzędne, za wyjątkiem liścia.
• Zrównoważone lub idealne drzewo binarne: W drzewie wszystkie węzły mają dwoje dzieci. Poza tym każdy podwęzeł ma ten sam poziom.

Dowiedz się więcej o: Drzewo binarne w strukturze danych Jeśli jesteś zainteresowany.

Jak działa drzewo wyszukiwania binarnego?

Drzewo zawsze ma węzeł główny i dalsze węzły podrzędne, czy to po lewej, czy po prawej stronie. Algorytm wykonuje wszystkie operacje, porównując wartości z korzeniem i jego dalszymi węzłami podrzędnymi w lewym lub prawym poddrzewie.

W zależności od tego, jaki element ma zostać wstawiony, przeszukany lub usunięty, algorytm po porównaniu może łatwo pominąć lewe lub prawe poddrzewo węzła głównego.

BST oferuje przede wszystkim trzy rodzaje operacji do wykorzystania:

• Szukanie: wyszukuje element w drzewie binarnym.
• Wstawić: dodaje element do drzewa binarnego.
• Kasować: usuwa element z drzewa binarnego.

Każda operacja ma swoją własną strukturę i metodę wykonywania/analizy, ale najbardziej złożoną ze wszystkich jest operacja usuwania.

Szukaj Operacja

Analizę drzewa należy zawsze rozpoczynać od węzła głównego, a następnie przechodzić do prawego lub lewego poddrzewa węzła głównego, w zależności od tego, czy element, który ma zostać zlokalizowany, jest mniejszy czy większy od korzenia.

1. Przeszukiwany element to 10.
2. Porównaj element z węzłem głównym 12, 10 < 12, co spowoduje przejście do lewego poddrzewa. Nie ma potrzeby analizowania prawego poddrzewa.
3. Teraz porównaj 10 z węzłem 7, 10 > 7, przejdź do prawego poddrzewa.
4. Następnie porównaj 10 z następnym węzłem, którym jest 9, 10 > 9, spójrz na prawe dziecko poddrzewa.
5. 10 dopasowań z wartością w węźle, 10 = 10, zwraca wartość użytkownikowi.

Rzekomy Code do wyszukiwania w BST

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

wstawka Operacja

To bardzo prosta operacja. Najpierw wstawiany jest węzeł główny, a następnie kolejna wartość jest z nim porównywana. Jeśli wartość jest większa od węzła głównego, jest dodawana do prawego poddrzewa, a jeśli jest mniejsza od węzła głównego, jest dodawana do lewego poddrzewa.

1. Istnieje lista 6 elementów, które należy wstawić do BST w kolejności od lewej do prawej.
2. Wstaw 12 jako węzeł główny i porównaj kolejne wartości 7 i 9, aby wstawić je odpowiednio do prawego i lewego poddrzewa.
3. Porównaj pozostałe wartości 19, 5 i 10 z węzłem głównym 12 i umieść je odpowiednio. 19 > 12, umieść je jako prawe dziecko 12; 5 < 12 i 5 < 7, stąd umieść je jako lewe dziecko 7. Teraz porównaj 10, 10 jest < 12 i 10 jest > 7 i 10 jest > 9, umieść 10 jako prawe poddrzewo 9.

Pseudokod do wstawiania węzła w BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Usunięcia Operanych

Aby usunąć węzeł z BST, istnieją pewne przypadki, takie jak usunięcie korzenia lub usunięcie węzła liścia. Ponadto, po usunięciu korzenia, musimy pomyśleć o węźle korzeniowym.

Powiedzmy, że chcemy usunąć węzeł liścia, możemy go po prostu usunąć, ale jeśli chcemy usunąć korzeń, musimy zastąpić wartość korzenia innym węzłem. Weźmy następujący przykład:

• Przypadek 1 – węzeł z zerowymi dziećmi: to jest najłatwiejsza sytuacja, wystarczy usunąć węzeł, który nie ma żadnych dalszych dzieci ani po prawej, ani po lewej stronie.
• Przypadek 2 – Węzeł z jednym dzieckiem: po usunięciu węzła wystarczy połączyć jego węzeł podrzędny z węzłem nadrzędnym usuniętej wartości.
• Przypadek 3 – Węzeł z dwójką dzieci: jest to najtrudniejsza sytuacja, która opiera się na dwóch następujących zasadach:
  • 3a – Poprzednik w kolejności: należy usunąć węzeł z dwoma dziećmi i zastąpić go największą wartością w lewym poddrzewie usuniętego węzła.
  • 3b – Następca w kolejności: należy usunąć węzeł z dwoma dziećmi i zastąpić go najmniejszą wartością w prawym poddrzewie usuniętego węzła.

1. To pierwszy przypadek usunięcia, w którym usuwasz węzeł, który nie ma potomków. Jak widać na diagramie, 19, 10 i 5 nie mają potomków. Ale usuniemy 19.
2. Usuń wartość 19 i usuń łącze z węzła.
3. Zobacz nową strukturę BST bez 19.

1. To drugi przypadek usunięcia, w którym usuwasz węzeł, który ma 1 potomka. Jak widać na diagramie, węzeł 9 ma jedno potomstwo.
2. Usuń węzeł 9 i zastąp go jego dzieckiem 10, a następnie dodaj połączenie od 7 do 10.
3. Zobacz nową strukturę BST bez 9.

1. Tutaj usuniesz węzeł 12, który ma dwójkę dzieci.
2. Usunięcie węzła nastąpi zgodnie z regułą kolejności poprzedników, co oznacza, że ​​największy element w lewym poddrzewie 12 zastąpi go.
3. Usuń węzeł 12 i zastąp go wartością 10, ponieważ jest to największa wartość w lewym poddrzewie.
4. Zobacz nową strukturę BST po usunięciu 12.

1. Usuń węzeł 12, który ma dwoje dzieci.
2. Usunięcie węzła nastąpi zgodnie z regułą In-Order Successor, co oznacza, że ​​najmniejszy element w prawym poddrzewie 12 zastąpi go.
3. Usuń węzeł 12 i zastąp go węzłem 19, ponieważ jest to najmniejsza wartość w prawym poddrzewie.
4. Zobacz nową strukturę BST po usunięciu 12.

Rzekomy Code do usuwania węzła

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Ważne terminy

• Wstawić: Wstawia element do drzewa / tworzy drzewo.
• Szukanie: Wyszukuje element w drzewie.
• Przejście w przedsprzedaży: Przechodzi przez drzewo w sposób uporządkowany.
• Przechodzenie w kolejności: Przechodzi przez drzewo w sposób uporządkowany.
• Przejście postorderowe: Przechodzi przez drzewo w sposób uporządkowany.

FAQ