Implementacja binarnego drzewa wyszukiwania

2024 Autor: Angel Austin | [email protected]. Ostatnio zmodyfikowany: 2023-12-17 05:38

Drzewo wyszukiwania binarnego - ustrukturyzowana baza danych zawierająca węzły, dwa łącza do innych węzłów, prawe i lewe. Węzły są obiektem klasy, która ma dane, a NULL jest znakiem oznaczającym koniec drzewa.

To jest często określane jako BST, które ma specjalną właściwość: węzły większe niż korzeń znajdują się po jego prawej stronie, a mniejsze po lewej.

Ogólna teoria i terminologia

W drzewie wyszukiwania binarnego każdy węzeł, z wyjątkiem korzenia, jest połączony ukierunkowaną krawędzią z jednego węzła do drugiego, która jest nazywana rodzicem. Każdy z nich może być połączony z dowolną liczbą węzłów, zwanych dziećmi. Węzły bez „dzieci” nazywane są liśćmi (węzły zewnętrzne). Elementy, które nie są liśćmi, nazywane są wewnętrznymi. Węzły z tym samym rodzicem są rodzeństwem. Najwyższy węzeł nazywa się korzeniem. W BST przypisz element do każdego węzła i upewnij się, że mają dla niego ustawioną specjalną właściwość.

Terminologia dotycząca drzew:

1. Głębokość węzła to liczba krawędzi zdefiniowanych od nasady do niego.
2. Wysokość węzła to liczba krawędzi zdefiniowanych od niego do najgłębszego liścia.
3. Wysokość drzewa zależy od wysokości korzenia.
4. Drzewo wyszukiwania binarnego jest specjalną konstrukcją, zapewnia najlepszy stosunek wysokości do liczby węzłów.
5. Wysokość h z N węzłami co najwyżej O (log N).

Możesz to łatwo udowodnić, licząc węzły na każdym poziomie, zaczynając od korzenia, zakładając, że zawiera ich największą liczbę: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Rozwiązanie tego dla h daje h=O (log n).

Zalety drewna:

1. Odzwierciedlaj strukturalne zależności danych.
2. Służy do reprezentowania hierarchii.
3. Zapewnij wydajną instalację i wyszukiwanie.
4. Drzewa to bardzo elastyczne dane, umożliwiające przenoszenie poddrzew przy minimalnym wysiłku.

Metoda wyszukiwania

Ogólnie rzecz biorąc, aby określić, czy wartość znajduje się w BST, uruchom drzewo wyszukiwania binarnego u jego korzenia i określ, czy spełnia ono wymagania:

• być u podstaw;
• być w lewym poddrzewie korzenia;
• w prawym poddrzewie korzenia.

Jeżeli żaden rejestr bazowy nie jest spełniony, w odpowiednim poddrzewie przeprowadzane jest wyszukiwanie rekurencyjne. W rzeczywistości istnieją dwie podstawowe opcje:

1. Drzewo jest puste - zwróć fałszywe.
2. Wartość znajduje się w węźle głównym - zwróć prawdę.

Należy zauważyć, że drzewo wyszukiwania binarnego z rozwiniętym schematem zawsze rozpoczyna wyszukiwanie wzdłuż ścieżki od korzenia do liścia. W najgorszym przypadku dochodzi do liścia. Dlatego najgorszy czas jest proporcjonalny do długości najdłuższej drogi od korzenia do liścia, czyli do wysokości drzewa. Ogólnie rzecz biorąc, wtedy musisz wiedzieć, ile czasu zajmuje wyszukiwanie w funkcji liczby wartości przechowywanych w drzewie.

Innymi słowy, istnieje związek między liczbą węzłów w BST a wysokością drzewa, w zależności od jego „kształtu”. W najgorszym przypadku węzły mają tylko jedno dziecko, a zrównoważone drzewo wyszukiwania binarnego jest zasadniczo połączoną listą. Na przykład:

50

/

10

15

30

/

20

