Samobalansujące drzewo wyszukiwania binarnego - Self-balancing binary search tree

Przykład niezrównoważonego drzewa; podążanie ścieżką od korzenia do węzła zajmuje średnio 3,27 dostępu do węzła

To samo drzewo po wyrównaniu wysokości; średni nakład pracy na ścieżce spadł do 3,00 dostępów do węzła

W informatyce , o samobalansujący binarne drzewo poszukiwań jest każdy węzeł -na binarne drzewo wyszukiwania automatycznie aktualizuje jego wysokość (maksymalna liczba poziomów poniżej korzenia) małe w obliczu arbitralnych wstawkami pozycji i skreśleń. Operacje te, gdy są zaprojektowane dla samorównoważącego się drzewa wyszukiwania binarnego, zawierają środki ostrożności zapobiegające bezgranicznie rosnącej wysokości drzewa, dzięki czemu te abstrakcyjne struktury danych otrzymują atrybut „samobalansujący”.

W przypadku drzew binarnych o zrównoważonej wysokości wysokość jest definiowana jako logarytmiczna w liczbie elementów. Tak jest w przypadku wielu binarnych drzew wyszukiwania, takich jak drzewa AVL i czerwono-czarne – te ostatnie nazwano symetrycznym binarnym drzewem B i zmieniono jego nazwę; można go jednak nadal mylić z ogólną koncepcją samobalansującego drzewa wyszukiwania binarnego ze względu na inicjały. ${\ Displaystyle {\ mathcal {O}} (\ log n)}$ ${\ Displaystyle n}$

Ale drzewa Splay i Treaps są również uważane za samobalansujące , chociaż ich wysokość nie gwarantuje logarytmicznej liczby przedmiotów.

Samobalansujące się drzewa binarnego wyszukiwania zapewniają wydajne implementacje mutowalnych uporządkowanych list i mogą być używane do innych abstrakcyjnych struktur danych, takich jak tablice asocjacyjne , kolejki priorytetowe i zbiory .

Przegląd

Rotacje drzew są bardzo powszechnymi operacjami wewnętrznymi na samobalansujących drzewach binarnych, aby zachować idealną lub prawie idealną równowagę.

Większość operacji na drzewie wyszukiwania binarnego (BST) zajmuje czas wprost proporcjonalny do wysokości drzewa, dlatego pożądane jest, aby wysokość była mała. Drzewo binarne o wysokości h może zawierać co najwyżej 2 ⁰ +2 ¹ +···+2 ^h = 2 ^{h +1} −1 węzłów. Wynika z tego, że dla każdego drzewa o n węzłach i wysokości h :

{\ Displaystyle n \ równoważnik 2 ^ {h + 1} -1}

A to oznacza:

{\ Displaystyle h \ geq \ lceil \ log _ {2} (n + 1) -1 \ rceil \ geq \ l podłoga \ log _ {2} n \ r podłoga}

.

Innymi słowy, minimalna wysokość drzewa binarnego z n węzłami to log ₂ ( n ), zaokrąglona w dół ; czyli . $\lpodłoga \log_{2}n\rpodłoga$

Jednak najprostsze algorytmy wstawiania elementów BST mogą dać drzewo o wysokości n w dość powszechnych sytuacjach. Na przykład, gdy elementy są wstawiane w posortowanej kluczowego porządku, degeneratów drzewo w połączonej listy z n węzłach. Różnica w wydajności między tymi dwiema sytuacjami może być ogromna: na przykład, gdy n = 1 000 000, minimalna wysokość wynosi . $\lpodłoga \log_{2}(1 000 000)\rpodłoga =19$

Jeśli elementy danych są znane z wyprzedzeniem, wysokość można utrzymać na niskim poziomie, w średnim sensie, dodając wartości w losowej kolejności, co daje losowe drzewo wyszukiwania binarnego . Istnieje jednak wiele sytuacji (takich jak algorytmy online ), w których taka randomizacja nie jest opłacalna.

Samobalansujące drzewa binarne rozwiązują ten problem, wykonując przekształcenia na drzewie (takie jak rotacje drzewa ) w czasie wstawiania klucza, aby zachować wysokość proporcjonalną do log ₂ ( n ). Chociaż w grę wchodzi pewien narzut , nie jest on większy niż zawsze niezbędny koszt wyszukiwania i może być uzasadniony zapewnieniem szybkiego wykonania wszystkich operacji.

