Drzewo wyszukiwania binarnego (BST) z przykładem

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 rodzic-dziecko
• 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 niż klucze ich węzła nadrzędnego
• Podobnie klucze lewego węzła poddrzewa mają mniejsze wartości niż klucze węzła nadrzędnego.

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

Dlaczego potrzebujemy drzewa wyszukiwania binarnego?

• Dwa główne czynniki, które sprawiają, że drzewo wyszukiwania binarnego jest optymalnym rozwiązaniem wszelkich problemów w świecie rzeczywistym, 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, w przypadku, gdy szukany element jest większy lub mniejszy od węzła nadrzędnego, węzeł wie, której strony drzewa szukać. Powodem jest to, że lewe poddrzewo jest zawsze mniejsze niż węzeł nadrzędny, a prawe poddrzewo ma wartości zawsze równe lub większe niż węzeł nadrzędny.
• 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:

• Kompletne drzewo binarne: wszystkie poziomy w drzewach są pełne możliwych wyjątków ostatniego poziomu. Podobnie wszystkie węzły są pełne, kierując się skrajnie w lewo.
• Pełne drzewo binarne: wszystkie węzły mają 2 węzły podrzędne z wyjątkiem liścia.
• Zrównoważone lub doskonałe 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 elementu, który ma zostać wstawiony, przeszukany lub usunięty, po porównaniu algorytm może z łatwością usunąć lewe lub prawe poddrzewo węzła głównego.

BST oferuje przede wszystkim trzy rodzaje operacji do wykorzystania:

• Szukaj: przeszukuje element z drzewa binarnego
• Wstaw: dodaje element do drzewa binarnego
• Usuń: usuń 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

Zawsze rozpoczynaj analizę drzewa w węźle głównym, a następnie przejdź dalej do prawego lub lewego poddrzewa węzła głównego, w zależności od tego, czy lokalizowany element jest mniejszy lub większy od korzenia.

1. Szukanym elementem jest 10
2. Porównaj element z węzłem głównym 12, 10 < 12, w ten sposób przejdziesz do lewego poddrzewa. Nie ma potrzeby analizowania prawego poddrzewa
3. Teraz porównaj 10 z węzłem 7, 10 > 7, więc przejdź do prawego poddrzewa
4. Następnie porównaj 10 z następnym węzłem, czyli 9, 10 > 9, spójrz na prawe dziecko poddrzewa
5. 10 dopasowań z wartością w węźle, 10 = 10, zwraca wartość użytkownikowi.

Pseudokod 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 następna wartość jest porównywana z węzłem głównym. Jeśli wartość jest większa od korzenia, jest dodawana do prawego poddrzewa, a jeśli jest mniejsza od korzenia, 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 odpowiednio wstawić 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ść to jako prawe dziecko liczby 12, 5 < 12 i 5 < 7, a zatem umieść je jako lewe dziecko liczby 7. Teraz porównaj 10, 10 to < 12 i 10 to > 7, a 10 to > 9, miejsce 10 jako prawe poddrzewo liczby 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

Usuń Operanych

Istnieją pewne przypadki usunięcia węzła z BST, np. usunięcie korzenia lub usunięcie węzła liścia. Ponadto po usunięciu korzenia musimy pomyśleć o węźle głównym.

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: jest to najłatwiejsza sytuacja, wystarczy usunąć węzeł, który nie ma dalszych dzieci po prawej lub 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 i działa na podstawie następujących dwóch reguł
• 3a – W kolejności poprzednika: należy usunąć węzeł z dwójką dzieci i zastąpić go największą wartością z lewego poddrzewa usuniętego węzła
• 3b – W kolejności następcy: należy usunąć węzeł z dwójką dzieci i zastąpić go największą wartością z prawego poddrzewa usuniętego węzła

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

1. Jest to drugi przypadek usunięcia, w którym usuwa się węzeł mający 1 dziecko, jak widać na diagramie, że 9 ma jedno dziecko.
2. Usuń węzeł 9 i zastąp go jego dzieckiem 10 i dodaj łącze od 7 do 10
3. Zobacz nową strukturę BST bez 9

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

1. 1 Usuń węzeł 12, który ma dwoje dzieci
2. 2 Usunięcie węzła nastąpi w oparciu o regułę In Order Successor, co oznacza, że ​​zastąpi go największy element prawego poddrzewa liczby 12
3. 3 Usuń węzeł 12 i zastąp go węzłem 19, ponieważ jest to największa wartość w prawym poddrzewie
4. 4 Wyświetl nową strukturę BST po usunięciu 12

Pseudokod 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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Ważne terminy

• Wstaw: Wstawia element do drzewa/tworzy drzewo.
• Szukaj: przeszukuje element w drzewie.
• Przemierzanie w przedsprzedaży: Przemierza drzewo w sposób zamówiony w przedsprzedaży.
• Inorder Traversal: Przemierza drzewo w określonej kolejności.
• Postorder Traversal: Przemierza drzewo w sposób postorder.

Podsumowanie

• BST to zaawansowany algorytm, który wykonuje różne operacje w oparciu o porównanie wartości węzłów z węzłem głównym.
• Dowolny punkt w hierarchii nadrzędny-podrzędny reprezentuje węzeł. Co najmniej jeden węzeł nadrzędny lub główny pozostaje obecny przez cały czas.
• Istnieje lewe poddrzewo i prawe poddrzewo. Lewe poddrzewo zawiera wartości mniejsze niż węzeł główny. Jednak prawe poddrzewo zawiera wartość większą niż węzeł główny.
• Każdy węzeł może mieć zero, jeden lub dwoje dzieci.
• Drzewo wyszukiwania binarnego ułatwia wykonywanie podstawowych operacji, takich jak wyszukiwanie, wstawianie i usuwanie.
• Usuwanie jest najbardziej złożone i ma wiele przypadków, na przykład węzeł bez dzieci, węzeł z jednym dzieckiem i węzeł z dwójką dzieci.
• Algorytm jest wykorzystywany w rozwiązaniach rzeczywistych, takich jak gry, autouzupełnianie danych i grafika.