To drzewo ma 5 węzłów i wysokość=5. Znalezienie wartości z przedziału 16-19 i 21-29 będzie wymagało następującej ścieżki od korzenia do liścia (węzeł zawierający wartość 20), tj., zajmie to czas proporcjonalny do liczby węzłów. W najlepszym przypadku wszystkie mają 2 dzieci, a liście znajdują się na tej samej głębokości.

To drzewo wyszukiwania binarnego ma 7 węzłów i wysokość=3. Ogólnie, takie drzewo (pełne drzewo) będzie miało wysokość około log 2 (N), gdzie N jest liczbą węzłów w drzewie. Wartość log 2 (N) to liczba (2), kiedy N można podzielić przed osiągnięciem zera.

Podsumowanie: najgorszy czas potrzebny na wyszukiwanie w BST to O (wysokość drzewa). Najgorszym przypadkiem drzewa „liniowego” jest O(N), gdzie N jest liczbą węzłów w drzewie. W najlepszym przypadku „kompletne” drzewo to O(log N).

Wstaw binarny BST

Zastanawiasz się, gdzie powinno byćnowy węzeł znajduje się w BST, musisz zrozumieć logikę, musi być umieszczony tam, gdzie użytkownik go znajdzie. Dodatkowo musisz pamiętać o zasadach:

1. Duplikaty są niedozwolone, próba wstawienia zduplikowanej wartości spowoduje zgłoszenie wyjątku.
2. Publiczna metoda wstawiania używa rekurencyjnej metody „pomocnika” do faktycznego wstawiania.
3. Węzeł zawierający nową wartość jest zawsze wstawiany jako liść w BST.
4. Publiczna metoda wstawiania zwraca void, ale metoda pomocnicza zwraca BSTnode. Robi to, aby obsłużyć przypadek, w którym przekazany do niego węzeł ma wartość null.

Ogólnie rzecz biorąc, metoda pomocnicza wskazuje, że jeśli oryginalne drzewo wyszukiwania binarnego jest puste, wynikiem jest drzewo z jednym węzłem. W przeciwnym razie wynik będzie wskaźnikiem do tego samego węzła, który został przekazany jako argument.

Usunięcie w algorytmie binarnym

Jak można się spodziewać, usunięcie elementu polega na znalezieniu węzła zawierającego wartość do usunięcia. W tym kodzie jest kilka rzeczy:

1. BST używa pomocniczej, przeciążonej metody usuwania. Jeśli elementu, którego szukasz, nie ma w drzewie, metoda pomocnicza zostanie ostatecznie wywołana z n==null. Nie jest to uważane za błąd, drzewo po prostu się w tym przypadku nie zmienia. Metoda pomocnicza usuwania zwraca wartość - wskaźnik do zaktualizowanego drzewa.
2. Kiedy liść jest usuwany, usunięcie z drzewa wyszukiwania binarnego ustawia odpowiedni wskaźnik dziecka jego rodzica na null lub na null, jeśli usuwany jestwęzeł jest korzeniem i nie ma dzieci.
3. Zauważ, że wywołanie usuwania musi być jednym z następujących: root=delete (root, klucz), n.setLeft (delete (n.getLeft (), klucz)), n.setRight (delete(n. getRight(), klucz)). Tak więc we wszystkich trzech przypadkach poprawne jest, że metoda usuwania po prostu zwraca wartość null.
4. Gdy wyszukiwanie węzła zawierającego wartość do usunięcia powiedzie się, istnieją trzy opcje: węzeł do usunięcia jest liściem (nie ma dzieci), węzeł do usunięcia ma jedno dziecko, ma dwa dzieci.
5. Gdy usuwany węzeł ma jedno dziecko, możesz go po prostu zastąpić dzieckiem, zwracając wskaźnik do dziecka.
6. Jeżeli węzeł, który ma zostać usunięty, ma zero lub 1 dziecko, metoda usuwania będzie "podążać ścieżką" od korzenia do tego węzła. Zatem najgorszy czas jest proporcjonalny do wysokości drzewa, zarówno dla wyszukiwania, jak i wstawiania.

