Drzewa rozłożone to samobalansujące lub samoregulujące się drzewa wyszukiwania binarnego. Innymi słowy, możemy powiedzieć, że drzewa rozgałęzione są odmianami drzew poszukiwań binarnych. Warunek wstępny dla drzew rozgałęzionych, który powinniśmy wiedzieć o drzewach wyszukiwania binarnego.
Jak już wiemy, złożoność czasowa drzewa poszukiwań binarnych w każdym przypadku. Złożoność czasowa drzewa wyszukiwania binarnego w przeciętnym przypadku wynosi O(zaloguj się) a złożoność czasowa w najgorszym przypadku wynosi O(n). W drzewie wyszukiwania binarnego wartość lewego poddrzewa jest mniejsza niż węzeł główny, a wartość prawego poddrzewa jest większa niż węzeł główny; w takim przypadku złożoność czasowa byłaby O(zaloguj się) . Jeśli drzewo binarne jest przekrzywione w lewo lub w prawo, wówczas złożoność czasowa wyniesie O (n). Aby ograniczyć skośność, Drzewo AVL i czerwono-czarne pojawił się na zdjęciu, mając O(log ) złożoność czasową dla wszystkich operacji we wszystkich przypadkach. Możemy również poprawić tę złożoność czasową, wykonując bardziej praktyczne implementacje, więc nowe Drzewo Czym jest drzewo Splay?
Drzewo rozłożyste jest drzewem samorównoważącym, ale Drzewa AVL i czerwono-czarne są wówczas również drzewami samorównoważącymi się. Co sprawia, że drzewo rozłożyste jest wyjątkowe, dwa drzewa. Ma jedną dodatkową właściwość, która czyni go wyjątkowym, to rozproszenie.
Drzewo rozłożone zawiera te same operacje, co a Drzewo wyszukiwania binarnego , czyli wstawianie, usuwanie i wyszukiwanie, ale zawiera jeszcze jedną operację, czyli rozkładanie. Więc. po wszystkich operacjach w drzewie rozkładania następuje rozkładanie.
Drzewa rozłożyste nie są drzewami ściśle zrównoważonymi, ale są drzewami mniej więcej zrównoważonymi. Przyjrzyjmy się operacji wyszukiwania w drzewie rozłożonym.
Załóżmy, że chcemy przeszukać 7 elementów w drzewie, co pokazano poniżej:
Aby przeszukać dowolny element drzewa splay, najpierw wykonamy standardową operację drzewa wyszukiwania binarnego. Ponieważ 7 jest mniejsze niż 10, przejdziemy na lewo od węzła głównego. Po wykonaniu operacji wyszukiwania musimy wykonać rozkładanie. Tutaj rozproszenie oznacza, że operacja, którą wykonujemy na dowolnym elemencie, po wykonaniu pewnych przegrupowań, powinna stać się węzłem głównym. Przegrupowanie drzewa nastąpi poprzez rotacje.
Uwaga: Drzewo rozłożone można zdefiniować jako samodopasowujące się drzewo, w którym każda operacja wykonana na elemencie powoduje zmianę układu drzewa w taki sposób, że element, na którym została wykonana operacja, staje się węzłem głównym drzewa.
Obroty
Istnieje sześć rodzajów rotacji używanych do rozkładania:
- Obrót Zig (obrót w prawo)
- Obrót Zag (obrót w lewo)
- Zig zag (Zig, po którym następuje zag)
- Zag zig (Zag, po którym następuje zig)
- Zig zig (dwa obroty w prawo)
- Zag zag (dwa obroty w lewo)
Czynniki wymagane przy wyborze rodzaju rotacji
Poniżej przedstawiono czynniki stosowane przy wyborze typu rotacji:
- Czy węzeł, który próbujemy obrócić, ma dziadka?
- Czy węzeł jest lewym czy prawym dzieckiem rodzica?
- Czy węzeł jest lewym czy prawym dzieckiem dziadka?
Przypadki rotacji
Przypadek 1: Jeśli węzeł nie ma dziadka, a jest prawym dzieckiem rodzica, to wykonujemy obrót w lewo; w przeciwnym razie wykonywany jest prawy obrót.
Przypadek 2: Jeśli węzeł ma dziadka, to w oparciu o następujące scenariusze; rotacja zostanie wykonana:
Scenariusz 1: Jeśli węzeł jest na prawo od rodzica, a rodzic jest również na prawo od swojego rodzica, to zig zig w prawo obrót w prawo jest wykonywane.
Scenariusz 2: Jeśli węzeł znajduje się na lewo od rodzica, ale rodzic jest na prawo od swojego rodzica, to zygzakowaty obrót w prawo w lewo jest wykonywane.
Scenariusz 3: Jeśli węzeł znajduje się na prawo od rodzica, a rodzic jest na prawo od swojego rodzica, to zig zig w lewo obrót w lewo jest wykonywane.
Scenariusz 4: Jeśli węzeł znajduje się na prawo od rodzica, ale rodzic jest na lewo od rodzica, to zygzakowaty obrót prawo-lewo jest wykonywane.
Teraz zrozumiemy powyższe obroty na przykładach.
Aby zmienić układ drzewa, musimy wykonać kilka obrotów. Poniżej przedstawiono typy rotacji w drzewie rozłożonym:
Rotacje zig są używane, gdy przeszukiwany element jest albo węzłem głównym, albo dzieckiem węzła głównego (tj. lewym lub prawym dzieckiem).
Poniżej przedstawiono przypadki, które mogą wystąpić w drzewie rozwijanym podczas wyszukiwania:
Przypadek 1: Jeśli wyszukiwany element jest węzłem głównym drzewa.
Przypadek 2: Jeśli wyszukiwany element jest elementem podrzędnym węzła głównego, będą dostępne dwa scenariusze:
- Jeśli dziecko jest lewym dzieckiem, zostanie wykonany prawy obrót, zwany obrotem zygzakowatym w prawo.
- Jeśli dziecko jest prawym dzieckiem, zostanie wykonany obrót w lewo, zwany obrotem zygzakowatym w lewo.
Przyjrzyjmy się powyższym dwóm scenariuszom na przykładzie.
Rozważ poniższy przykład:
W powyższym przykładzie musimy przeszukać 7 elementów w drzewie. Wykonamy poniższe kroki:
Krok 1: Najpierw porównujemy 7 z węzłem głównym. Ponieważ 7 jest mniejsze niż 10, jest to lewe dziecko węzła głównego.
Krok 2: Po znalezieniu elementu wykonamy rozkładanie. Prawy obrót jest wykonywany tak, że 7 staje się węzłem głównym drzewa, jak pokazano poniżej:
Rozważmy inny przykład.
W powyższym przykładzie musimy przeszukać 20 elementów w drzewie. Wykonamy poniższe kroki:
Krok 1: Najpierw porównujemy 20 z węzłem głównym. Ponieważ 20 jest większe niż węzeł główny, jest to prawe dziecko węzła głównego.
Krok 2: Po znalezieniu elementu wykonamy rozkładanie. Obrót w lewo wykonywany jest w taki sposób, że element 20 staje się węzłem głównym drzewa.
Czasami dochodzi do sytuacji, gdy poszukiwany przedmiot ma zarówno rodzica, jak i dziadka. W tym przypadku musimy wykonać cztery rotacje w celu rozłożenia.
Rozumiemy ten przypadek na przykładzie.
Załóżmy, że musimy przeszukać 1 element w drzewie, co pokazano poniżej:
Krok 1: Najpierw musimy wykonać standardową operację wyszukiwania BST, aby przeszukać 1 element. Ponieważ 1 jest mniejsze niż 10 i 7, więc będzie znajdować się na lewo od węzła 7. Zatem element 1 ma rodzica, tj. 7, a także dziadka, tj. 10.
Krok 2: Na tym etapie musimy wykonać rozkładanie. Musimy utworzyć węzeł 1 jako węzeł główny za pomocą kilku obrotów. W tym przypadku nie możemy po prostu wykonać obrotu w zygzaku lub zag; musimy wdrożyć rotację zig zig.
Aby węzeł 1 stał się węzłem głównym, musimy wykonać dwa obroty w prawo, zwane obrotami zygzakowatymi. Kiedy wykonamy odpowiedni obrót, wówczas 10 przesunie się w dół, a węzeł 7 przesunie się w górę, jak pokazano na poniższym rysunku:
Ponownie wykonamy obrót zygzakowaty w prawo, węzeł 7 przesunie się w dół, a węzeł 1 przesunie się w górę, jak pokazano poniżej:
Jak widzimy na powyższym rysunku, węzeł 1 stał się węzłem głównym drzewa; zatem wyszukiwanie zostało zakończone.
Załóżmy, że chcemy przeszukać 20 w poniższym drzewie.
Aby przeszukać 20, musimy wykonać dwa obroty w lewo. Poniżej przedstawiono kroki wymagane do przeszukania 20 węzłów:
Krok 1: Najpierw wykonujemy standardową operację wyszukiwania BST. Ponieważ liczba 20 jest większa niż 10 i 15, będzie ona znajdować się po prawej stronie węzła 15.
Krok 2: Drugim krokiem jest wykonanie szpachlowania. W takim przypadku zostaną wykonane dwa obroty w lewo. Podczas pierwszego obrotu węzeł 10 przesunie się w dół, a węzeł 15 w górę, jak pokazano poniżej:
Podczas drugiego obrotu w lewo węzeł 15 przesunie się w dół, a węzeł 20 stanie się węzłem głównym drzewa, jak pokazano poniżej:
Jak zaobserwowaliśmy, wykonywane są dwa obroty w lewo; dlatego nazywa się to zygzakowatym obrotem w lewo.
Do tej pory czytaliśmy, że zarówno rodzice, jak i dziadkowie są w związku RR lub LL. Teraz zobaczymy relację RL lub LR między rodzicem a dziadkiem.
Rozumiemy ten przypadek na przykładzie.
Załóżmy, że chcemy przeszukać 13 elementów w drzewie pokazanym poniżej:
Krok 1: Najpierw wykonujemy standardową operację wyszukiwania BST. Ponieważ 13 jest większe niż 10, ale mniejsze niż 15, zatem węzeł 13 będzie lewym dzieckiem węzła 15.
Krok 2: Ponieważ węzeł 13 znajduje się na lewo od węzła 15, a węzeł 15 znajduje się na prawo od węzła 10, zatem istnieje relacja RL. Najpierw wykonujemy prawy obrót w węźle 15, a węzeł 15 przesunie się w dół, a węzeł 13 przesunie się w górę, jak pokazano poniżej:
Mimo to węzeł 13 nie jest węzłem głównym, a węzeł 13 znajduje się na prawo od węzła głównego, dlatego wykonamy obrót w lewo, zwany obrotem zag. Węzeł 10 przesunie się w dół, a węzeł 13 stanie się węzłem głównym, jak pokazano poniżej:
Jak możemy zaobserwować na powyższym drzewie, węzeł 13 stał się węzłem głównym; zatem wyszukiwanie zostało zakończone. W tym przypadku najpierw wykonaliśmy rotację zygzakową, a następnie rotacyjną zag; dlatego nazywa się to obrotem zygzakowatym.
Rozumiemy ten przypadek na przykładzie.
Załóżmy, że chcemy przeszukać 9 elementów w drzewie, co pokazano poniżej:
Krok 1: Najpierw wykonujemy standardową operację wyszukiwania BST. Ponieważ 9 jest mniejsze niż 10, ale większe niż 7, będzie to prawe dziecko węzła 7.
Krok 2: Ponieważ węzeł 9 znajduje się na prawo od węzła 7, a węzeł 7 na lewo od węzła 10, zatem istnieje zależność LR. Najpierw wykonujemy obrót w lewo w węźle 7. Węzeł 7 przesunie się w dół, a węzeł 9 w górę, jak pokazano poniżej:
Mimo to węzeł 9 nie jest węzłem głównym, a węzeł 9 znajduje się na lewo od węzła głównego, dlatego wykonamy obrót w prawo, zwany obrotem zygzakowatym. Po wykonaniu odpowiedniego obrotu węzeł 9 staje się węzłem głównym, jak pokazano poniżej:
Jak możemy zaobserwować na powyższym drzewie, węzeł 13 jest węzłem głównym; zatem wyszukiwanie zostało zakończone. W tym przypadku najpierw wykonaliśmy obrót zag (obrót w lewo), a następnie wykonujemy obrót zygzakowaty (obrót w prawo), więc jest to znane jako obrót zag zig.
Zalety drzewa rozłożystego
- W drzewie rozkładania nie musimy przechowywać dodatkowych informacji. Z kolei w drzewach AVL musimy przechowywać współczynnik równowagi każdego węzła, który wymaga dodatkowej przestrzeni, a drzewa czerwono-czarne wymagają również przechowywania jednego dodatkowego bitu informacji, który oznacza kolor węzła, czerwony lub czarny.
- Jest to najszybszy typ drzewa wyszukiwania binarnego do różnych zastosowań praktycznych. Jest używany w Kompilatory Windows NT i GCC .
- Zapewnia lepszą wydajność, ponieważ często używane węzły będą przesuwać się bliżej węzła głównego, dzięki czemu można szybko uzyskać dostęp do elementów w drzewach rozwiniętych. Jest używany w implementacji pamięci podręcznej, ponieważ ostatnio dostępne dane są przechowywane w pamięci podręcznej, dzięki czemu nie musimy udawać się do pamięci, aby uzyskać dostęp do danych, i zajmuje to mniej czasu.
Wada drzewa rozłożystego
Główną wadą drzewa rozgałęzionego byłoby to, że drzewa nie są ściśle zrównoważone, tj. Są w przybliżeniu zrównoważone. Czasami drzewa rozgałęzione są liniowe, więc zajmie to złożoność czasową O(n).
Operacja wstawiania w drzewie Splay
w wprowadzenie operacji, najpierw wstawiamy element do drzewa, a następnie wykonujemy operację rozkładania na wstawionym elemencie.
15, 10, 17, 7
Krok 1: Najpierw wstawiamy do drzewa węzeł 15. Po włożeniu musimy wykonać rozkładanie. Ponieważ 15 jest węzłem głównym, więc nie musimy wykonywać rozkładania.
Krok 2: Następnym elementem jest 10. Ponieważ 10 jest mniejsze niż 15, zatem węzeł 10 będzie lewym dzieckiem węzła 15, jak pokazano poniżej:
Teraz występujemy rozchylanie . Aby utworzyć 10 jako węzeł główny, wykonamy prawy obrót, jak pokazano poniżej:
Krok 3: Następnym elementem jest 17. Ponieważ 17 jest większe od 10 i 15, stanie się prawym dzieckiem węzła 15.
Teraz wykonamy rozkładanie. Ponieważ 17 lat to zarówno rodzic, jak i dziadek, dlatego będziemy wykonywać zygzakowate rotacje.
Na powyższym rysunku możemy zaobserwować, że 17 staje się węzłem głównym drzewa; dlatego wstawianie jest zakończone.
Krok 4: Następnym elementem jest 7. Ponieważ 7 jest mniejsze niż 17, 15 i 10, zatem węzeł 7 pozostanie dzieckiem 10.
Teraz musimy rozłożyć drzewo. Ponieważ liczba 7 ma zarówno rodzica, jak i dziadka, wykonamy dwie rotacje w prawo, jak pokazano poniżej:
Nadal węzeł 7 nie jest węzłem głównym, jest lewym dzieckiem węzła głównego, tj. 17. Zatem musimy wykonać jeszcze jeden obrót w prawo, aby węzeł 7 stał się węzłem głównym, jak pokazano poniżej:
Algorytm operacji wstawiania
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
W powyższym algorytmie T jest drzewem, a n jest węzłem, który chcemy wstawić. Stworzyliśmy zmienną temp zawierającą adres węzła głównego. Będziemy uruchamiać pętlę while, aż wartość temp stanie się NULL.
Po zakończeniu wstawiania zostanie wykonane rozkładanie
Algorytm operacji rozkładania
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
W powyższej implementacji x jest węzłem, na którym wykonywany jest obrót, natomiast y jest lewym dzieckiem węzła x.
Implementacja obrotu w lewo(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
W powyższej implementacji x jest węzłem, w którym wykonywany jest obrót, a y jest prawym dzieckiem węzła x.
Usunięcie w drzewie Splay
Ponieważ wiemy, że drzewa splay są odmianami drzewa wyszukiwania binarnego, więc operacja usuwania w drzewie splay będzie podobna do BST, z tą tylko różnicą, że po operacji usuwania w drzewach splay następuje operacja splayowania.
Rodzaje usunięć:
Istnieją dwa rodzaje usunięć w drzewach rozlanych:
- Rozkładanie od dołu do góry
- Rozkładanie od góry do dołu
Rozkładanie od dołu do góry
W przypadku rozkładania od dołu do góry najpierw usuwamy element z drzewa, a następnie wykonujemy rozkładanie na usuniętym węźle.
Rozumiemy usunięcie w drzewie Splay.
Załóżmy, że chcemy usunąć 12, 14 z drzewa pokazanego poniżej:
numpy dziennik
- Najpierw po prostu wykonujemy standardową operację usuwania BST, aby usunąć 12 elementów. Ponieważ 12 jest węzłem liścia, więc po prostu usuwamy węzeł z drzewa.
Usuwanie nadal nie zostało zakończone. Musimy rozłożyć rodzica usuniętego węzła, czyli 10. Musimy wykonać Rozłóż(10) na drzewie. Jak widać na powyższym drzewie, 10 znajduje się na prawo od węzła 7, a węzeł 7 na lewo od węzła 13. Zatem najpierw wykonujemy obrót w lewo na węźle 7, a następnie wykonujemy obrót w prawo na węźle 13, jak pokazano poniżej:
Mimo to węzeł 10 nie jest węzłem głównym; węzeł 10 jest lewym dzieckiem węzła głównego. Musimy zatem wykonać odpowiedni obrót w węźle głównym, tj. 14, aby węzeł 10 stał się węzłem głównym, jak pokazano poniżej:
- Teraz musimy usunąć element 14 z drzewa, co pokazano poniżej:
Jak wiemy, nie możemy po prostu usunąć węzła wewnętrznego. Zastąpimy wartość węzła za pomocą inny poprzednik Lub inny następca . Załóżmy, że używamy następnika inorder, w którym zastępujemy wartość najniższą wartością istniejącą w prawym poddrzewie. Najniższa wartość w prawym poddrzewie węzła 14 wynosi 15, więc zastępujemy wartość 14 liczbą 15. Ponieważ węzeł 14 staje się węzłem liścia, możemy go po prostu usunąć, jak pokazano poniżej:
Mimo to usuwanie nie zostało zakończone. Musimy wykonać jeszcze jedną operację, czyli rozciągnięcie, w którym musimy uczynić rodzica usuniętego węzła jako węzeł główny. Przed usunięciem rodzicem węzła 14 był węzeł główny, tj. 10, więc w tym przypadku musimy wykonać dowolne rozkładanie.
Rozkładanie od góry do dołu
W przypadku rozkładania z góry na dół najpierw wykonujemy rozkładanie, na którym ma nastąpić usunięcie, a następnie usuwamy węzeł z drzewa. Po usunięciu elementu wykonamy operację łączenia.
Przyjrzyjmy się rozkładaniu z góry na dół na przykładzie.
Załóżmy, że chcemy usunąć 16 z drzewa, jak pokazano poniżej:
Krok 1: W przypadku rozkładania z góry na dół najpierw wykonujemy rozkładanie na węźle 16. Węzeł 16 ma zarówno rodzica, jak i dziadka. Węzeł 16 znajduje się na prawo od swojego rodzica, a węzeł nadrzędny również znajduje się na prawo od swojego rodzica, więc jest to sytuacja zag. W tym przypadku najpierw wykonamy obrót w lewo w węźle 13, a następnie 14, jak pokazano poniżej:
Węzeł 16 nadal nie jest węzłem głównym i jest prawym dzieckiem węzła głównego, dlatego musimy wykonać obrót w lewo w węźle 12, aby węzeł 16 stał się węzłem głównym.
Gdy węzeł 16 stanie się węzłem głównym, usuniemy węzeł 16 i otrzymamy dwa różne drzewa, tj. lewe i prawe poddrzewo, jak pokazano poniżej:
Jak wiemy, wartości lewego poddrzewa są zawsze mniejsze niż wartości prawego poddrzewa. Korzeń lewego poddrzewa ma liczbę 12, a pierwiastek prawego poddrzewa wynosi 17. Pierwszym krokiem jest znalezienie elementu maksymalnego w lewym poddrzewie. W lewym poddrzewie maksymalny element wynosi 15, a następnie musimy wykonać operację rozkładania na 15.
Jak możemy zaobserwować na powyższym drzewie, element 15 ma zarówno rodzica, jak i dziadka. Węzeł znajduje się na prawo od swojego rodzica i węzeł nadrzędny również znajduje się na prawo od swojego rodzica, dlatego musimy wykonać dwa obroty w lewo, aby węzeł 15 stał się węzłem głównym, jak pokazano poniżej:
Po wykonaniu dwóch obrotów na drzewie węzeł 15 staje się węzłem głównym. Jak widzimy, prawym dzieckiem liczby 15 jest NULL, więc dołączamy węzeł 17 po prawej stronie liczby 15, jak pokazano poniżej, a operacja ta jest znana jako dołączyć operacja.
Uwaga: Jeżeli elementu nie ma w drzewie splay, które ma zostać usunięte, wówczas zostanie wykonane splayowanie. Rozkładanie zostanie wykonane na ostatnim elemencie, do którego uzyskano dostęp przed osiągnięciem wartości NULL.
Algorytm operacji usuwania
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
W powyższym algorytmie najpierw sprawdzamy, czy pierwiastek ma wartość Null, czy nie; jeśli korzeń ma wartość NULL, oznacza to, że drzewo jest puste. Jeżeli drzewo nie jest puste, wykonamy operację rozkładania na elemencie, który ma zostać usunięty. Po zakończeniu operacji rozkładania porównamy dane korzenia z elementem, który ma zostać usunięty; jeśli oba nie są równe, oznacza to, że elementu nie ma w drzewie. Jeśli są równe, mogą wystąpić następujące przypadki:
Przypadek 1 : Lewa strona korzenia ma wartość NULL, prawa strona korzenia staje się węzłem głównym.
Przypadek 2 : Jeśli istnieje zarówno lewy, jak i prawy, wówczas umieszczamy maksymalny element w lewym poddrzewie. Po zakończeniu rozkładania maksymalny element staje się korzeniem lewego poddrzewa. Prawe poddrzewo stanie się prawym dzieckiem korzenia lewego poddrzewa.