Chociaż możliwe jest utrzymanie BST o minimalnej wysokości z oczekiwanymi operacjami czasowymi (wyszukiwanie/wstawianie/usuwanie), dodatkowe wymagania przestrzenne wymagane do utrzymania takiej struktury zwykle przeważają nad skróceniem czasu wyszukiwania. Dla porównania, drzewo AVL gwarantuje czynnik 1,44 optymalnej wysokości, wymagając tylko dwóch dodatkowych bitów pamięci w naiwnej implementacji. Dlatego większość samobalansujących algorytmów BST utrzymuje wysokość w stałym współczynniku tej dolnej granicy. ${\ Displaystyle O (\ log n)}$

W sensie asymptotycznym („ Big-O ”) samobalansująca struktura BST zawierająca n elementów umożliwia wyszukiwanie, wstawianie i usuwanie elementu w czasie najgorszego przypadku O(log n ) oraz uporządkowane wyliczenie wszystkich elementów w O( n ) czas. W przypadku niektórych implementacji są to granice czasu na operację, podczas gdy dla innych są to granice amortyzacji w sekwencji operacji. Te czasy są asymptotycznie optymalne wśród wszystkich struktur danych, które manipulują kluczem tylko poprzez porównania.

Realizacje

Struktury danych implementujące ten typ drzewa obejmują:

Aplikacje

Samobalansujące drzewa wyszukiwania binarnego mogą być używane w naturalny sposób do konstruowania i utrzymywania uporządkowanych list, takich jak kolejki priorytetowe . Mogą być również używane do tablic asocjacyjnych ; pary klucz-wartość są po prostu wstawiane z kolejnością opartą na samym kluczu. Pod tym względem samobalansujące tabele BST mają szereg zalet i wad w porównaniu z ich głównym konkurentem, tablicami mieszającymi . Jedną z zalet samobilansujących się tabel BST jest to, że umożliwiają szybkie (w istocie asymptotycznie optymalne) wyliczanie pozycji w kolejności kluczy , czego nie zapewniają tabele mieszające. Jedną wadą jest to, że ich algorytmy wyszukiwania stają się bardziej skomplikowane, gdy może istnieć wiele elementów z tym samym kluczem. Samobalansujące tabele BST mają lepszą wydajność wyszukiwania najgorszego przypadku niż tabele mieszające (O (log n) w porównaniu z O (n)), ale mają gorszą wydajność w przypadku średniej wielkości (O (log n) w porównaniu z O (1)).

Samobalansujące BST można wykorzystać do implementacji dowolnego algorytmu, który wymaga mutowalnych uporządkowanych list, aby osiągnąć optymalną wydajność asymptotyczną w najgorszym przypadku. Na przykład, jeśli sortowanie drzewa binarnego jest zaimplementowane z samobalansującym BST, mamy bardzo prosty do opisania, ale asymptotycznie optymalny algorytm sortowania O( n log n ). Podobnie wiele algorytmów w geometrii obliczeniowej wykorzystuje wariacje samobalansujących się BST w celu efektywnego rozwiązywania problemów, takich jak problem przecięcia odcinka linii i problem lokalizacji punktu . (Jednakże w przypadku przeciętnej wydajności, samobalansujące BST mogą być mniej wydajne niż inne rozwiązania. W szczególności sortowanie drzewa binarnego jest prawdopodobnie wolniejsze niż merge sort , quicksort lub heapsort , ze względu na obciążenie równoważenia drzewa, ponieważ jak również wzorce dostępu do pamięci podręcznej ).

Samobalansujące BST są elastycznymi strukturami danych, dzięki czemu można je łatwo rozszerzyć w celu efektywnego rejestrowania dodatkowych informacji lub wykonywania nowych operacji. Na przykład można zarejestrować liczbę węzłów w każdym poddrzewie o określonej właściwości, co pozwala policzyć liczbę węzłów w określonym zakresie kluczy z tą właściwością w czasie O(log n ). Rozszerzenia te mogą być używane na przykład do optymalizacji zapytań do bazy danych lub innych algorytmów przetwarzania list.

Zobacz też

Bibliografia

Zewnętrzne linki

Słownik algorytmów i struktur danych: drzewo wyszukiwania binarnego o zrównoważonym wysokości
GNU libavl , licencjonowana przez LGPL biblioteka implementacji drzewa binarnego w C, z dokumentacją

Languages

In other projects