[Powered by Google Translate] [Szukaj binarny] [Patrick Schmid - Harvard University] [To jest CS50. - CS50.TV] 

Gdybym dał ci listę nazwisk Disney znaków w porządku alfabetycznym i poprosił o znalezienie Mickey Mouse, jak byś się za to zabrać? Oczywistym sposobem byłoby przeszukać listę od początku i sprawdzić każdą nazwę, aby zobaczyć, czy jest Mickey. Ale jak można przeczytać Aladdin, Alice, Ariel, i tak dalej, można szybko sobie sprawę, że zaczynając od początku listy nie był dobry pomysł. Okay, może powinieneś zacząć pracować wstecz od końca listy. Teraz możesz czytać Tarzan, Stich, Królewna Śnieżka, i tak dalej. Mimo to, to nie wydaje się najlepszym sposobem przejść o nim. 

Cóż, kolejny sposób, że można go o to robi to, aby spróbować zawęzić lista nazwisk, że trzeba patrzeć. Skoro wiesz, że są w porządku alfabetycznym, można po prostu spojrzeć na nazwiska w środku listy i sprawdzić, czy Mickey Mouse jest przed lub po tej nazwie. Patrząc na nazwiska w drugiej kolumnie , że zdajesz sobie sprawę, że M Mickey przychodzi po J dla Jasmine, więc trzeba po prostu zignorować pierwszą połowę listy. Potem pewnie patrzeć na szczycie ostatniej kolumnie i widzę, że zaczyna się od Rapunzel. Mickey jest przed Rapunzel; wygląda możemy zignorować ostatnią kolumnę, jak również. Kontynuując strategię wyszukiwania, można szybko zobaczyć, że Mickey jest w pierwszej połowie pozostałej listą nazw i wreszcie znaleźć Mickey ukrywając między Merlinem i Minnie. 

, Co po prostu nie było w zasadzie binary search. Jak to nazwa wskazuje, wykonuje swoją strategię poszukiwania w binarnym materii. Co to znaczy? Cóż, biorąc pod uwagę listę sortowanych elementów, sprawia, że ​​algorytm wyszukiwania binarnego binarnego decyzję - lewo lub w prawo, większa lub mniejsza, przed lub po alfabetycznie - w każdym punkcie. Teraz, gdy mamy nazwę, która idzie w parze z tym algorytmem wyszukiwania, Spójrzmy na inny przykład, tym razem z listy posortowanych numerów. Powiedzmy, że szukasz numeru 144 w tym listy posortowanych numerów. Podobnie jak wcześniej, możemy znaleźć numer, który znajduje się w środku - która w tym przypadku wynosi 13 - 144 i czy jest większa lub mniejsza niż 13. Ponieważ jest wyraźnie większa niż 13, możemy ignorować wszystko, co jest 13 lub mniej i po prostu skupić się na pozostałej połowy. Ponieważ mamy parzystą liczbę pozycji w lewo, po prostu wybrać numer, który jest blisko centrum. W tym przypadku mamy do wyboru 55. Moglibyśmy tak łatwo wybrać 89. Okay. Ponownie, 144 jest większa niż 55, więc przejść do prawej. Na szczęście dla nas, następna liczba środku jest 144, jeden szukamy. Tak więc, aby wybrać 144 stosując wyszukiwanie binarne, jesteśmy w stanie go znaleźć w zaledwie 3 krokach. Gdybyśmy wykorzystali liniowe przeszukiwanie tutaj zajęłoby nam 12 kroków. W rzeczywistości, ponieważ metoda wyszukiwania połówki liczbę elementów musi patrzeć na każdym kroku, to znajdź element jest wyszukiwany w około dzienniku liczby elementów na liście. Teraz wiemy już 2 przykłady, rzućmy okiem na niektóre Pseudokod dla funkcji rekurencyjnej, który implementuje wyszukiwanie binarne. Zaczynając od góry, widzimy, że musimy znaleźć funkcję, która pobiera 4 argumenty: klucz, tablica, min i max. Kluczem jest numer, który szukamy, więc 144 w poprzednim przykładzie. Tablica jest lista numerów szukamy. Min i max są wskaźniki pozycji minimalnej i maksymalnej że jesteśmy obecnie patrząc na. Więc kiedy zaczynamy, min będzie zero i max będzie maksymalna indeksu tablicy. Jak zawęzić wyszukiwanie w dół, będziemy aktualizować MIN i MAX być tylko zakres, który wciąż szuka w. 

