Drzewo WAVL

W informatyce drzewo WAVL lub słabe drzewo AVL jest samobalansującym się drzewem wyszukiwania binarnego . Drzewa WAVL zostały nazwane na cześć drzew AVL , innego rodzaju zrównoważonego drzewa wyszukiwania i są blisko spokrewnione zarówno z drzewami AVL, jak i drzewami czerwono-czarnymi , które wszystkie mieszczą się we wspólnej strukturze drzew zrównoważonych rangowo . Podobnie jak inne zrównoważone drzewa wyszukiwania binarnego, drzewa WAVL mogą obsługiwać operacje wstawiania, usuwania i wyszukiwania w czasie $O (log n)$ na operację.

Drzewa WAVL zostały zaprojektowane tak, aby łączyć jedne z najlepszych właściwości obu drzew AVL i drzew czerwono-czarnych. Jedną z zalet drzew AVL w porównaniu z drzewami czerwono-czarnymi jest to, że są bardziej zrównoważone: mają co najwyżej wysokość ${\ Displaystyle \ log _ {\ varphi} n \ około 1,44 \ log _ {2} n}$ (dla drzewa z $n$ elementami danych, gdzie jest złotym podziałem $)$ , podczas gdy czerwono-czarne drzewa mają większą maksymalną wysokość ${\ Displaystyle 2 \ log _ {2} n}$ . Jeśli drzewo WAVL jest tworzone tylko przy użyciu wstawiania, bez usuwania, to ma takie samo ograniczenie wysokości, jak drzewo AVL. Z drugiej strony drzewa czerwono-czarne mają przewagę nad drzewami AVL w mniejszej restrukturyzacji swoich drzew. W drzewach AVL każde usunięcie może wymagać logarytmicznej liczby obracania drzewa , podczas gdy drzewa czerwono-czarne mają prostsze operacje usuwania, które wykorzystują tylko stałą liczbę obrotów drzewa. Drzewa WAVL, podobnie jak drzewa czerwono-czarne, wykorzystują tylko stałą liczbę rotacji drzew, a stała jest nawet lepsza niż w przypadku drzew czerwono-czarnych.

Drzewa WAVL zostały wprowadzone przez Haeuplera, Sen i Tarjana (2015) . Ci sami autorzy przedstawili również wspólny pogląd, że drzewa AVL, drzewa WAVL i drzewa czerwono-czarne są rodzajem drzewa o zrównoważonej randze.

Ramy zrównoważonych drzew rangi

Różne drzewa wyszukiwania binarnego mają różne algorytmy wstawiania/usuwania i algorytmy równoważenia, co utrudnia systematyczne badania. Autorzy Haeupler, Sen & Tarjan (2015) wprowadzają strukturę drzew zrównoważonych rangą w celu ujednolicenia badania drzewa wyszukiwania binarnego poprzez zdefiniowanie drzewa binarnego rangi, a każde drzewo wyszukiwania binarnego podlega określonym ograniczeniom zastosowanym do funkcji rangi. Należy zauważyć, że struktura nie określa algorytmów, w których te drzewa są implementowane.

Rankingowe drzewo binarne to drzewo binarne, w którym każdy węzeł x jest powiązany z rangą r(x). Zgodnie z konwencją pusty węzeł ma rangę -1. Dla węzła x, który nie jest korzeniem, różnica rang wynosi ${\ Displaystyle r (p (x)) -r (x)}$ , a taki węzeł nazywa się i-dziecko, jeśli różnica rang wynosi i. Węzeł jest typu ${\ displaystyle i, j}$ jeśli różnica rang jego lewego i prawego dziecka wynosi i oraz j (pomijając kolejność).

Dzięki temu możemy zdefiniować dodatkowe reguły, które odpowiadają różnym drzewom:

Reguła AVL, która odpowiada drzewu AVL : każdy węzeł jest typu 1,1 lub 1,2.
Reguła 2-3, która odpowiada zbinaryzowanemu drzewu 2-3: każdy węzeł jest typu 0,1 lub 1,1, a żaden rodzic dziecka 0 nie jest dzieckiem 0.
Reguła czerwonego czarnego, która odpowiada drzewu czerwono-czarnemu : wszystkie różnice rang wynoszą 0 lub 1, a żaden rodzic dziecka 0 nie jest dzieckiem 0. Zauważ, że reguła czerwono-czarna uogólnia regułę 2-3, dopuszczając węzeł typu 0,0.

Jak dotąd wszystkie te reguły są symetryczne dla lewego i prawego węzła. Łamiąc takie symetrie, rodzi inne zasady:

Prawostronna zasada dwóch-trzech, która odpowiada pochylonemu w prawo binaryzowanemu drzewu 2-3: każdy węzeł to 1,1 lub 0,1, żaden rodzic dziecka 0 nie jest dzieckiem 0, a żadne dziecko 0 nie jest lewy.
Lewostronna reguła dwóch-trzech, która odpowiada pochylonemu w lewo binaryzowanemu drzewu 2-3: każdy węzeł to 1,1 lub 0,1, żaden rodzic dziecka 0 nie jest dzieckiem 0, a żadne dziecko 0 nie jest Prawidłowy.
Prawoskrętna reguła czerwono-czarna, która odpowiada czerwono-czarnemu drzewu Reft: żaden rodzic dziecka 0 nie jest dzieckiem 0, a żadne dziecko 0,1-węzła nie zostało.
Lewostronna reguła czerwono-czarna, która odpowiada lewicowemu czerwono-czarnemu drzewu : wszystkie różnice w rangach wynoszą 0 lub 1, żaden rodzic dziecka 0 nie jest dzieckiem 0, a żadne dziecko 0 nie jest dzieckiem 0,1 -węzeł ma rację.

Słabe drzewo AVL jest zdefiniowane przez słabą regułę AVL:

Słaba reguła AVL: wszystkie różnice rang wynoszą 1 lub 2, a wszystkie węzły liści mają rangę 0.

Zauważ, że słabe drzewo AVL uogólnia drzewo AVL, dopuszczając węzeł typu 2,2. Prosty dowód pokazuje, że słabe drzewo AVL można pokolorować w sposób reprezentujący czerwono-czarne drzewo. Więc w pewnym sensie słabe drzewo AVL łączy w sobie właściwości drzewa AVL i drzewa czerwono-czarnego.

Definicja

Podobnie jak ogólnie w przypadku drzew wyszukiwania binarnego, drzewo WAVL składa się z kolekcji węzłów dwojakiego rodzaju: węzłów wewnętrznych i węzłów zewnętrznych. Węzeł wewnętrzny przechowuje element danych i jest połączony ze swoim rodzicem (z wyjątkiem wyznaczonego węzła głównego, który nie ma rodzica) oraz z dokładnie dwoma dziećmi w drzewie, lewym i prawym dzieckiem. Węzeł zewnętrzny nie przenosi żadnych danych i ma łącze tylko do swojego rodzica w drzewie. Te węzły są ułożone tak, aby tworzyły drzewo binarne, tak że dla dowolnego węzła wewnętrznego $x$ rodzicami lewego i prawego dziecka $x$ są $x$ samo. Zewnętrzne węzły tworzą liście drzewa. Pozycje danych są rozmieszczone w drzewie w taki sposób, że przez drzewo w kolejności inorder powoduje wyświetlenie pozycji danych w posortowanej kolejności.

To, co odróżnia drzewa WAVL od innych typów drzew wyszukiwania binarnego, to wykorzystanie rang . Są to liczby związane z każdym węzłem, które zapewniają przybliżoną odległość od węzła do najdalszego potomka liścia. W przeciwieństwie do drzew AVL, gdzie rangi są zdefiniowane jako takie same jak wysokości węzłów, rangi nie zawsze są równe wysokościom w drzewach WAVL. Różnica rang węzła x jest zdefiniowana jako różnica między rangą rodzica x a rangą x. Rangi są zobowiązane do przestrzegania następujących właściwości:

Właściwość węzła zewnętrznego: każdy węzeł zewnętrzny ma rangę $0$
Właściwość różnicy rang: Jeśli węzeł inny niż główny ma rangę $r$ , to ranga jego rodzica musi wynosić $r + 1$ lub $r + 2$ . Innymi słowy, różnica rang dla dowolnego węzła innego niż główny wynosi 1 lub 2.
Właściwość węzła wewnętrznego: węzeł wewnętrzny z dwoma zewnętrznymi dziećmi musi mieć rangę dokładnie 1.

Operacje

Badawczy

Wyszukiwanie klucza $k$ w drzewie WAVL jest bardzo podobne, jak w przypadku dowolnej zrównoważonej struktury danych drzewa wyszukiwania binarnego. Zaczyna się od korzenia drzewa, a następnie wielokrotnie porównuje $k$ z elementem danych przechowywanym w każdym węźle na ścieżce od korzenia, podążając ścieżką do lewego dziecka węzła, gdy $k$ jest mniejsze niż wartość w węźle lub zamiast tego podążaj ścieżką do prawego dziecka, gdy $k$ jest większe niż wartość w węźle. Gdy zostanie osiągnięty węzeł o wartości równej $k$ lub zostanie osiągnięty węzeł zewnętrzny, wyszukiwanie zostanie zatrzymane.

Jeśli wyszukiwanie zatrzyma się w węźle wewnętrznym, klucz $k$ został znaleziony. Jeśli zamiast tego wyszukiwanie zatrzyma się na zewnętrznym węźle, to pozycja, w której $k$ zostanie wstawione (gdyby zostało wstawione), została znaleziona.

Wprowadzenie

Wstawienie węzła wewnętrznego z kluczem $k$ do drzewa WAVL wymaga wyszukania $k$ w drzewie, kończącego się na węźle zewnętrznym, następnie zastąpienia tego węzła zewnętrznego nowym węzłem wewnętrznym z dwoma zewnętrznymi dziećmi, a na końcu ponownego zrównoważenia drzewa . Krok ponownego równoważenia można przeprowadzić od góry do dołu lub od dołu do góry, ale wersja równoważenia od dołu do góry jest tą, która najbardziej pasuje do drzew AVL.

Równoważenie od dołu do góry rozpoczyna się od rozważenia różnicy rang między węzłem - początkowo nowo wstawionym węzłem - a jego rodzicem. Jeśli nie ma rodzica, równowaga zostaje przywrócona. Przed rozpoczęciem wstawiania różnica rang między rodzicem a węzłem wynosiła 1 lub 2, ale różnica ta została zmniejszona o 1, ponieważ poddrzewo zakorzenione w węźle urosło. Jeśli nowa różnica rang między rodzicem a węzłem wynosi 1, równowaga zostaje przywrócona. W przeciwnym razie, jeśli rodzeństwo, drugie dziecko rodzica, ma różnicę w randze równą 1 z rodzicem, awansuj rodzica - zwiększ jego rangę, zwiększając różnice w randze między nim a każdym z jego dzieci - i kontynuuj przywracanie równowagi ze starym parent jako nowy węzeł.

Wreszcie, przy różnicach rang 0 i 2 dla węzła i rodzeństwa, jedna lub dwie rotacje drzewa, z powiązanymi dostosowaniami do różnic rang, mogą przywrócić równowagę. Pośrednie dziecko węzła to dziecko z kluczem między kluczami węzła i rodzica. Jeśli różnica rang dla tego dziecka i węzła wynosi 2, obróć, aby przesunąć węzeł w górę w drzewie, a rodzica w dół, a następnie zdegraduj rodzica - zmniejsz jego rangę, dostosowując różnice rang wokół niego - i równowaga zostanie przywrócona. W przeciwnym razie obróć, aby przesunąć dziecko w górę i węzeł w dół, a następnie obróć ponownie, aby przesunąć dziecko w górę i rodzica w dół. Awansuj dziecko, obniż poziom węzła i rodzica, a równowaga zostanie przywrócona.

