Co to jest drzewo wyszukiwania binarnego?

Drzewo wyszukiwania binarnego to jedna z różnych struktur danych, które pomagają nam organizować i sortować dane. Jest to wydajny sposób przechowywania danych w hierarchii i jest bardzo elastyczny.

W tym artykule przyjrzymy się bliżej jego działaniu — wraz z jego właściwościami i zastosowaniami.

Co to jest drzewo wyszukiwania binarnego?

Drzewo wyszukiwania binarnego to struktura danych składająca się z węzłów — podobna do połączonych list. Mogą istnieć dwa typy węzłów: rodzic i dziecko. Węzeł główny jest punktem początkowym struktury rozgałęziającej się na dwa węzły potomne, zwane węzłem lewym i węzłem prawym.

Do każdego węzła może odnosić się tylko jego rodzic, a my możemy przeszukiwać węzły drzewa w zależności od kierunku. Drzewo wyszukiwania binarnego ma trzy główne właściwości:

1. Lewy węzeł jest mniejszy niż jego rodzic.
2. Prawy węzeł jest większy niż jego rodzic.
3. Lewe i prawe poddrzewa muszą być binarnymi drzewami wyszukiwania.

Doskonałe drzewo wyszukiwania binarnego uzyskuje się, gdy wszystkie poziomy są wypełnione, a każdy węzeł ma lewy i prawy węzeł podrzędny.

Związane z: Biblioteki Data Science dla Pythona, których powinien używać każdy analityk danych

Podstawowe operacje na drzewie wyszukiwania binarnego

Teraz masz lepsze pojęcie o tym, czym jest drzewo wyszukiwania binarnego, poniżej możemy przyjrzeć się jego podstawowym operacjom.

1. Operacja wyszukiwania

Wyszukiwanie pozwala nam zlokalizować konkretną wartość obecną w drzewie. Możemy użyć dwóch typów wyszukiwania: przeszukiwania wszerz (BFS) i przeszukiwania w głąb (DFS). Wyszukiwanie wszerz to algorytm wyszukiwania, który rozpoczyna się w węźle głównym i przebiega poziomo, na boki, aż do znalezienia celu. Każdy węzeł jest odwiedzany raz podczas tego wyszukiwania.

Z drugiej strony, przeszukiwanie według głębokości przebiega przez drzewo pionowo — zaczynając od węzła głównego i przechodząc w dół pojedynczej gałęzi. Jeśli cel zostanie znaleziony, operacja się kończy. Ale jeśli nie, to i przeszukuje inne węzły.

2. Operacja wstawiania

Operacja wstawiania wykorzystuje operację wyszukiwania do określenia lokalizacji, w której należy wstawić nowy węzeł. Proces rozpoczyna się od węzła głównego, a wyszukiwanie rozpoczyna się aż do osiągnięcia celu. Przy wstawianiu należy wziąć pod uwagę trzy przypadki.

• Przypadek 1: Gdy żaden węzeł nie istnieje. Wstawiany węzeł stanie się węzłem głównym.

• Przypadek 2: Nie ma dzieci. W takim przypadku węzeł zostanie porównany z węzłem głównym. Jeśli jest większy, stanie się właściwym dzieckiem; w przeciwnym razie stanie się lewym dzieckiem.

• Przypadek 3: Kiedy korzeń i jego dzieci są obecne. Nowy węzeł zostanie porównany z każdym węzłem na swojej ścieżce, aby określić, który węzeł odwiedza jako następny. Jeśli węzeł jest większy niż węzeł główny, przejdzie w dół prawego poddrzewa lub w lewo. Podobnie dokonuje się porównań na każdym poziomie, aby określić, czy będzie szedł w prawo, czy w lewo, aż dotrze do celu.

3. Usuń operację

Operacja usuwania służy do usuwania określonego węzła w drzewie. Usunięcie jest uważane za trudne, ponieważ po usunięciu węzła drzewo musi zostać odpowiednio zreorganizowane. Należy wziąć pod uwagę trzy główne przypadki:

• Przypadek 1: Usunięcie węzła liścia. Węzeł liścia to węzeł bez dzieci. Jest to najłatwiejsze do usunięcia, ponieważ nie wpływa na żaden inny węzeł; po prostu przemierzamy drzewo, aż do niego dotrzemy i je usuniemy.