Pomińmy do interesującej części pierwsze. Pierwszą rzeczą, jaką możemy zrobić, to znaleźć punkt środkowy, Indeks, który jest w połowie drogi pomiędzy min i max w tablicy, że nadal rozważa. Patrząc na to w tablicy wartości w tym miejscu środkowym i sprawdzić, czy numer, który szukamy jest mniejsza niż tego klucza. Jeśli liczba w tej pozycji jest mniejsza, to znaczy, jest większy niż element z numerami na lewo tej pozycji. Więc możemy wywołać funkcję wyszukiwania binarnego ponownie ale tym razem aktualizując min i parametry max czytać tylko pół , która jest większa niż lub równa wartości po prostu sprawdzić. Z drugiej strony, jeśli klawisz jest mniejsza niż liczba w bieżącym środkowego tablicy chcemy iść w lewo i ignorować wszystkie numery, które są większe. Ponownie wzywamy przeszukiwanie binarne ale tym razem z zakresu min i max aktualizowane włączyć tylko dolną połowę. Jeżeli wartość na obecnym środkowym w tablicy nie jest ani większy niż nie mniejsze niż klucz, a następnie musi być równa do klucza. Tak więc możemy po prostu wrócić bieżący indeks punktu środkowego, a skończymy. Wreszcie, sprawdzanie jest dla przypadku, że liczba w rzeczywistości nie jest w tablicy liczb szukamy. Jeżeli maksymalny wskaźnik zakresu, że szukamy jest coraz mniej niż minimum, co oznacza, że ​​posunęliśmy się za daleko. Ponieważ liczba nie była w tablicy wejście, wracamy -1 aby wskazać, że nic nie znaleziono. 

Można zauważyć, że w przypadku tego algorytmu do pracy, Lista numerów ma być sortowana. Innymi słowy, możemy znaleźć tylko 144 za pomocą wyszukiwania binarnego jeśli wszystkie numery są uporządkowane od najniższego do najwyższego. Jeśli nie było, to nie może wyłączyć połowę ilości, przy każdym kroku. Więc mamy 2 opcje. Albo możemy wziąć niesortowanych listę i sortować przed użyciem wyszukiwanie binarne, czy możemy mieć pewność, że lista numerów jest sortowana jak dodać numery do niego. Tak więc, zamiast sortowania tylko gdy mamy do wyszukiwania, dlaczego nie przechowywać listę posortowaną w każdej chwili? 

Jednym ze sposobów, aby utrzymać listę numerów posortowane jednocześnie umożliwiając jeden dodać lub przenieść numery z tej listy jest za pomocą czegoś, co nazywa drzewo binarne wyszukiwania. Drzewo wyszukiwania binarnego jest strukturą danych, która ma 3 właściwości. Po pierwsze, po lewej stronie każdego węzła poddrzewo zawiera tylko wartości, które są mniej niż lub równa wartości węzła. Po drugie, z prawego poddrzewa węzła zawiera tylko wartości, które są większe niż lub równa wartości węzła. I wreszcie, po lewej i prawej poddrzew wszystkich węzłów są również binarne drzewa wyszukiwania. Spójrzmy na przykład z takimi samymi numerami używaliśmy wcześniej. Dla tych z was, którzy nigdy nie widzieli drzewo informatyka przed, Zacznę mówiąc, że drzewo rośnie informatyka dół. Tak, w przeciwieństwie do drzew jesteś przyzwyczajony do, korzeń drzewa informatyki jest na górze, Liście i na dole. Każdy małe pole nazywa węzła, a węzły są połączone ze sobą krawędziami. Więc korzeń tego drzewa jest węzeł z wartością 13, która ma 2 dzieci węzły z wartościami 5 i 34. Poddrzewo jest drzewo, które powstaje po prostu patrząc w podsekcji całego drzewa. 