Zatem ogólnie procedura wstawiania składa się z wyszukiwania, tworzenia stałej liczby nowych węzłów, logarytmicznej liczby zmian rang i stałej liczby rotacji drzewa.

Usunięcie

Usuwanie węzła wewnętrznego z drzewa WAVL rozpoczyna się od zwykłego usunięcia drzewa wyszukiwania binarnego . W przypadku węzła wewnętrznego bez zewnętrznego dziecka oznacza to znalezienie jego następcy w drzewie, zamianę węzła na jego następcę, a następnie usunięcie węzła z jego nowej pozycji w drzewie, gdzie jego lewe dziecko jest koniecznie węzłem zewnętrznym. Aby usunąć wewnętrzny węzeł z zewnętrznym dzieckiem, zastąp węzeł innym dzieckiem.

Ponowne równoważenie od dołu do góry rozpoczyna się od rozważenia różnicy rang między węzłem — początkowo węzłem, który zastąpił usunięty węzeł — a jego rodzicem. Jeśli nie ma rodzica, równowaga zostaje przywrócona. Przed rozpoczęciem usuwania różnica rang między rodzicem a węzłem wynosiła 1 lub 2, ale różnica ta została zwiększona o 1, ponieważ poddrzewo zakorzenione w węźle uległo skróceniu. Jeśli rodzic ma teraz dwoje zewnętrznych dzieci, właściwość węzła wewnętrznego jest naruszona, ponieważ rodzic ma rangę 2. Rodzic musi zostać zdegradowany, a ponowne równoważenie kontynuowane z rodzicem jako węzłem, który jest korzeniem zbyt krótkiego poddrzewa.

Jeśli węzeł nie ma rodzica, przywracana jest równowaga. Jeśli różnica rang między węzłem a rodzicem wzrosła z 1 do 2, równowaga zostaje przywrócona. W przeciwnym razie, jeśli rodzeństwo, drugie dziecko rodzica, ma różnicę w rankingu równą 2 z rodzicem, zdegraduj rodzica - obniż jego rangę, zmniejszając różnice w randze między nim a każdym z jego dzieci - i kontynuuj przywracanie równowagi ze starym parent jako nowy węzeł. W przeciwnym razie, jeśli dwoje dzieci rodzeństwa ma różnicę rang równą 2 z rodzeństwem, zdegraduj rodzica i rodzeństwo i kontynuuj przywracanie równowagi ze starym rodzicem jako nowym węzłem.

Wreszcie, przy różnicach rang wynoszących 3 i 1 dla węzła i rodzeństwa oraz przy rodzeństwie mającym dziecko z różnicą rang 1, jedna lub dwie rotacje drzewa, z powiązanymi dostosowaniami do różnic rang, mogą przywrócić równowagę. Zidentyfikuj dzieci rodzeństwa jako siostrzenicę i siostrzeńca, gdzie klucz siostrzenicy leży między kluczami rodzica i rodzeństwa, a klucz siostrzeńca nie. Jeśli różnica rang między rodzeństwem a siostrzeńcem wynosi 1, obróć, aby przesunąć rodzeństwo w górę, a rodzica w dół, awansować rodzeństwo i zdegradować rodzica co najmniej raz i dwa razy, jeśli to konieczne, aby uniknąć naruszenia właściwości węzła wewnętrznego. W przeciwnym razie, przy różnicy w randze rodzeństwa i siostrzeńca równej 1, obróć, aby przesunąć siostrzenicę w górę, a rodzeństwo w dół, obróć ponownie, aby przesunąć siostrzenicę w górę, a rodzica w dół, dwukrotnie awansuj siostrzenicę, raz zdegraduj rodzeństwo i zdegraduj rodzic dwa razy.