Jeśli węzeł do usunięcia ma dwoje dzieci, podejmowane są następujące kroki:

1. Znajdź węzeł do usunięcia, podążając ścieżką od korzenia do niego.
2. Znajdź najmniejszą wartość v w prawym poddrzewie, kontynuując ścieżką do liścia.
3. Rekursywnie usuń wartość v, podążaj tą samą ścieżką, jak w kroku 2.
4. Dlatego w najgorszym przypadku ścieżka od korzenia do liścia jest wykonywana dwukrotnie.

Kolejność trawersów

Traversal to proces, który odwiedza wszystkie węzły w drzewie. Ponieważ drzewo wyszukiwania binarnego w języku C jest nieliniową strukturą danych, nie ma unikatowego przechodzenia. Na przykład czasami kilka algorytmów przemierzaniapogrupowane w następujące dwa typy:

• głębokość przejścia;
• pierwsze przejście.

Istnieje tylko jeden rodzaj przechodzenia na szerokość - omijanie poziomu. To przejście odwiedza węzły poziomo w dół i w lewo, u góry i w prawo.

Istnieją trzy różne typy przepraw na głębokości:

1. Passing PreOrder - najpierw odwiedź rodzica, a następnie lewe i prawe dziecko.
2. Passing InOrder - odwiedzenie lewego dziecka, następnie rodzica i prawego dziecka.
3. Past the PostOrder - odwiedzenie lewego dziecka, potem prawego dziecka, potem rodzica.

Przykład czterech przejść w drzewie wyszukiwania binarnego:

1. Przedsprzedaż - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. Na zamówienie - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. PoziomKolejność - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Ilustracja pokazuje kolejność, w jakiej odwiedzane są węzły. Numer 1 to pierwszy węzeł w danym przejściu, a 7 to ostatni węzeł.

Te ogólne przechodzenie można przedstawić jako pojedynczy algorytm, zakładając, że każdy węzeł jest odwiedzany trzy razy. Trasa Euler to spacer po drzewie binarnym, w którym każda krawędź jest traktowana jako ściana, której użytkownik nie może przekroczyć. Podczas tego spaceru każdy węzeł będzie odwiedzany po lewej, poniżej lub po prawej stronie. Trasa Eulera, która odwiedza węzły po lewej stronie, powoduje ominięcie przyimka. Kiedy odwiedzane są poniższe węzły, są one przeszukiwane w kolejności. A kiedy odwiedzone zostaną węzły po prawej stronie - pobierzobejście krok po kroku.

Nawigacja i debugowanie

Aby ułatwić poruszanie się po drzewie, utwórz funkcje, które najpierw sprawdzają, czy są lewym czy prawym dzieckiem. Aby zmienić pozycję węzła, musi być łatwy dostęp do wskaźnika na węźle nadrzędnym. Prawidłowe zaimplementowanie drzewa jest bardzo trudne, dlatego musisz znać i stosować procesy debugowania. Drzewo wyszukiwania binarnego z implementacją często zawiera wskaźniki, które w rzeczywistości nie wskazują kierunku podróży.

Aby zrozumieć to wszystko, używana jest funkcja, która sprawdza, czy drzewo może być poprawne i pomaga znaleźć wiele błędów. Na przykład sprawdza, czy węzeł nadrzędny jest węzłem podrzędnym. Dziękiasset(is_wellformed(root)) wiele błędów może zostać wyłapanych przedwcześnie. Używając kilku podanych punktów przerwania w tej funkcji, możesz również określić, który wskaźnik jest zły.

Funkcja Konsolenausgabe

Ta funkcja opróżnia całe drzewo do konsoli i dlatego jest bardzo przydatna. Kolejność, w jakiej wykonywany jest cel wyjściowy drzewa, to:

1. Aby to zrobić, musisz najpierw określić, jakie informacje będą wyprowadzane przez węzeł.
2. Musisz także wiedzieć, jak szerokie i wysokie jest drzewo, aby uwzględnić ilość miejsca do pozostawienia.
3. Następujące funkcje obliczają te informacje dla drzewa i każdego poddrzewa. Ponieważ możesz pisać do konsoli tylko linia po linii, będziesz także musiał wydrukować drzewo linia po linii.
4. Teraz potrzebujemy innego sposobu na wypłatęcałe drzewo, a nie tylko linia po linii.
5. Za pomocą funkcji zrzutu możesz odczytać drzewo i znacznie poprawić algorytm wyjściowy, jeśli chodzi o szybkość.

Jednak ta funkcja będzie trudna w użyciu na dużych drzewach.

Kopiuj konstruktor i destruktor

Ponieważ drzewo nie jest banalną strukturą danych, lepiej zaimplementować konstruktor kopiujący, destruktor i operator przypisania. Destruktor można łatwo zaimplementować rekurencyjnie. W przypadku bardzo dużych drzew radzi sobie z „przepełnieniem hałdy”. W tym przypadku jest formułowany iteracyjnie. Pomysł polega na usunięciu liścia reprezentującego najmniejszą wartość ze wszystkich liści, tak aby znajdował się po lewej stronie drzewa. Odcięcie pierwszych liści tworzy nowe, a drzewo kurczy się, aż w końcu przestaje istnieć.

Konstruktor kopiujący można również zaimplementować rekursywnie, ale należy zachować ostrożność, jeśli zostanie zgłoszony wyjątek. W przeciwnym razie drzewo szybko staje się zagmatwane i podatne na błędy. Dlatego preferowana jest wersja iteracyjna. Pomysł polega na przejściu przez stare i nowe drzewo, tak jak w destruktorze, klonując wszystkie węzły znajdujące się w starym drzewie, ale nie nowe.

Dzięki tej metodzie implementacja drzewa wyszukiwania binarnego jest zawsze w dobrym stanie i może zostać usunięta przez destruktor nawet w stanie niekompletnym. Jeśli wystąpi wyjątek, wystarczy poinstruować destruktor, aby usunął częściowo ukończone drzewo. operator przypisaniamożna łatwo wdrożyć za pomocą funkcji Kopiuj i Zamień.

Tworzenie binarnego drzewa wyszukiwania

Optymalne drzewa wyszukiwania binarnego są niezwykle wydajne, jeśli są odpowiednio zarządzane. Niektóre zasady dla drzew wyszukiwania binarnego:

1. Węzeł nadrzędny ma maksymalnie 2 węzły podrzędne.
2. Lewy węzeł podrzędny jest zawsze mniejszy niż węzeł nadrzędny.
3. Prawidłowy węzeł podrzędny jest zawsze większy lub równy węzłowi nadrzędnemu.

Tabela, która zostanie użyta do zbudowania drzewa wyszukiwania binarnego:

1. Podstawowa tablica liczb całkowitych składająca się z siedmiu wartości w nieposortowanej kolejności.
2. Pierwsza wartość w tablicy to 10, więc pierwszym krokiem w budowaniu drzewa jest utworzenie węzła głównego o wartości 10, jak pokazano tutaj.
3. Z zestawem węzłów głównych wszystkie inne wartości będą dziećmi tego węzła. Odnosząc się do zasad, pierwszym krokiem, jaki należy podjąć, aby dodać 7 do drzewa, jest porównanie go z węzłem głównym.
4. Jeśli wartość 7 jest mniejsza niż 10, stanie się lewym węzłem podrzędnym.
5. Jeśli wartość 7 jest większa lub równa 10, przesunie się w prawo. Ponieważ wiadomo, że 7 jest mniejsze niż 10, jest on oznaczony jako lewy węzeł podrzędny.
6. Rekurencyjnie wykonuj porównania dla każdego elementu.
7. Podążając za tym samym wzorcem, wykonaj to samo porównanie z 14. wartością w tablicy.
8. Porównanie wartości 14 z węzłem głównym 10, wiedząc, że 14 jest poprawnym dzieckiem.
9. Przechodząc przez tablicę,przyjdź do 20.
10. Zacznij od porównania tablicy z liczbą 10, w zależności od tego, która wartość jest większa. Więc przejdź w prawo i porównaj to do 14, on ma ponad 14 lat i nie ma dzieci po prawej.
11. Teraz jest wartość 1. Podążając za tym samym wzorcem co inne wartości, porównaj 1 do 10, przesuwając się w lewo i porównując do 7 i wreszcie do 1 lewego dziecka 7. węzła.
12. Jeśli wartość wynosi 5, porównaj ją z 10. Ponieważ 5 jest mniejsze niż 10, przejdź w lewo i porównaj z 7.
13. Widząc, że 5 jest mniejsze niż 7, przejdź dalej w dół drzewa i porównaj 5 z 1 wartością.
14. Jeśli 1 nie ma dzieci, a 5 jest większe niż 1, to 5 jest prawidłowym dzieckiem 1 węzła.
15. Na koniec wstaw wartość 8 do drzewa.
16. Kiedy 8 jest mniejsze niż 10, przesuń je w lewo i porównaj z 7, 8 jest większe niż 7, więc przesuń je w prawo i uzupełnij drzewo, czyniąc 8 właściwym dzieckiem 7.

