binarne drzewa wyszukiwania obsługują trzy główne operacje: wstawianie elementów, usuwanie elementów i wyszukiwanie (sprawdzanie, czy klucz jest obecny).
SearchingEdit
wyszukiwanie w drzewie binarnym dla określonego klucza może być programowane rekurencyjnie lub iteracyjnie.
zaczynamy od zbadania węzła głównego. Jeśli drzewo ma wartość null, klucz, którego szukamy, nie istnieje w drzewie. W przeciwnym razie, jeśli klucz jest równy kluczowi root, wyszukiwanie zakończy się sukcesem i zwracamy węzeł. Jeśli klucz jest mniejszy niż klucz główny, przeszukujemy lewy podzbiór., Podobnie, jeśli klucz jest większy niż klucz główny, przeszukujemy właściwy podzbiór. Proces ten jest powtarzany, dopóki klucz nie zostanie znaleziony lub pozostałym podzbiorem nie będzie null. Jeśli szukany klucz nie zostanie znaleziony po osiągnięciu poddrzewa null, wtedy klucz nie jest obecny w drzewie. Jest to łatwo wyrażone jako algorytm rekurencyjny (zaimplementowany w Pythonie):
ten sam algorytm może być zaimplementowany iteracyjnie:
te dwa przykłady nie obsługują duplikatów, to znaczy polegają na tym, że relacja kolejności jest całkowitą kolejnością.
można zauważyć, że algorytm rekurencyjny jest rekurencyjny., W języku wspierającym optymalizację wywołań ogonowych, rekurencyjne i iteracyjne przykłady będą kompilowane do równoważnych programów.
ponieważ w najgorszym przypadku algorytm ten musi przeszukiwać od korzenia drzewa do liścia najdalej od korzenia, operacja wyszukiwania trwa proporcjonalnie do wysokości drzewa (patrz terminologia drzewa). Średnio drzewa wyszukiwania binarnego z kluczami węzłów mają wysokość O(log |Nodes|). Jednak w najgorszym przypadku drzewa wyszukiwania binarnego mogą mieć wysokość O(|Nodes|), gdy drzewo niezrównoważone przypomina listę połączoną (drzewo zdegenerowane).,
wyszukiwanie za pomocą duplikatów dozwolonychedytuj
jeśli relacja order jest tylko całkowitym preorderem, rozsądnym rozszerzeniem funkcjonalności jest: również w przypadku równości szukaj w dół do list. W ten sposób pozwala określić (lub twardego drutu) kierunek, w którym wstawić duplikat, albo po prawej lub lewej stronie wszystkich duplikatów w drzewie do tej pory. Jeśli kierunek jest sztywny, obie opcje, w prawo i w lewo, obsługują stos z insert duplicate jako operacja push I delete jako operacja pop.,:155
sortowanie drzewa binarnego wyposażone w taką funkcję wyszukiwania staje się stabilne.
InsertionEdit
Wstawianie rozpoczyna się w momencie rozpoczęcia Wyszukiwania; jeśli klucz nie jest równy kluczowi root, przeszukujemy lewe lub prawe podzbiory jak poprzednio. Ostatecznie dotrzemy do zewnętrznego węzła i dodamy nową parę klucz-wartość (tutaj zakodowaną jako rekord 'newNode') jako jego prawe lub lewe dziecko, w zależności od klucza węzła., Innymi słowy, badamy root i rekurencyjnie wstawiamy nowy węzeł do lewego poddrzewa, jeśli jego klucz jest mniejszy niż klucz roota, lub do prawego poddrzewa, jeśli jego klucz jest większy lub równy rootowi.
oto jak typowe wstawianie binarnego drzewa wyszukiwania może być wykonywane w drzewie binarnym w C++:
alternatywnie, wersja nie rekurencyjna może być zaimplementowana w ten sposób., Użycie wskaźnika-do-wskaźnika do śledzenia tego, skąd przybyliśmy pozwala kodowi uniknąć jawnego sprawdzania i obsługi przypadku, w którym musi wstawić węzeł w korzeniu drzewa:
powyższy destrukcyjny wariant proceduralny modyfikuje drzewo w miejscu. Używa tylko stałej przestrzeni stosu( a wersja iteracyjna również używa stałej przestrzeni stosu), ale poprzednia wersja drzewa jest tracona., Alternatywnie, jak w poniższym przykładzie Pythona, możemy zrekonstruować wszystkich przodków wstawionego węzła; wszelkie odniesienia do oryginalnego korzenia drzewa pozostają ważne, czyniąc drzewo trwałą strukturą danych:
część, która jest przebudowywana, używa przestrzeni o(log n) w średnim przypadku I O(n) w najgorszym przypadku.
w obu wersjach operacja ta wymaga czasu proporcjonalnego do wysokości drzewa w najgorszym przypadku, który jest O(log n) czas w średnim przypadku dla wszystkich drzew, ale O(N) czas w najgorszym przypadku.,
innym sposobem wyjaśnienia wstawiania jest to, że aby wstawić nowy węzeł w drzewie, jego klucz jest najpierw porównywany z kluczem korzenia. Jeśli jego klucz jest mniejszy od klucza roota, jest on porównywany z kluczem lewego potomka roota. Jeśli jego klucz jest większy, jest porównywany z prawym dzieckiem roota. Proces ten trwa, dopóki nowy węzeł nie zostanie porównany z węzłem liścia, a następnie zostanie dodany jako prawy lub lewy potomek tego węzła, w zależności od jego klucza: jeśli klucz jest mniejszy niż klucz liścia, to jest wstawiany jako lewy potomek liścia, w przeciwnym razie jako prawy potomek liścia.,
istnieją inne sposoby wstawiania węzłów do drzewa binarnego, ale jest to jedyny sposób wstawiania węzłów w liściach i jednocześnie zachowania struktury BST.
DeletionEdit
podczas usuwania węzła z binarnego drzewa wyszukiwania obowiązkowe jest zachowanie kolejności węzłów. Istnieje wiele możliwości, aby to zrobić. Jednak następująca metoda zaproponowana przez T. Hibbarda w 1962 gwarantuje, że wysokość subtreów przedmiotu zmienia się co najwyżej o jedną., Istnieją trzy możliwe przypadki do rozważenia:
- usuwanie węzła bez dzieci: po prostu Usuń węzeł z drzewa.
- usuwanie węzła z jednym potomkiem: Usuń węzeł i zastąp go jego potomkiem.
- usunięcie węzła D z dwójką dzieci: wybierz poprzednika D lub następcę E (patrz rysunek). Zamiast usuwać D, Nadpisz jego klucz i wartość E. Jeśli E nie ma potomka, Usuń E z poprzedniego rodzica G. Jeśli E ma potomka F, jest to właściwe dziecko, więc ma zastąpić e na rodzicu e.,
usuwanie węzła z dwójką dzieci z binarnego drzewa wyszukiwania. Najpierw identyfikowany jest najbardziej lewy węzeł w prawym poddrzewie, następca rzędu E. Jego wartość jest kopiowana do usuniętego węzła D. Następcę w kolejności można następnie łatwo usunąć, ponieważ ma co najwyżej jedno dziecko. Ta sama metoda działa symetrycznie przy użyciu poprzednika C.
we wszystkich przypadkach, gdy D stanie się korzeniem, Utwórz ponownie korzeń węzła zastępczego.
węzły z dwójką dzieci są trudniejsze do usunięcia., Następcą węzła w kolejności jest jego prawe poddrzewo-lewe-most child, a poprzednikiem węzła w kolejności jest prawe poddrzewo-prawe-most child. W obu przypadkach węzeł ten będzie miał tylko jedno dziecko lub w ogóle go nie będzie. Usunąć zgodnie z jednym z dwóch prostszych przypadków powyżej.
konsekwentne używanie następcy w kolejności lub poprzednika w kolejności dla każdej instancji sprawy dwudziesty może prowadzić do niesymetrycznego drzewa, więc niektóre implementacje wybierają jedną lub drugą w różnym czasie.,
Analiza Runtime: chociaż ta operacja nie zawsze trawersuje drzewo w dół do liścia, zawsze jest to możliwe; dlatego w najgorszym przypadku wymaga czasu proporcjonalnego do wysokości drzewa. Nie wymaga więcej nawet wtedy, gdy węzeł ma dwoje dzieci, ponieważ nadal podąża jedną ścieżką i nie odwiedza żadnego węzła dwa razy.,
TraversalEdit
Po utworzeniu binarnego drzewa wyszukiwania, jego elementy mogą być pobierane w kolejności przez rekurencyjne przemierzanie lewego poddrzewa węzła głównego, dostęp do samego węzła, a następnie rekurencyjnie przemierzanie prawego poddrzewa węzła, kontynuując ten wzór z każdym węzłem w drzewie, jak to jest rekurencyjnie dostępne. Podobnie jak w przypadku wszystkich drzew binarnych, można przeprowadzić Trawers przed zamówieniem lub Trawers po zamówieniu, ale żadne z nich nie może być użyteczne dla drzew wyszukiwania binarnego., Przejście w kolejności binarnego drzewa wyszukiwania zawsze spowoduje posortowanie listy elementów węzła (liczb, łańcuchów lub innych porównywalnych elementów).
kod dla przesiadki w Pythonie jest podany poniżej. Wywoła ona callback (niektóre funkcje, które programista chce wywołać na wartość węzła, takie jak drukowanie na ekranie) dla każdego węzła w drzewie.
Traversal wymaga czasu O(n), ponieważ musi odwiedzać każdy węzeł. Algorytm ten jest również O (n), więc jest asymptotycznie optymalny.
Traversal może być również zaimplementowany iteracyjnie. Do niektórych zastosowań, np., większe wyszukiwanie równe, wyszukiwanie przybliżone, operacja pojedynczego kroku (iteracyjnego) może być bardzo przydatna. Jest to oczywiście zaimplementowane bez konstrukcji wywołania zwrotnego i przyjmuje średnio O(1) i o(log n) w najgorszym przypadku.
VerificationEdit
czasami mamy już drzewo binarne i musimy ustalić, czy jest to BST. Problem ten ma proste rekurencyjne rozwiązanie.,
właściwość BST—każdy węzeł po prawej podstrze musi być większy od bieżącego węzła i każdy węzeł po lewej podstrze musi być mniejszy od bieżącego węzła-jest kluczem do ustalenia, czy drzewo jest BST, czy nie. Algorytm chciwy-po prostu przemierzaj drzewo, na każdym węźle sprawdzaj, czy węzeł zawiera wartość większą niż wartość w lewym potomku i mniejszą niż wartość w prawym potomku—nie działa we wszystkich przypadkach., Rozważ następujące drzewo:
20 / \ 10 30 / \ 5 40
w powyższym drzewie każdy węzeł spełnia warunek, że węzeł zawiera wartość większą niż jego lewy potomek i mniejszą niż jego prawy potomek, a mimo to nie jest BST: wartość 5 znajduje się na prawym poddrzewie węzła zawierającego 20, co stanowi naruszenie właściwości BST.
zamiast podejmować decyzje wyłącznie w oparciu o wartości węzła i jego dzieci, potrzebujemy również informacji płynących z rodzica., W przypadku drzewa powyżej, gdybyśmy mogli pamiętać o węźle zawierającym wartość 20, zauważylibyśmy, że węzeł o wartości 5 narusza umowę własności BST.,
warunek, który musimy sprawdzić w każdym węźle to:
- jeśli węzeł jest lewym potomkiem swojego rodzica, to musi być mniejszy (lub równy) rodzicowi i musi przekazać wartość z rodzica do prawego poddrzewa, aby upewnić się, że żaden z węzłów w tym poddrzewu nie jest większy niż rodzic
- jeśli węzeł jest Prawym potomkiem swojego rodzica, to musi być większy niż rodzic I musi przekazać wartość z rodzica do lewego poddrzewa do prawego poddrzewa.upewnij się, że żaden z węzłów w tym poddrzewie nie jest mniejszy niż rodzic.,
rozwiązanie rekurencyjne w C++ może wyjaśnić to dalej:
node->key+1 Inode->key-1 są wykonywane, aby zezwalać tylko na różne elementy w BST.
Jeśli chcemy, aby te same elementy były obecne, możemy używać tylkonode->key w obu miejscach.
początkowe wywołanie tej funkcji może wyglądać następująco:
if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}
zasadniczo tworzymy poprawny zakres (zaczynając od ) i zmniejszamy go dla każdego węzła, gdy schodzimy rekurencyjnie.,
jak wspomniano w sekcji #Traversal, przejście w kolejności binarnego drzewa wyszukiwania zwraca węzły posortowane. Tak więc musimy tylko zachować ostatni odwiedzony węzeł podczas przechodzenia przez drzewo i sprawdzić, czy jego klucz jest mniejszy (lub mniejszy/równy, jeśli duplikaty mają być dozwolone w drzewie) w porównaniu do bieżącego klucza.
algorytmy Równoległeedytuj
istnieją również algorytmy równoległe dla binarnych drzew wyszukiwania, w tym wstawianie/usuwanie wielu elementów, Budowa z tablicy, filtrowanie z określonym predykatorem, spłaszczanie do tablicy, łączenie/odejmowanie / przecinanie dwóch drzew itp., Algorytmy te mogą być zaimplementowane przy użyciu algorytmów join-based tree, które mogą również utrzymać równowagę drzewa za pomocą kilku schematów równoważenia (w tym AVL tree, red-black tree, weight-balanced tree i treap).