W tym wykładzie porozmawiamy o funkcji trybu usuniętego, a ponieważ jest to
funkcja najbardziej złożona pod względem dyskursu.
Nie zamierzam pisać kodu źródłowego od zera, ponieważ istnieje kilka instrukcji if, jak widać,
jestem pewien, że będzie wiele literówek i tak dalej.
Więc może najlepiej jest pobrać slajdy i kod źródłowy oraz oczywiście materiały z ostatniego wykładu
oraz skopiować i wkleić kod.
I zamierzamy przedyskutować, co dokładnie się dzieje.
Dlatego za każdym razem, gdy usuwamy dany węzeł, musimy go znaleźć.
Przede wszystkim, jeśli węzeł nie jest, oczywiście zwrot.
Ale w przeciwnym razie przede wszystkim musimy znaleźć w danym węźle, który chcemy usunąć.
O tym mówiliśmy w części teoretycznej, że na przykład, jeśli
mamy strukturę podobną do drzewa i chcielibyśmy usunąć pięć, to co musimy zrobić?
Przede wszystkim musimy wyszukać dany węzeł.
A potem możemy go usunąć.
Dlatego właśnie po pierwsze musimy znaleźć dany węzeł i jak go znaleźć.
Oczywiście, jeśli dane, których szukamy, są mniejsze niż rzeczywiste dane węzła, musimy przejść do lewego
poddrzewa.
Dlatego właśnie tę funkcję wywołujemy rekurencyjnie na lewym dziecku.
W przeciwnym razie, jeśli dane są większe niż rzeczywiste dane węzła, wówczas wywołujemy tę funkcję rekurencyjnie,
ponieważ wiemy, że dane, które chcielibyśmy usunąć, znajdują się we właściwym drzewie SOC.
I jak wiemy, że znaleźliśmy dany węzeł.
Chcielibyśmy usunąć.
I o tym też mówiliśmy, że są cztery przypadki.
Węzeł, który chcielibyśmy usunąć, może być węzłem typu liść.
Może mieć jedno dziecko, bez względu na to, czy jest to dziecko prawe czy lewe.
I wreszcie możemy usunąć węzeł z dwójką dzieci.
Przede wszystkim najprostszym przypadkiem jest próba usunięcia węzła liścia.
Co mamy robić?
O tym mówiliśmy w radykalnej części.
Musimy po prostu usunąć dany węzeł, jak widać.
Po znalezieniu węzła piątego musimy po prostu powiadomić jego element nadrzędny, że węzeł został usunięty.
Dlatego potrzebujemy węzła nadrzędnego.
Właśnie dlatego w klasie węzłów mamy rodzica, który jest w pobliżu.
Co więc musimy zrobić, gdy węzły odejdą?
Dziecko jest samotne, a właściwe dziecko jest nieznane.
Tak jest w przypadku węzła liścia, który chcielibyśmy usunąć.
Ale potem musimy zdobyć rodzica i musimy sprawdzić, czy dane dane węzła są zamówieniem po lewej stronie dziecka.
Racja, Chad.
Wiemy, że sam węzeł jest węzłem liścia, więc nie ma żadnego lewego lub prawego dziecka.
Ale musimy sprawdzić, czy dany węzeł jest lewym dzieckiem, czy prawym plemieniem.
Więc jeśli rodzic nie jest nie-rodzicem, a rodzic zostawił dziecko, to sama notatka.
Wiemy, że jest to lewe dziecko.
Właśnie dlatego rodzice zostali.
Dziecko jest równe anonowi.
W ten sposób go usuwamy.
Jeśli jest to lewe dziecko rodzica.
W przeciwnym razie, jeśli jest to właściwe dziecko rodziców, wówczas ustawiamy je również jako zakonnicę.
Więc jeśli rodzic jest zakonnicą.
Mamy więc do czynienia z węzłem głównym.
Potem powiedzieliśmy, że korzeniami nie jest zakonnica.
I w końcu usuwamy dany węzeł.
Dlatego jest to nieco bardziej złożone, ponieważ musimy zaktualizować rodziców.
Więc tutaj, na przykład, musimy sprawdzić rodzica, a ponieważ rodzic piątego dziecka ma cztery lata, a pięcioro jest właściwym
dzieckiem czwartego roku życia.
Musimy zwolnić czterech.
Dobrze.
Próbuję zostać zakonnicą, ponieważ usunęliśmy tę notatkę.
Dlatego ważne jest, aby zdecydować, czy rodzice pozostawili dziecko, czy prawe dziecko jest faktycznym węzłem.
Chcielibyśmy usunąć.
W ten sposób usuwamy węzeł liścia.
A co, jeśli węzły odejdą?
Lewy-prawy jest nie-węzłem.
Dobrze.
Dziecko nie jest znane.
Oznacza to, że chcielibyśmy usunąć węzeł z jednym prawym dzieckiem.
Co więc musimy zrobić?
Ten problem jest tutaj dość symetryczny.
Na przykład chcielibyśmy usunąć jeden.
Przede wszystkim musimy to znaleźć.
I w tym przypadku ma jedno pozostawione dziecko.
Co więc musimy zrobić?
Jakoś musimy zaktualizować referencje.
I jak widać, rodzic będzie wskazywał na swoje lewe dziecko.
I tak by było, gdybyśmy mieli do czynienia z właściwym dzieckiem.
Co mamy robić?
Musimy zaktualizować węzeł nadrzędny i powiedział rodziców.
Dobrze.
Dziecko, które będzie właściwym dzieckiem danego węzła.
Zasadniczo jest bardzo, bardzo podobny.
Kiedy mamy tutaj do czynienia z lewymi dziećmi i prawymi dziećmi, mamy do czynienia z węzłem z jednym prawym
dzieckiem.
Co więc musimy zrobić?
Znów musimy zdobyć rodziców.
A jeśli rodzic nie jest nie.
Następnie musimy sprawdzić, czy jeśli rodzice pozostawili dziecko, jest węzłem, to ten rodzic lub to dziecko jest
równe węzłowi.
Dobrze.
Dziecko, możesz postawić pytanie, dlaczego to robimy, ponieważ wiemy na pewno, że węzły, które
opuściły dziecko, nie są.
I węzły.
Dobrze.
Dziecko to za mało.
Usuwamy więc węzeł z jednym prawym dzieckiem.
Dlatego rodzice zostawili dziecko.
Dlaczego lewe dziecko?
Ponieważ wiemy na pewno, że węzeł jest lewym dzieckiem rodzica.
I oczywiście chcielibyśmy usunąć węzeł.
Właśnie dlatego rodzice, którzy opuścili dziecko, będą węzłem.
Dobrze.
Dziecko.
DOBRZE.
A jeśli rodzice.
Dobrze.
Dziecko jest węzłem, a następnie rodzicami.
Dobrze.
Dziecko będzie węzłem.
Dobrze.
W ten sposób upewniamy się, że rodzic zostanie powiadomiony i zapytamy, co to znaczy,
że rodzic nie jest.
Mamy więc do czynienia z węzłem głównym.
A następnie musimy zaktualizować sam węzeł root.
Więc węzeł główny będzie węzłami, prawda?
Dziecko oczywiście, ponieważ węzeł.
Dobrze.
To nie wystarczy.
Nie możemy przypisać lewej strony węzła, ponieważ lewy trójkąt to węzeł.
I jest bardzo, bardzo podobny.
I mamy do czynienia z węzłem z jednym lewym dzieckiem.
Właściwe dziecko nie jest.
A lewe dziecko nie jest zakonnicą.
Jak widać tutaj kod, jest on bardzo, bardzo podobny do tego.
Co więc musimy zrobić?
Musimy zdobyć rodzica.
A jeśli rodzic nie jest zakonnicą, musimy to sprawdzić.
Jeśli rodzice odeszli, dziecko jest węzłem.
Więc węzeł jest lewym dzieckiem swojego rodzica.
Wtedy rodzice będą starali się być węzłami pozostawionymi dziecku.
A jeśli rodzice moje dziecko jest węzłem, to rodzice.
Dobrze.
Dziecko będzie węzłem pozostawionym dzieckiem.
Ponownie oczywiście mamy do czynienia z węzłami Lewo-Prawa, ponieważ węzły.
Dobrze.
Dziecko jest zakonnicą.
A ponieważ oznacza to, że węzeł nadrzędny jest węzłem głównym.
Musimy więc ustawić węzeł główny jako węzeł pozostawiony jako dziecko.
Ponownie mamy do czynienia z lewym dzieckiem, ponieważ prawe dziecko jest zakonnicą.
Jest to zasadniczo bardzo symetryczne.
Wizualizacja tego problemu jest dość łatwa, ponieważ musimy po prostu pozbyć się faktycznego węzła.
I musimy powiadomić rodzica, aby odwołał się do następnego węzła w drzewie wyszukiwania binarnego.
W ten sposób możemy pozbyć się tego faktycznego węzła.
A poza tym wiemy, że chcielibyśmy usunąć węzeł, który dwoje dzieci?
Co mamy robić?
Na przykład, jeśli chcemy usunąć 32, który jest węzłem głównym.
Jak widać, ma lewe dziecko i właściwą ścieżkę.
Mamy więc dwie opcje.
Szukamy największej pozycji w lewym poddrzewie lub najmniejszej pozycji w prawym poddrzewie.
Użyjemy pierwszego rozwiązania.
Więc znajdziemy największy element w lewym poddrzewie, który nazywa się poprzednikiem.
I musimy je wymazać.
Więc jeśli wymazamy drapieżnika z węzłem korzeniowym, to tutaj otrzymamy przypadek.
Musimy więc teraz ustawić dwa, ponieważ jest to węzeł liścia.
Wiemy, jak radzić sobie z B, węzłem liścia.
Musimy to tylko usunąć.
A więc przede wszystkim, co zobaczył drapieżnik?
Co zobaczył Predator?
Predator zobaczył.
Czy to prawda?
Większość przedmiotów.
Więc największy przedmiot w lewym S3.
Zasadniczo więc musimy ponownie zdobyć maksymalną liczbę przedmiotów.
Jak zdobyć maksymalną pozycję.
Możemy użyć iteracji.
Lub możemy użyć rekurencji.
Musimy tylko znaleźć odpowiednie większość przedmiotów.
Dlatego właśnie będzie bardzo, bardzo podobny.
Co mamy robić?
Musimy sprawić, by drapieżnik zobaczył z lewej strony, zaniepokojony Sokrates.
Właśnie dlatego mieliśmy węzeł, który opuścił poddrzewo.
Więc spróbujmy.
Jak widzisz.
Właśnie dlatego upewniamy się, że znajdziemy największy przedmiot w lewym poddrzewie.
Nazywa się to sklepem Predator.
Co więc musimy zrobić?
Musimy wymazać dwa przedmioty.
Musimy wymazać piłę Predator.
Zrobiliśmy węzeł.
Chcielibyśmy usunąć.
Następnie wywołujemy tę funkcję rekurencyjnie i chcielibyśmy usunąć drapieżnika.
Właśnie o tym mówiliśmy.
Dość tej sekcji siatki.
Musimy znaleźć źródło drapieżnika.
Musimy je zamienić.
A potem jesteśmy w pierwszym przypadku.
Musimy więc usunąć liść.
Nie, w zasadzie nazywamy tę funkcję rekurencyjnie na tego typu drapieżniku.
Ta funkcja zostanie ponownie wywołana.
Co się stanie?
Węzłem będzie drapieżnik widział Predatora.
Więc nie ma żadnych dzieci, ponieważ jest węzłem liścia.
Zasadniczo to właśnie zostanie wykonane.
I usuniemy węzeł liścia.
To wszystko dotyczy wdrożenia.
I oczywiście potrzebujemy tej funkcji pomocnika.
Otrzymujemy dane.
Chcielibyśmy się pozbyć.
A jeśli węzeł główny nie jest znany, nazywamy go węzłem usuwania.
My.
Węzeł główny na początku.
Zasadniczo chodzi o operację usuwania.
Na przykład mamy strukturę podobną do drzewa.
Załóżmy, że na początku wywołajmy funkcję Travaris.
Więc jeśli go uruchomię, jak widać, minus pięć jeden pięć dziesięć trzydzieści cztery, dziewięćdziesiąt dziewięć i tysiąc.
Co jeśli chciałbym usunąć BSD, które usuwają na przykład, spróbujmy usunąć element, który nie jest obecny
w drzewie wyszukiwania binarnego.
W zasadzie nic się nie wydarzy, ponieważ nie jesteśmy w stanie znaleźć tego przedmiotu.
Więc nic się nie dzieje.
Co jeśli chcielibyśmy usunąć na przykład tysiąc, to jeśli je uruchomimy, to jak
widać, tysiące zniknęły.
Co jeśli chcielibyśmy usunąć na przykład węzeł główny 10?
Jeśli usuniemy dziesięć, dziesięć będzie węzłem głównym z dwójką dzieci.
Zasadniczo jest to najbardziej złożony scenariusz.
Zobaczmy więc, czy działa dobrze, czy nie.
Jak widać, udało nam się usunąć pierwszy element.
Co jeśli chcielibyśmy usunąć na przykład minus pięć, a następnie minus pięć zostały usunięte?
Co jeśli chcielibyśmy usunąć, na przykład, trzydzieści cztery niż trzydzieści cztery zostaną usunięte?
Dziewięćdziesiąt dziewięć.
Możemy usunąć 99 bez żadnego problemu.
Zasadniczo w ten sposób możemy usunąć dany element z binarnego drzewa wyszukiwania.
Musimy tylko sprawić, by drapieżnik zobaczył drapieżników lub jest największym przedmiotem w lewym poddrzewie.
Właśnie dlatego nazywamy to lewym węzłem.
I ciągle wywołujemy tę funkcję rekurencyjnie w prawym poddrzewie, ponieważ szukamy największego elementu.
Następnie musimy wymazać przedmioty, a następnie wywołać funkcję rekurencyjnie, ponieważ udało nam się
zredukować najbardziej skomplikowany problem do problemu liścia północnego.
A węzeł liścia po prostu usunie dany węzeł liścia.
Musimy zaktualizować rodzica.
Dlatego jeśli wiemy, że był rodzicem w klasie węzłów, implementacja byłaby o wiele bardziej
złożona.
Musielibyśmy zaimplementować wiele wywołań funkcji rekurencyjnych i tak dalej.
Tak czy inaczej, w ten sposób radzimy sobie z operacjami binarnymi.
Porozmawiajmy o złożoności czasu wykonywania.
Wstawienie ponownie zamówiło niski poziom, złożoność czasu działania.
Więc dziennik audio.
Ale w czym problem?
Boort.
Jeśli drzewo jest zrównoważone, co oznacza, że wycięte drzewo zawiera w przybliżeniu taką samą ilość przedmiotów.
Następnie prawe miękkie drzewo.
Jest to zasadnicza wada drzew binarnych wyszukiwania polegająca na tym, że wszystkie operacje mają logarytmiczną złożoność czasu
działania, co jest bardzo, bardzo dobre.
Problem polega jednak na tym, że jeśli drzewo nie jest zrównoważone, oznacza to, że złożoność czasu pracy może zostać zredukowana
do czasu pracy liniowej.
Złożoność odwróconego przypadku Canario i liniowy czas działania.
Złożoność nie jest najlepsza z możliwych.
Dlatego właśnie w nadchodzącym wykładzie porozmawiamy o. re. drzewa i czerwone czarne drzewa.
I dojdziemy do wniosku, że za pomocą rotacji możemy upewnić się, że lewe
poddrzewo zawiera w przybliżeniu taką samą liczbę elementów, jak prawe poddrzewo.
Zasadniczo możemy się upewnić, że złożoność czasu wykonywania będzie logiem audio i bez względu na wszystko.
We wszystkich przypadkach przeciętny przypadek Canario, najlepszy przypadek i najgorszy przypadek.
O tym właśnie powiemy w kolejnych rozdziałach.
Dzięki za oglądanie.