• Przypadek 2: Usunięcie węzła z jednym dzieckiem. Usunięcie rodzica z jednym węzłem spowoduje, że dziecko zajmie jego pozycję, a wszystkie kolejne węzły przesuną się o poziom wyżej. Nie będzie zmian w strukturze poddrzewa.

• Przypadek 3: Usunięcie węzła z dwójką dzieci. Kiedy musimy usunąć węzeł z dwójką dzieci, musimy najpierw znaleźć kolejny węzeł, który może zająć jego pozycję. Dwa węzły mogą zastąpić usunięty węzeł, następcę lub poprzednika w kolejności. Następca w kolejności jest najbardziej wysuniętym na lewo dzieckiem prawego poddrzewa, a poprzednik w kolejności jest najbardziej wysuniętym na prawo dzieckiem lewego poddrzewa. Kopiujemy zawartość następcy/poprzednika do węzła i usuwamy następcę/poprzednika w kolejności.

Związane z: Jak budować struktury danych za pomocą klas JavaScript ES6?

Jak przeszukiwać drzewo wyszukiwania binarnego

Przemierzanie to proces, przez który poruszamy się po drzewie wyszukiwania binarnego. Odbywa się to w celu zlokalizowania określonej pozycji lub wydrukowania zarysu drzewa. Zawsze zaczynamy od węzła głównego i musimy podążać za krawędziami, aby dostać się do innych węzłów. Każdy węzeł powinien być traktowany jako poddrzewo, a proces jest powtarzany, aż wszystkie węzły zostaną odwiedzone.

• Przechodzenie na zamówienie: Przemierzanie w kolejności spowoduje utworzenie mapy w kolejności rosnącej. W tej metodzie zaczynamy od lewego poddrzewa i przechodzimy do głównego i prawego poddrzewa.

• Przechodzenie w przedsprzedaży: W tej metodzie najpierw odwiedzany jest węzeł główny, a następnie lewe poddrzewo i prawe poddrzewo.

• Przechodzenie po zamówieniu: To przechodzenie obejmuje odwiedzenie węzła głównego jako ostatniego. Zaczynamy od lewego poddrzewa, następnie prawego poddrzewa, a następnie węzła głównego.

Aplikacje w świecie rzeczywistym

Jak więc wykorzystujemy algorytmy drzewa wyszukiwania binarnego? Jak można przypuszczać, są one niezwykle skuteczne w wyszukiwaniu i sortowaniu. Największą siłą drzew binarnych jest ich zorganizowana struktura. Umożliwia wyszukiwanie z niezwykłą szybkością, zmniejszając ilość danych, które potrzebujemy do analizy, o połowę na przebieg.

Drzewa wyszukiwania binarnego pozwalają nam skutecznie utrzymywać dynamicznie zmieniający się zestaw danych w zorganizowanej formie. W przypadku aplikacji, w których dane są często wstawiane i usuwane, są one bardzo pomocne. Silniki gier wideo używają algorytmu opartego na drzewach znanego jako binarna partycja przestrzeni, aby pomóc w uporządkowanym renderowaniu obiektów. Microsoft Excel i większość oprogramowania do arkuszy kalkulacyjnych wykorzystuje drzewa binarne jako podstawową strukturę danych.

Możesz być zaskoczony, wiedząc, że kod Morse'a używa drzewa wyszukiwania binarnego do kodowania danych. Innym ważnym powodem, dla którego drzewa wyszukiwania binarnego są tak przydatne, jest ich wiele odmian. Ich elastyczność doprowadziła do powstania wielu wariantów do rozwiązywania wszelkiego rodzaju problemów. Przy odpowiednim użyciu drzewa wyszukiwania binarnego są wielkim atutem.

Drzewa wyszukiwania binarnego: idealny punkt wyjścia

Jednym z głównych sposobów oceny wiedzy inżyniera jest znajomość i zastosowanie struktur danych. Struktury danych są pomocne i mogą pomóc w stworzeniu wydajniejszego systemu. Drzewa wyszukiwania binarnego to świetne wprowadzenie do struktur danych dla każdego początkującego programisty.

15 metod macierzy JavaScript, które powinieneś opanować już dziś

Chcesz zrozumieć tablice JavaScript, ale nie możesz się z nimi uporać? Zapoznaj się z naszymi przykładami tablic JavaScript, aby uzyskać wskazówki.

Czytaj dalej

O autorze