Ogólnie rzecz biorąc, usunięcie składa się z wyszukiwania w dół w celu znalezienia węzła z zewnętrznym dzieckiem, usunięcia stałej liczby nowych węzłów, logarytmicznej liczby zmian rang i stałej liczby obrotów drzewa.

Warto porównać wynik usunięcia, które spowodowałoby rotacje na wielu poziomach w drzewie AVL, z rotacją i zmianami rang wykonanymi w drzewie WAVL. Na drugim obrazie usunięto węzeł o wartości 12, następnie wykonano obrót w prawo i przypisano wszystkim zewnętrznym węzłom rangę zero.

Drzewo Fibonacciego Z Rangami

Drzewo Fibonacciego Z Rangami Po Usunięciu

Złożoność obliczeniowa

Każde wyszukiwanie, wstawianie lub usuwanie w drzewie WAVL obejmuje podążanie po jednej ścieżce w drzewie i wykonywanie stałej liczby kroków dla każdego węzła w ścieżce. W drzewie WAVL z $n$ elementami, które przeszły tylko wstawienia, maksymalna długość ścieżki wynosi ${\ Displaystyle \ log _ {\ varphi} n \ około 1,44 \ log _ {2} n}$ . Jeśli mogły wystąpić zarówno wstawienia, jak i usunięcia, maksymalna długość ścieżki wynosi ${\ Displaystyle 2 \ log _ {2} n}$ . Dlatego w obu przypadkach najgorszy czas dla każdego wyszukiwania, wstawiania lub usuwania w drzewie WAVL z $n$ elementami danych wynosi $O (log n)$ .

Dodatkowo, po znalezieniu węzła do wstawiania i usuwania, amortyzowana złożoność operacji restrukturyzacji drzewa jest stała. Dodawanie lub usuwanie samego węzła jest stałe w czasie, ilość obrotów jest zawsze co najwyżej stała i można wykazać, że całkowita ilość zmian rang w węzłach jest liniowa pod względem liczby zarówno wstawień, jak i usunięć.

Powiązane struktury

Drzewa WAVL są blisko spokrewnione zarówno z drzewami AVL , jak i drzewami czerwono-czarnymi . Każde drzewo AVL może mieć rangi przypisane do swoich węzłów w sposób, który czyni je drzewem WAVL. A każde drzewo WAVL może mieć węzły w kolorze czerwonym i czarnym (i ponownie przypisane jego rangi) w sposób, który czyni je drzewem czerwono-czarnym. Jednak niektóre drzewa WAVL nie pochodzą w ten sposób z drzew AVL, a niektóre czerwono-czarne drzewa nie pochodzą w ten sposób z drzew WAVL.

Drzewa AVL

Drzewo AVL jest rodzajem zrównoważonego drzewa wyszukiwania binarnego, w którym dwoje dzieci każdego węzła wewnętrznego musi mieć wysokość różniącą się co najwyżej o jeden. Wysokość węzła zewnętrznego wynosi zero, a wysokość dowolnego węzła wewnętrznego jest zawsze równa jeden plus maksymalna wysokość jego dwojga dzieci. Zatem funkcja wysokości drzewa AVL podlega ograniczeniom drzewa WAVL i możemy przekształcić dowolne drzewo AVL w drzewo WAVL, używając wysokości każdego węzła jako jego rangi.

Kluczowa różnica między drzewem AVL a drzewem WAVL pojawia się, gdy węzeł ma dwoje dzieci o tej samej randze lub wysokości. W drzewie AVL, jeśli węzeł $x$ ma dwoje dzieci o tej samej wysokości $h$ , to wysokość $x$ musi wynosić dokładnie $h + 1$ . Natomiast w drzewie WAVL, jeśli węzeł $x$ ma dwoje dzieci o tej samej randze $r$ co każdy inny, to ranga $x$ może wynosić albo $r + 1$ , albo $r + 2$ . Dzieje się tak, ponieważ ranga nie jest dokładnie równa wysokości w drzewie WAVL. Ta większa elastyczność rang prowadzi również do większej elastyczności struktur: niektórych drzew WAVL nie można przekształcić w drzewa AVL nawet poprzez modyfikację ich rang, ponieważ zawierają one węzły, których wysokości potomków różnią się o więcej niż jeden. Możemy jednak powiedzieć, że wszystkie drzewa AVL są drzewami WAVL. Drzewa AVL to drzewa WAVL bez typu węzła, który ma oba dzieci o różnicy rang 2.