Na przykład, lewy poddrzewa węzeł 3 jest utworzony przez drzewa węzłów, 0, 1 i 2. Tak więc, jeśli chcemy wrócić do właściwości drzewa wyszukiwania binarnego, widzimy, że każdy węzeł w drzewie spełnia wszystkie 3 nieruchomości, a mianowicie, lewego poddrzewa zawiera tylko wartości, które są mniej niż lub równa wartości węzła; prawego poddrzewa wszystkich węzłów zawiera jedynie wartości, które są większe lub równe wartości węzła oraz zarówno lewego i prawego poddrzewa wszystkich węzłów, które są drzewa binarne wyszukiwania. Mimo to drzewo wygląda inaczej, jest to ważne binary search tree dla tych samych numerów. W rzeczywistości, istnieje wiele sposobów, które można tworzyć binary search tree ważne od tych liczb. Dobrze, wróćmy do pierwszego stworzyliśmy. Więc co możemy zrobić z tymi drzewami? Cóż, możemy w bardzo prosty sposób znaleźć wartości minimalne i maksymalne. Minimalne wartości można znaleźć, zawsze będzie w lewo dopóki nie ma więcej węzłów do odwiedzenia. Odwrotnie, aby znaleźć maksymalną tuż po prostu przechodzi do prawego w każdym czasie. 

Znalezienie inny numer nie minimalnej lub maksymalnej jest jest tak samo łatwe. Powiedzmy, że szukasz numeru 89. Po prostu sprawdzić wartość każdego węzła i iść w lewo lub w prawo, zależnie od tego czy wartość węzła jest mniejszy lub większy niż jeden szukamy. Więc, zaczynając od podstaw 13, widzimy, że 89 jest większa, i tak idziemy w prawo. Następnie widzimy węzeł 34, i znowu idziemy w prawo. 89 jest w dalszym ciągu większe niż 55, tak, że nadal będzie do prawej. Następnie wymyślić węzła o wartości 144 i idź w lewo. I oto 89 jest tu. 

Inną rzeczą, którą możemy zrobić, to wydrukować wszystkie numery, wykonując inorder przechodzenie. Inorder traversal oznacza drukować wszystko w lewo poddrzewo poprzez drukowanie węzeł się a następnie poprzez drukowanie wszystkiego w prawym poddrzewie. Na przykład, weźmy nasze ulubione drzewo wyszukiwania binarnego i wydrukować numery posortowanych. Zaczynamy u podstaw 13, ale przed drukowaniem 13 mamy do wydrukowania wszystko w lewo poddrzewa. Więc idziemy do 5. Mamy jeszcze głębiej w dół drzewa, aż znajdziemy lewej najwięcej węzła która jest zero. Po wydrukowaniu zerowej, wracamy do 1 i wydrukować to. Potem idziemy do prawego poddrzewa, które jest 2 i wydrukować to. Teraz, kiedy skończysz z tym poddrzewie możemy wrócić do 3 i wydrukować. Kontynuując powrotem, drukujemy 5 i 8. Teraz, po zakończeniu całego lewego poddrzewa, możemy wydrukować 13 i rozpocząć pracę na prawym poddrzewie. Mamy hop aż do 34, ale przed drukowaniem 34 musimy wydrukować jego lewego poddrzewa. Więc wydrukować 21, a następnie dostać się do wydrukowania 34 i odwiedzić jego prawego poddrzewa. Od 55 nie ma lewego poddrzewa, możemy wydrukować go i przejdź do jego prawego poddrzewa. 144 ma lewą poddrzewa i wydrukować więc 89, a następnie przez 144, wreszcie najbardziej prawym węzłem 233. Nie masz go, wszystkie numery są drukowane w kolejności od najniższego do najwyższego. 

Dodając coś do drzewa jest stosunkowo bezbolesny, jak również. Wszystko, co musimy zrobić, to upewnić się, że idziemy za 3 wyszukiwania właściwości drzewa binarnego a następnie wstawić wartości, gdzie jest miejsce. Powiedzmy, że chcemy wstawić wartość 7. Od 7 jest mniejsza niż 13, idziemy w lewo. Ale jest większy niż 5, tak, że przechodzenie w prawo. Ponieważ jest to mniej niż 8, a 8 jest węzeł liścia, to dodaje się 7 do 8 lewej dziecka. Voila! Dodaliśmy numer do naszego drzewa wyszukiwania binarnego. 