Pozyskiwanie i ocena prostej elegancji optymalnych drzew wyszukiwania binarnego. Podobnie jak w przypadku wielu tematów programowania, siła drzew wyszukiwania binarnego wynika z ich zdolności do rozwiązywania danych na małe, powiązane komponenty. Od teraz możesz pracować z pełnym zestawem danych w zorganizowany sposób.

Potencjalne problemy z wyszukiwaniem binarnym

Drzewa wyszukiwania binarnego są świetne, ale należy pamiętać o kilku zastrzeżeniach. Zwykle są skuteczne tylko wtedy, gdy są zrównoważone. Zrównoważone drzewo to drzewo, w którymróżnica między wysokościami poddrzew dowolnego węzła w drzewie wynosi co najwyżej jeden. Spójrzmy na przykład, który może pomóc wyjaśnić zasady. Wyobraźmy sobie, że tablica zaczyna się jako sortowalna.

Jeśli spróbujesz uruchomić algorytm drzewa wyszukiwania binarnego na tym drzewie, będzie on działał dokładnie tak, jakby po prostu iterował po tablicy, aż do znalezienia żądanej wartości. Siła wyszukiwania binarnego polega na możliwości szybkiego odfiltrowania niechcianych wartości. Gdy drzewo nie jest zrównoważone, nie zapewni takich samych korzyści jak drzewo zrównoważone.

Bardzo ważne jest zbadanie danych, z którymi pracuje użytkownik podczas tworzenia drzewa wyszukiwania binarnego. Możesz zintegrować procedury, takie jak randomizacja tablic, przed wdrożeniem binarnego drzewa wyszukiwania liczb całkowitych, aby je zrównoważyć.

Przykłady obliczeń wyszukiwania binarnego

Musimy określić, jaki rodzaj drzewa będzie wynikiem wstawienia 25 do następującego drzewa wyszukiwania binarnego:

10

/

/

5 15

/ /

/ /

2 12 20

Podczas wstawiania x do drzewa T, które jeszcze nie zawiera x, klucz x jest zawsze umieszczany w nowym liściu. W związku z tym nowe drzewo będzie wyglądało tak:

10

/

/

5 15

/ /

/ /

2 12 20

25

Jakie drzewo otrzymasz, jeśli wstawisz 7 do następującego drzewa wyszukiwania binarnego?

10

/

/

5 15

/ /

/ /

2 12 20

Odpowiedź:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

Drzewo wyszukiwania binarnego może służyć do przechowywania dowolnego obiektu. Zaletą korzystania z drzewa wyszukiwania binarnego zamiast połączonej listy jest to, że jeśli drzewo jest rozsądnie zrównoważone i bardziej przypomina drzewo „pełne” niż „liniowe”, można zaimplementować wstawianie, wyszukiwanie i wszystkie operacje usuwania do uruchomienia w Czas O(log N).