W tym wykładzie będziemy rozmawiać o tym, jak wstawiać elementy do binarnego drzewa wyszukiwania i
jak wyszukiwać dowolny element.
Na przykład chcielibyśmy wstawić 12 i oczywiście, ponieważ struktura danych jest pusta.
Pierwszym elementem, który wstawimy, będzie węzeł główny drzewa wyszukiwania binarnego.
Mamy więc węzeł główny o wartości 12.
OK, a co by było, gdybyśmy chcieli wstawić cyfrę cztery?
Oczywiście musimy zacząć od węzła głównego, ponieważ mamy dostęp wyłącznie do węzła głównego.
Więc co musimy zrobić?
Musimy sprawdzić, czy wartość w rozważanym przez nas węźle jest większa czy mniejsza niż
wartość, którą chcielibyśmy wstawić.
Możesz zadać pytanie, dlaczego?
Ponieważ jest to topologia drzew wyszukiwania binarnego, lewe dzieci są mniejsze niż rzeczywisty węzeł, a prawe
dzieci są większe niż rzeczywisty węzeł.
Więc jeśli mamy wartość dla, chcielibyśmy wstawić i mamy wartość, którą mamy w rzeczywistym węźle, o której
wiemy na pewno, że musimy iść w lewo, ponieważ lewe dziecko jest mniejsze od rodzica.
Tak więc, ponieważ nie ma lewego dziecka, tworzymy nowy węzeł w drzewie wyszukiwania binarnego z wartością for.
OK, a co by było, gdybyśmy chcieli wstawić osiem?
Ponownie musimy zacząć od węzła głównego i musimy nadal porównywać rzeczywistą wartość węzła z
wartością, którą chcielibyśmy wstawić.
Osiem jest mniejsze niż 12.
Idziemy więc w lewo i musimy ponownie porównać pozycje.
Mamy wartość i mamy wartość osiem.
Chcielibyśmy wstawić osiem jest większe niż cztery.
Musimy więc iść w prawo.
Ale ponieważ nie ma właściwego dziecka, dlatego tworzymy właściwe dziecko z wartością.
A co by było, gdybyśmy chcieli ponownie wstawić 20, nie mamy innego wyjścia, jak zacząć od węzła
głównego 20 jest większy niż 12.
Idziemy więc w prawo.
Ale ponieważ nie ma właściwego dziecka, tworzymy właściwe dziecko z wartością.
Dwadzieścia jeden.
Jeśli chcielibyśmy ponownie wstawić dwadzieścia siedem, musimy zacząć od węzła głównego.
Dwadzieścia siedem to więcej niż dwanaście, więc musimy iść w prawo.
Dwadzieścia siedem to więcej niż dwadzieścia.
Musimy więc iść w prawo.
Ale ponieważ nie ma właściwego dziecka, tworzymy właściwe dziecko z wartością.
Dwadzieścia siedem.
OK, a co by było, gdybyśmy chcieli wstawić szesnaście.
Musimy zacząć od węzła głównego.
Szesnaście jest większe niż dwanaście, więc musimy iść dalej w prawo.
16 jest mniejsze niż 20, więc musimy iść dalej w lewo.
Ale ponieważ nie ma lewego dziecka, tworzymy lewe dziecko z wartością.
Szesnaście.
Zasadniczo jest to podstawowa zasada operacji binarnej, którą musimy wziąć pod uwagę w węźle po
lewej stronie.
Jeśli wartość jest mniejsza i musimy wziąć pod uwagę węzeł po prawej stronie, jeśli podana wartość jest większa
niż rzeczywista wartość węzła.
OK, a co by było, gdybyśmy chcieli wstawić na przykład taki, który musimy zacząć od węzła głównego.
Jeden jest mniejszy niż dwanaście, więc idziemy w lewo, jeden jest mniejszy niż cztery, więc idziemy w lewo.
Ale ponieważ nie ma lewego dziecka, tworzymy lewe dziecko z wartością włączoną.
Zasadniczo w ten sposób możemy wstawiać wartości jedna po drugiej.
Jak widać, jest to prawidłowe drzewo wyszukiwania binarnego, ponieważ wszystkie lewe dzieci są mniejsze od
rodzica, a wszystkie prawe dzieci są większe niż rodzic.
Osiem jest większe niż cztery.
20 jest większe niż dwanaście.
Dwadzieścia siedem to więcej niż dwadzieścia.
Jeden jest mniejszy niż szesnaście, jest mniejszy niż dwadzieścia i tak dalej.
Jest to więc prawidłowe drzewo wyszukiwania binarnego, które stworzyliśmy.
I dlaczego to jest dobre.
Bo jeśli szukamy na przykład ośmiu, dlaczego mamy to robić.
Oczywiście mamy dostęp wyłącznie do węzła głównego.
Musimy więc zacząć od węzła głównego i porównać podane wartości.
Osiem jest mniejsze niż dwanaście, więc rekurencyjnie rozważamy lewą trzecią podrzędną.
Więc co to znaczy?
Jak widać po pojedynczym sprawdzeniu, odrzuciliśmy połowę struktury danych, więc udało nam się
odrzucić 16, 20 i 27, ponieważ wiemy na pewno, że osiem jest mniejsze niż dwanaście.
A jeśli chodzi o właściwy Sabari, zawiera elementy, które są większe niż dwanaście.
Możemy więc dojść do wniosku, że musimy wziąć pod uwagę lewe poddrzewo i nie ma potrzeby
sprawdzania prawego poddrzewa.
I właśnie dlatego właśnie skonstruowaliśmy drzewa wyszukiwania binarnego w ten sposób, ponieważ w
każdej pojedynczej iteracji możemy odrzucić połowę oryginalnego zestawu danych.
Jest bardzo podobny do wyszukiwania binarnego i dlatego możemy skończyć z logarytmiczną złożonością czasu wykonywania.
Więc OK, rozważamy wierzchołek czwarty, więc mamy wartość osiem.
My.
Szukają pomocy jest większa niż cztery, więc musimy wziąć pod uwagę odpowiednie poddrzewo i to jest
wartość, której szukamy dla pieniędzy.
Jeśli chcielibyśmy znaleźć maksymalny przedmiot, wiemy na pewno, że większe przedmioty znajdują się po lewej
stronie Sabari.
Na przykład 20 jest większe niż 12.
Dwadzieścia siedem to więcej niż 20.
Więc jeśli chcemy znaleźć maksymalny przedmiot, to co musimy zrobić?
Przede wszystkim musimy jak zwykle zacząć od węzła głównego i musimy rozważyć właściwe dziecko,
aż dojdziemy do wniosku, że rzeczywisty węzeł nie ma żadnego właściwego dziecka.
Możemy dojść do wniosku, że to największa pozycja.
Tak więc w zasadzie maksymalny element w drzewie wyszukiwania binarnego to najbardziej prawy element w drzewie, taki jak struktura lub cokolwiek
innego.
Minimalna pozycja.
Oczywiście wiemy na pewno, że lewe dziecko jest mniejsze od rodzica.
Możemy więc powiedzieć, że lewe poddrzewo zawiera elementy mniejsze niż węzeł nadrzędny.
Co więc musimy zrobić, jeśli chcemy ponownie znaleźć minimum?
Musimy zacząć od węzła głównego i musimy rozważyć lewe dzieci, aż dojdziemy do wniosku, że rzeczywisty
węzeł nie ma żadnego lewego dziecka.
I możemy dojść do wniosku, że jest to najmniejsza wartość w chirurgii binarnej.
Jak widać, jest w porządku, ponieważ jeden jest najmniejszą pozycją w drzewie wyszukiwania binarnego.
Zatem minimalna pozycja w drzewie wyszukiwania binarnego to pozycja znajdująca się najbardziej po lewej stronie w strukturze drzewa.
Więc w zasadzie możemy dojść do wniosku, że jeśli użyjemy tych cech, lewe dziecko jest mniejsze niż rodzic,
wiemy, że prawe dziecko jest większe niż węzeł nadrzędny.
Następnie przechowujemy pozycje w posortowanej kolejności.
A dlaczego to jest dobre?
Ponieważ w każdej iteracji możemy odrzucić połowę oryginalnego zbioru danych.
W związku z tym możemy otrzymać logarytmiczną złożoność czasu wykonywania.
Ale oczywiście to prawda.
Jeśli wyszukiwanie binarne jest zrównoważone, nawet drzewo wyszukiwania binarnego jest niezrównoważone.
Na przykład w tym przykładzie szukamy medium item.
Wtedy nie zamierzamy odrzucać połowy zestawu danych w każdej iteracji, ponieważ nie ma lewego poddrzewa, jak
widać.
Dlatego właśnie o tym rozmawialiśmy.
Powinniśmy utrzymać drzewo na minimalnym poziomie, ponieważ oznacza to, że struktura podobna do drzewa
zostanie zrównoważona.
A jeśli struktura podobna do drzewa jest zrównoważona, możemy odrzucić połowę struktury
danych w każdej iteracji, co oznacza, że chociaż logarytmiczna złożoność czasu działania Laganna, jeśli drzewo zostanie
niezrównoważone, to tę logarytmiczną złożoność czasu wykonania można zredukować do nawet liniowej złożoność czasowa.
Tak więc wstawiamy elementy do drzewa wyszukiwania binarnego i tak możemy wyszukiwać dany element.
Dzięki za oglądanie.