Jeśli drzewo WAVL jest tworzone tylko za pomocą operacji wstawiania, to jego struktura będzie taka sama jak struktura drzewa AVL utworzonego przez tę samą sekwencję wstawiania, a jego rangi będą takie same jak rangi odpowiedniego drzewa AVL. Tylko poprzez operacje usuwania drzewo WAVL może różnić się od drzewa AVL. W szczególności oznacza to, że drzewo WAVL utworzone tylko przez wstawienia ma co najwyżej wysokość ${\ Displaystyle \ log _ {\ varphi} n \ około 1,44 \ log _ {2} n}$ .

Drzewa czerwono-czarne

Drzewo czerwono-czarne to zrównoważone drzewo wyszukiwania binarnego, w którym każdy węzeł ma kolor (czerwony lub czarny), spełniający następujące właściwości:

Węzły zewnętrzne są czarne.
Jeśli wewnętrzny węzeł jest czerwony, jego dwoje dzieci jest czarnych.
Wszystkie ścieżki od korzenia do węzła zewnętrznego mają taką samą liczbę czarnych węzłów.

Drzewa czerwono-czarne można równoważnie zdefiniować w kategoriach systemu rang, przechowywanych w węzłach, spełniających następujące wymagania (inne niż wymagania dla rang w drzewach WAVL):

Ranga węzła zewnętrznego wynosi zawsze 0, a ranga jego rodzica zawsze wynosi 1.
Ranga dowolnego węzła innego niż główny jest równa randze jego rodzica lub rangi jego rodzica minus 1.
Żadne dwie kolejne krawędzie na dowolnej ścieżce korzenia-liścia nie mają różnicy rang 0.

Równoważność między definicjami opartymi na kolorze i na randze można zobaczyć w jednym kierunku, kolorując węzeł na czarno, jeśli jego rodzic ma wyższą rangę, i na czerwono, jeśli jego rodzic ma równą rangę. Z drugiej strony kolory można przekształcić w rangi, ustawiając rangę czarnego węzła na równą liczbie czarnych węzłów na dowolnej ścieżce do zewnętrznego węzła i ustawiając rangę czerwonego węzła na równi z jego rodzicem.

Rangi węzłów w drzewie WAVL można przekształcić w system rang węzłów, spełniający wymagania dla drzew czerwono-czarnych, dzieląc każdą rangę przez dwa i zaokrąglając w górę do najbliższej liczby całkowitej. Z powodu tej konwersji dla każdego drzewa WAVL istnieje prawidłowe czerwono-czarne drzewo o tej samej strukturze. Ponieważ czerwono-czarne drzewa mają maksymalną wysokość ${\ Displaystyle 2 \ log _ {2} n}$ , to samo dotyczy drzew WAVL. Istnieją jednak drzewa czerwono-czarne, którym nie można nadać prawidłowej funkcji rangi drzewa WAVL.

Pomimo faktu, że pod względem struktury drzewa drzewa WAVL są szczególnymi przypadkami drzew czerwono-czarnych, ich operacje aktualizacji są różne. Rotacje drzew stosowane w operacjach aktualizacji drzewa WAVL mogą wprowadzać zmiany, które nie byłyby dozwolone w drzewie czerwono-czarnym, ponieważ w efekcie spowodowałyby zmianę koloru dużych poddrzew drzewa czerwono-czarnego, zamiast zmiany koloru tylko na jednym ścieżka w drzewie. Dzięki temu drzewa WAVL mogą w najgorszym przypadku wykonywać mniej rotacji drzewa na usunięcie niż drzewa czerwono-czarne.