Jeśli możemy dodać rzeczy, lepiej być w stanie usunąć rzeczy, jak również. Niestety dla nas, usuwania jest trochę bardziej skomplikowane - nie dużo, ale tylko trochę. Istnieją 3 różne scenariusze, które musimy wziąć pod uwagę podczas usuwania elementów z drzewa binarne wyszukiwania. Po pierwsze, jest najprostszym przypadku jest to, że element węzeł liścia. W tym przypadku, po prostu usunąć i przejść z naszej działalności. Powiedzmy, że chcesz usunąć 7 że właśnie dodane. Cóż, po prostu znaleźć, usuń go, a to jest to. Następna sprawa, jeśli węzeł ma tylko 1 dziecko. Tutaj możemy usunąć węzeł, ale najpierw musimy się upewnić, połączyć poddrzewa, które teraz w lewo nadrzędnymi do nadrzędnego węzła po prostu usunięte. Powiedzmy, że chcesz usunąć 3 z naszego drzewa. Bierzemy element podrzędny tego węzła i dołączyć go do nadrzędnego węzła. W tym przypadku, jesteśmy teraz mocowania 1 do 5. Działa to bez problemu, ponieważ wiadomo, w zależności od własności wyszukiwania binarnego drzewa że wszystko w lewo poddrzewo 3 było mniej niż 5. Teraz, 3'S poddrzewo jest pod opieką, możemy go usunąć. Trzecia i ostatnia sprawa jest najbardziej skomplikowana. Tak jest w przypadku, gdy węzeł chcemy usunąć ma 2 dzieci. Aby to zrobić, musimy najpierw znaleźć węzeł, który ma z kolei największą wartość, zamienić dwa, a następnie usunąć węzeł pytanie. Wskazówka węzeł, który ma następna największa wartość nie może mieć 2 dzieci się ponieważ jego lewa dziecko będzie lepszym kandydatem na następne największe. Dlatego usuwanie węzła z 2 dzieci wynosi swapping 2 węzłów, a następnie usuwając jest obsługiwany przez 1 z 2 wymienionymi powyżej regułami. Na przykład, powiedzmy, że chcemy usunąć węzeł główny, 13. Pierwszą rzeczą, jaką możemy zrobić, to znaleźć następną największą wartość w drzewie która w tym przypadku wynosi 21. Następnie zamienić 2 węzłów, co czyni 13 liści i 21 centralny węzeł grupy. Teraz możemy po prostu usunąć 13. 

Jak wspomniałem wcześniej, istnieje wiele możliwych sposobów, aby poprawny drzewo wyszukiwania binarnego. Niestety dla nas, niektóre są gorsze od innych. Na przykład, co się dzieje, kiedy możemy zbudować drzewo binarne wyszukiwania z posortowanej listy liczb? Wszystkie numery są po prostu dodaje się w prawo w każdym kroku. Gdy chcemy wyszukać numer, nie mamy wyboru, ale tylko patrzeć na prawo na każdym kroku. To nie jest lepszy niż liniowy wyszukiwania. Mimo, że nie obejmie ich tutaj, istnieją inne, bardziej złożone, struktury danych, które składają się, że tak się nie stanie. Jednakże, jeden prosty, co można wykonać w celu uniknięcia jest do po prostu losowo Shuffle wartości wejściowych. Jest wysoce prawdopodobne, że przez przypadek losowy tasuje lista numerów jest posortowana. Jeśli tak było, kasyna nie zatrzymam się w biznesie na długo. 

Nie masz go. Teraz wiesz o binarnego przeszukiwania i wyszukiwania drzew binarnych. Jestem Patrick Schmid, a to CS50. [CS50.TV] Oczywistym sposobem byłoby przeszukać listę od ... [beep] ... Liczba elementów ... yep [Śmieje się] ... Post węzeł 234 ... augh. >> Yay! To było -