W poprzednich wykładach wdrażaliśmy jak usunąć dany plik. z poradnika i jak wstawić dany
węzeł do zdarzenia.
Jest dokładnie taki sam, jak omówiliśmy przy wyszukiwaniu binarnym.
W każdym razie w tym wykładzie będziemy mówić o tym, jak obliczyć, a więc obliczyć lub
policzyć parametr Haith w odniesieniu do danego węzła.
Więc jeśli pamiętacie, ilekroć wstawiamy dany węzeł do osiemdziesięciu trzech, musimy zaktualizować parametr
Haith dla węzła zdarzeń.
Jak widać tutaj, nazywamy funkcję parametru obliczania Haitha.
Więc co musimy zrobić.
W części teoretycznej rozmawialiśmy o tym, że jeśli węzłem jest nie, to musimy wrócić do minus
jeden.
Zasadniczo dzieje się tak, gdy węzeł nie jest wskaźnikiem.
Więc to jest, gdy węzeł nie jest appointer.
W przeciwnym razie musimy po prostu wrócić z samym parametrem Haith.
Na przykład tutaj każdy węzeł ma parametr Haith.
Te parametry zostały zaktualizowane po wstawieniu tych węzłów.
Dlatego właśnie mamy te parametry za każdym razem, gdy dochodzimy do wniosku, że węzeł jest appointer.
Wiemy na pewno, że żadne wskaźniki nie mają parametrów Haith minus jeden.
W przeciwnym razie wiemy na pewno, że musimy po prostu zwrócić parametr Haith powiązany z tym
danym węzłem.
Więc to jest dokładnie to, co się tutaj dzieje.
OK, musimy mieć funkcję obliczającą parametr bilansu skojarzony z danym węzłem.
Więc co musimy zrobić?
Ponownie, jeśli węzeł nie jest, to oczywiście jest bliski zeru, w przeciwnym razie musimy zwrócić lewy węzeł
i oczywiście Sahhaf, który oblicza parametr Haith.
Więc obliczamy parametr Haith dla lewej strony lub lewego poddrzewa minus i obliczamy
barometr Haitha dla prawego poddrzewa.
Możesz zadać pytanie, OK, dlaczego widzę lewą trójkę, gdy mamy do czynienia z lewym węzłem, a
prawą subtelnie, gdy mamy do czynienia z prawym węzłem.
Spójrzmy na konkretny przykład.
Jeśli chodzi o pożywienie, ma parametr Haith jeden, ale ten jest parametrem zdrowia samego Swaptree,
które ma węzeł główny, ponieważ jeśli mamy do czynienia z dwunastoma, na przykład
dwanaście ma parametr Haith dwa, a dwa to będzie najgorszym barometrem poddrzewa, które ma węzeł
główny dwanaście.
Dlatego właśnie, jeśli weźmiemy pod uwagę na przykład węzeł główny, lewe dziecko ma parametr Haith
jeden, a jedno jest parametrem Haith dla samego lewego poddrzewa.
Jeden jest parametrem dla prawego poddrzewa również w tym przypadku i jest to parametr Haith
dla prawego dziecka węzła głównego.
OK.
A tak przy okazji, o tym właśnie mówiliśmy w części teoretycznej, że mamy tak
zwany parametr zrównoważony.
Zrównoważony parametr to obwód Haitha lewego poddrzewa, minus barometr Haitha dla prawego
poddrzewa.
Więc to musimy obliczyć.
Nazywa się to współczynnikiem równowagi, ponieważ oczywiście, jeśli bezwzględna wartość współczynnika bilansu jest większa
niż jeden, oznacza to, że struktura podobna do drzewa jest niezrównoważona.
Musimy więc wykonywać obroty.
Na przykład w tym przypadku współczynnik równowagi wynosi jeden minus jeden, co jest równe dwa.
Więc jeśli współczynnik równowagi jest większy niż jeden, oznacza to, że jest to szczęśliwa sytuacja.
A jeśli współczynniki równowagi są takie, parametr Haith lewego poddrzewa minus
parametr nienawiści prawego poddrzewa, to jest obliczony parametr nienawiści lewego poddrzewa wynosi minus jeden minus parametr
nienawiści prawego poddrzewa wynosi jeden minus jeden minus jeden to minus dwa.
Więc jeśli współczynnik równowagi jest mniejszy niż minus jeden, oznacza to, że jest to właściwa szczęśliwa sytuacja.
Musimy więc wykonać obrót w lewo.
Dlatego ważne jest, aby obliczyć współczynnik równowagi.
Oczywiście, jeśli znamy Haith i współczynnik równowagi, możemy zdefiniować inną funkcję
naruszenia.
Harpur, naruszenie Harper przyjmie węzeł jako parametr.
I oczywiście przede wszystkim musimy obliczyć współczynnik równowagi dla danego węzła.
To będzie równowaga.
Więc co musimy zrobić?
Przede wszystkim więc wiemy na pewno, że jeśli parametr równowagi jest większy niż jeden, co to
dokładnie oznacza?
Oznacza to, że drzewo jest ciężkie.
Ale oczywiście są dwa przypadki.
Może to być ciężka sytuacja po lewej stronie po prawej lub szczęśliwa sytuacja po lewej stronie.
Więc znowu musimy sprawdzić, czy musimy obliczyć współczynnik równowagi dla węzła nadrzędnego.
OK, więc co mamy zrobić?
Musimy obliczyć współczynnik równowagi dla lewego dziecka, jeśli współczynnik równowagi.
Lewe dziecko jest mniejsze od zera niż lewe, prawe.
Masz sytuację?
Musimy więc obrócić rodzica w lewo, a dziadka w prawo.
Więc musimy zrobić lewy obrót na lewym dziecku.
W przeciwnym razie oznacza to, że jest to ciężka sytuacja po lewej stronie.
Musimy więc po prostu wykonać jeden prawy obrót, aby wykonać właściwy obrót, jeśli chodzi o węzeł.
OK, na przykład jest to typowa ciężka sytuacja z lewej i prawej strony.
Więc co musimy zrobić?
Musimy wykonać obrót w lewo na węźle B, a następnie musimy wykonać obrót w prawo na węźle D.
Tak więc możemy poradzić sobie z ciężką sytuacją po lewej stronie.
I właśnie dlatego wykonujemy obrót w lewo, a następnie w prawo.
OK, a co jeśli mamy ciężką sytuację z Dubberly?
Wtedy oczywiście możemy obliczyć współczynnik równowagi na podstawie parametrów Haitha.
Więc co musimy zrobić?
Musimy wykonać prostą prawą rotację.
OK, więc tak właśnie się dzieje, gdy mamy ciężką sytuację z Dubberly.
Więc jeśli mamy lewą prawą sytuację ciężką, to musimy wykonać lewy obrót, a następnie prawy
obrót.
Jeśli mamy ciężką sytuację z lewej strony Dubberly, nie ma potrzeby obracania się w lewo.
Po prostu wykonujemy prosty prawy obrót i oczywiście musimy zrobić mniej więcej to samo, jeśli
mamy współczynnik równowagi mniejszy niż minus jeden.
To jest właściwa ciężka sytuacja.
Ale oczywiście może to być sytuacja podwójnego zapisu lub ciężka sytuacja z prawej strony.
Jeśli jest to ciężka sytuacja na prawo i lewo, musimy wykonać prawidłowy obrót.
A potem ostatni obrót, jeśli jest to ciężka sytuacja z prawej strony Dubberly'ego, to musimy wykonać
jeden obrót w lewo.
Tak bardzo, bardzo podobny do tego, co widzieliśmy tutaj.
OK, więc znowu musimy sprawdzić współczynnik równowagi dla odpowiedniego dziecka.
Jeśli jest większa od zera, oznacza to, że jest to ciężka sytuacja z prawej strony lewej.
Musimy więc wykonać prawy obrót, a potem musimy wykonać lewy obrót bez względu na wszystko, ponieważ jest
to dwukrotność prawego.
W każdej sytuacji, w której nie wykonamy obrotu w prawo, wykonujemy tylko jeden obrót w lewo.
Zasadniczo jest to podstawowa zasada stojąca za drzewami, którą musimy sprawdzić.
Oczywiście współczynnik równowagi i współczynnik równowagi zależą od parametrów zdrowotnych.
I musimy się upewnić, że jeśli współczynnik równowagi jest większy niż jeden, jest to ciężka sytuacja po lewej stronie.
Jeśli współczynnik równowagi jest mniejszy niż minus jeden, jest to właściwa sytuacja ciężka, w przeciwnym razie struktura
podobna do drzewa jest zrównoważona.
To jest to, co musimy sprawdzić po każdej operacji usuwania i za każdym razem, gdy wstawiamy dany
węzeł do drzewa IV.
Na razie w porządku.
Najważniejsze jest jednak to, że wywołujemy tutaj funkcję handle violation, ilekroć wstawiamy
lub usuwamy dany element i zaimplementowaliśmy tzw. Funkcję pomocnika naruszenia.
Więc co musimy zrobić?
Musimy zaimplementować uchwyt, funkcję regulacji, która będzie sprawdzać węzeł z węzła, który
wstawiliśmy, do węzła głównego.
Przede wszystkim jest to zaimplementowane, a potem o tym porozmawiamy.
Więc zaczynamy od węzła, który wstawiliśmy lub w zasadzie od węzła macierzystego.
Więc za każdym razem, gdy usuniemy dany element lub wstawimy go ponownie, ten węzeł będzie reprezentował
węzeł nadrzędny tych elementów.
OK, więc chociaż węzłem nie jest Norns, więc w zasadzie, gdy trafimy do węzła głównego, przede wszystkim musimy
ponownie obliczyć parametr Haith dla tego podanego węzła.
Więc znowu musimy użyć tej samej rekurencyjnej formuły, którą omówiliśmy na poprzednich wykładach.
Zatem maksimum z parametru Haith w ostatnim poddrzewie, obwód prawego poddrzewa,
obliczamy maksymalny plus jeden.
Zwiększamy wartość o jeden.
Więc robimy coś takiego, OK?
Oczywiście dlatego wdrożyliśmy naruszenie.
Hatboro, bo musimy sprawdzić na podstawie współczynników bilansowych i parametrów Haitha, gdzie musimy
wykonać dany obrót, czy nie?
A potem co mamy robić?
Węzeł znajduje się blisko węzła nadrzędnego, więc nadal rozważamy każdy węzeł, zaczynając od węzła
nadrzędnego węzła.
Usunęliśmy lub wstawiliśmy do węzła głównego.
I oczywiście możesz zadać pytanie, dlaczego?
Ponieważ za każdym razem, gdy ustalamy naruszenie, więc wykonujemy obroty, oczywiście może się zdarzyć, że narusza to wszystkie
właściwości w innej części struktury podobnej do drzewa.
Dlatego właśnie musimy.
Wykonaj tak zwane podejście rekurencyjne, OK, w tym przypadku używamy iteracji, ale i tak
sprawdzamy, zaczynając od danego węzła do węzła głównego, w którym musimy wykonać obroty, aby wyrównać
strukturę drzewa .
W każdej pojedynczej iteracji naruszenie nazywamy Harpur.
To będzie sprawdzać na podstawie parametrów równowagi, gdzie dana struktura podobna do drzewa jest zrównoważona, czy
nie.
I oczywiście ważne jest, aby to sprawdzić.
Więc sprawdza, czy poddrzewo jest zrównoważone z węzłem głównym jest równe węzłowi.
Więc zamierzamy sprawdzić, czy poddrzewo jest zrównoważone, które ma węzeł główny.
Dlatego właśnie nazywamy tę funkcję w każdej iteracji.
Na przykład, jeśli wstawiliśmy węzeł pięć, nazywamy to naruszeniem w węźle nadrzędnym.
Następnie dochodzimy do wniosku, że to poddrzewo jest zrównoważone.
Rozważamy więc węzeł nadrzędny.
Jak postawiliśmy pytanie, opierając się na czynnikach równowagi, że niezależnie od tego, czy te trzy podobne struktury są zrównoważone,
czy nie, ta struktura podobna do drzewa jest równowagą.
To już koniec operacji.
Dlatego zawsze zaczynamy od węzła, który wstawiliśmy, a dokładniej, od węzła macierzystego węzła,
który wstawiliśmy do węzła głównego.
I w każdej pojedynczej iteracji zadawaliśmy pytanie, czy dane poddrzewo jest zrównoważone, czy nie.
Okay, więc to wszystko o naruszeniach, jeśli chodzi o naruszenie uchwytu i naruszenie, dotyczy Harpera
i to właśnie będziemy nazywać za każdym razem, gdy wstawimy dany węzeł.
A tak przy okazji, przepraszam za to.
Ilekroć nazywamy naruszenie uchwytu, kiedy usuwamy dany element, oczywiście musimy wywołać go w
węźle nadrzędnym.
Tak więc postępuj w przypadku naruszenia, jeśli chodzi o rodzica.
OK, więc mamy naruszenie uchwytu, naruszenie uchwytu rodzica w węźle nadrzędnym i oczywiście mamy obsługę naruszeń za
każdym razem, gdy wstawimy dane a ..
OK, więc w ten sposób możemy sprawdzić, czy struktura podobna do drzewa jest zrównoważona, czy nie, w oparciu o parametr
równowagi.
Dzięki za oglądanie.