Drzewo wyszukiwania binarnego (BST) z przykładem

Spisie treści:

Anonim

Co to jest drzewo wyszukiwania binarnego?

Drzewo wyszukiwania binarnego to zaawansowany algorytm służący do analizy węzła, jego lewej i prawej gałęzi, które są modelowane w strukturze drzewa i zwracają wartość. BST został opracowany na podstawie architektury podstawowego algorytmu wyszukiwania binarnego; w związku z tym umożliwia szybsze wyszukiwanie, wstawianie i usuwanie węzłów. To sprawia, że ​​program jest naprawdę szybki i dokładny.

Z tego samouczka Struktura danych dowiesz się:

  • Co to jest drzewo wyszukiwania binarnego?
  • Atrybuty drzewa wyszukiwania binarnego
  • Dlaczego potrzebujemy binarnego drzewa wyszukiwania?
  • Rodzaje drzew binarnych
  • Jak działa drzewo wyszukiwania binarnego?
  • Ważne terminy

Atrybuty drzewa wyszukiwania binarnego

BST składa się z wielu węzłów i składa się z następujących atrybutów:

  • 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 obecnych w lewym poddrzewie są mniejsze niż klucze ich węzła nadrzędnego
  • Podobnie, klucze węzłów lewego poddrzewa mają mniejsze wartości niż klucze ich węzłów nadrzędnych.

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

Dlaczego potrzebujemy binarnego drzewa wyszukiwania?

  • 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ść.
  • Ze względu na fakt, że wyszukiwanie binarne ma format rozgałęziony z relacjami rodzic-dziecko, algorytm wie, w której lokalizacji drzewa elementy mają być przeszukiwane. Zmniejsza to liczbę porównań klucz-wartość, które program musi wykonać, aby zlokalizować żądany element.
  • Dodatkowo, w przypadku gdy przeszukiwany element jest większy lub mniejszy niż węzeł nadrzędny, 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ń, niezawodnej logiki gry, działań autouzupełniania i grafiki.
  • Algorytm skutecznie 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 z 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 potomne z 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.

Jak działa drzewo wyszukiwania binarnego?

Drzewo zawsze ma węzeł główny i dalsze węzły potomne, 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 odpowiednio 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 łatwo usunąć lewe lub prawe poddrzewo węzła głównego.

BST oferuje przede wszystkim następujące trzy typy operacji do użytku:

  • Szukaj: przeszukuje element z drzewa binarnego
  • Wstaw: dodaje element do drzewa binarnego
  • Usuń: usuń element z drzewa binarnego

Każda operacja ma własną strukturę i metodę wykonywania / analizy, ale najbardziej złożona jest operacja Usuń.

Operacja wyszukiwania

Zawsze inicjuj 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 element, który ma być zlokalizowany, jest mniejszy lub większy od korzenia.

  1. Element do przeszukania to 10
  2. Porównaj element z węzłem głównym 12, 10 <12, stąd 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 poddrzewo potomne
  5. 10 pasuje do wartości w węźle, 10 = 10, zwraca wartość użytkownikowi.

Operacja wstawiania

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 niż root, jest dodawana do prawego poddrzewa, a jeśli jest mniejsza niż root, 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ść to jako prawe dziecko w wieku 12, 5 <12 i 5 <7, stąd umieść je jako lewe dziecko w wieku 7.
    1. Teraz porównaj 10, 10 to <12, a 10 to> 7, a 10 to> 9, umieść 10 jako prawe poddrzewo 9.

Usuń operacje

Usuwanie jest najbardziej zaawansowaną i złożoną spośród wszystkich innych operacji. W BST obsługiwanych jest wiele spraw do usunięcia.

  • Przypadek 1 - Węzeł bez dzieci: to jest najłatwiejsza sytuacja, wystarczy usunąć węzeł, który nie ma dalszych potomków po prawej ani po lewej stronie.
  • Przypadek 2 - Węzeł z jednym dzieckiem: po usunięciu węzła po prostu połącz jego węzeł podrzędny z węzłem nadrzędnym usuniętej wartości.
  • Przypadek 3 Węzeł z dwojgiem dzieci: to jest najtrudniejsza sytuacja i działa na następujących dwóch zasadach
    • 3a - W kolejności poprzednik: musisz usunąć węzeł z dwojgiem dzieci i zastąpić go największą wartością w lewym poddrzewie usuniętego węzła
    • 3b - W kolejności następca: należy usunąć węzeł z dwojgiem dzieci i zastąpić go największą wartością w prawym poddrzewie usuniętego węzła

  1. Jest to pierwszy przypadek usunięcia, w którym usuwasz węzeł, który nie ma dzieci. Jak widać na diagramie, 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 usuwasz węzeł, który ma 1 dziecko, jak widać na diagramie, że 9 ma jedno dziecko.
  2. Usuń węzeł 9 i zastąp go jego potomkiem 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 na podstawie poprzedniej reguły kolejności, co oznacza, że ​​największy element w lewym poddrzewie 12 zastąpi go.
  3. Usuń węzeł 12 i zastąp go 10, ponieważ jest to największa wartość w lewym poddrzewie
  4. Wyświetl 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 ​​największy element w prawym poddrzewie 12 zastąpi go
  3. 3 Usuń węzeł 12 i zastąp go 19, ponieważ jest to największa wartość w prawym poddrzewie
  4. 4 Wyświetl nową strukturę BST po usunięciu 12

Ważne terminy

  • Wstaw - wstawia element do drzewa / tworzy drzewo.
  • Szukaj - przeszukuje element w drzewie.
  • Preorder Traversal - przegląda drzewo w trybie zamówienia przedpremierowego.
  • Przechodzenie w kolejności - przechodzi przez drzewo w określonej kolejności.
  • Postorder Traversal - przechodzi przez drzewo w sposób po zamówieniu.

Podsumowanie

  • BST to zaawansowany algorytm, który wykonuje różne operacje na podstawie porównania 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, jedno lub dwoje dzieci.
  • Drzewo wyszukiwania binarnego ułatwia podstawowe operacje, takie jak wyszukiwanie, wstawianie i usuwanie.
  • Usuń jako najbardziej złożone ma wiele przypadków, na przykład węzeł bez dziecka, węzeł z jednym dzieckiem i węzeł z dwojgiem dzieci.
  • Algorytm jest używany w rzeczywistych rozwiązaniach, takich jak gry, dane autouzupełniania i grafika.