[MUZYKI] DOUG LLOYD: Więc byliśmy inching bliżej i bliżej, że Święty Graal danych struktury, który można włożyć się, usunąć z, i spójrz w górę w stałym czasie. Dobrze. To swego rodzaju siatkę. Chcemy być w stanie zrobić rzeczy bardzo, bardzo szybko. 

Mają znaleźliśmy go tutaj, kiedy mówimy o próbach? Cóż, rzućmy okiem. Tak więc widzieliśmy kilka różne struktury danych które obsługuje mapowanie tzw pary klucz-wartość, mapowanie jakiś kawałek danych do innej części danych więc wiemy, gdzie znaleźć Informacje zawarte w strukturze. 

Tak na tablicy, na przykład, Kluczowym elementem jest wskaźnik lub tablica Położenie 0 lub tablica 1 i tak dalej. A wartość jest dane że istnieje w tym miejscu. Więc co jest przechowywane w tablicy 0? Jakie są przechowywane w tablicy 1, w porównaniu z zaledwie 0 i 1, co byłoby klucze. 

Z tabeli mieszania to rodzaj tej samej idei. Z tabeli mieszania, mamy ten hash funkcja, która generuje kody hash. Tak więc kluczem jest kod skrótu danych. I wartość, w szczególności rozmawialiśmy o łańcuchowym w wideo na stołach z cebulą, jest to, że wiąże lista danych że skróty do tej hashcode. Dobrze. Co innego podejścia Ten sposób, chociaż? Co do sposobu, w którym Kluczem jest gwarantowane jest unikatowy, w przeciwieństwie do tabeli mieszania, gdzie moglibyśmy kończy się z dwóch części danych o tej samej hashcode. I wtedy mamy do czynienia z że albo sondowania lub więcej najlepiej łączenia naprawić ten problem. 

Więc teraz możemy zagwarantować że nasz klucz będzie wyjątkowy. A co, jeśli nasza wartość była tylko coś tak proste jak prawda i fałsz, który mówi nam, czy czy nie, że informacja występuje w strukturze? Boolean może być tak proste, jak się trochę. Realistycznie to chyba bajt bardziej prawdopodobne niż trochę. Ale to o wiele mniejsze niż przechowywania może ciąg 50 znaków, na przykład. 

Tak stara, podobna do mieszania tabele, które łączą tablice i związane lista, próbuje połączyć tablice, struktury, i wskaźniki razem przechowuje dane ciekawy sposób to całkiem inny od coś widzieliśmy do tej pory. Teraz możemy korzystać z danych w mapie drogowej aby poruszać tę strukturę danych. A jeśli możemy śledzić plan działania, jeśli to możliwe postępuj według danych z początku do końca, będziemy wiedzieć, czy te dane istnieć w trie. 

A jeśli nie możemy śledzić mapę od co oznacza do końca w ogóle, dane nie mogą istnieć. Ponownie, klucze tutaj muszą być unikalne. I tak, w przeciwieństwie do tabeli mieszania, że ​​nigdy nie będziesz mamy do czynienia z kolizji tutaj. I nie ma dwóch fragmentów danych mają dokładnie tę samą mapę drogową chyba, że ​​dane są identyczne. 

Jeśli wstawiamy Jana, a następnie szukamy Jana. To dwa identyczne kawałki Dane, w prawo, my patrząc przez. Ale w inny sposób, dwa kawałki danych są na pewno mają unikalne mapy drogowe przez tę strukturę danych. I mamy zamiar przyjrzeć się wizualny tego za chwilę. 

Zrobimy to, starając się utworzenie nowej struktury, mapowanie następujące pary wartość klucza. W tym przypadku nie będziemy korzystać coś tak prostego jak Boolean. My rzeczywiście będzie przechowywać ciąg. I że ciąg będzie być nazwa uczelni. 

Oraz kluczowy będzie rok gdy uniwersytet został założony. Wszystkie lata na uczelni będą cztery cyfry. I tak będziemy korzystać z tych czterech cyfr do poruszać się w tej strukturze danych. I zobaczymy, znowu, jak my, że w ciągu sekundy. 

Na koniec drogi, zobaczymy nazwę uczelni, który odpowiada do tego klawisza, te cztery cyfry. Podstawową ideą jest trie to mamy główną trasą. Więc pomyśl o tym jak drzewo. I to jest podobne w pisowni i koncepcji do drzewa. Generalnie, kiedy myślimy o drzewa w świecie rzeczywistym, mają korzeń, który jest w ziemi i rosną w górę i mają oddziały i mają liści. I w zasadzie idea trie jest dokładnie taka sama, oprócz tego, że korzeń jest zakotwiczony gdzieś w niebie. I pozostawia się na dole. 

Więc to jest trochę jak przy drzewo i po prostu przerzucanie go do góry nogami. Ale nadal istnieją oddziały. A ci, byłoby nasze drogi, będą to nasze połączenia od korzenia do liści. W tym przypadku te ścieżki, te gałęzie oznaczone są cyframi, które mówią nam w którą stronę iść, skąd jesteśmy. 

Jeśli widzimy 0, idziemy w dół tej branży, jeśli widzimy 1, idziemy w dół tej branży, i tak i tak dalej. Cóż, co to oznacza? Cóż, to oznacza, że w każdym punkcie połączenia i każdy węzeł w średniej i każdy oddział, istnieją 10 możliwe miejsca, że ​​możemy iść. Więc istnieje 10 wskazówek z każdego miejsca. 

I to jest, gdy próbuje mogą uzyskać trochę skomplikowane dla kogoś kto nie ma dużo doświadczenie w dziedzinie informatyki wcześniej. Ale próbuje są naprawdę dość niesamowite. A jeśli masz możliwość pracy z nimi i jesteś w stanie kopać w i eksperymentować z nimi, są naprawdę bardzo interesujące struktury danych do pracy. Jeśli chcemy, aby wstawić element do trie, wszystko musimy zrobić jest zbudować poprawną ścieżkę od korzenia do liścia. Oto, co na każdym kroku wraz sposób może wyglądać. Jedziemy do zdefiniowania nowego dane Struktura nowego węzła nazywany TRIE. 

I wewnątrz tych danych Struktura są dwa kawałki. Mamy zamiar przechowywać nazwa uczelni. I mamy zamiar przechowywać tablica wskaźników do innych węzłów o tym samym rodzaju. Tak, znowu, jest to ten rodzaj od koncepcji wszędzie jesteśmy, na 10 możliwe miejsca możemy iść. Jeśli widzimy 0, idziemy w dół tę gałąź. Jeśli widzimy 1, ta gałąź, i tak dalej, i tak dalej, i tak dalej. Jeśli mówimy, 9, idziemy w dół tę gałąź. Tak więc w każdym punkcie skrzyżowania, możemy iść 10 możliwych miejsc. Więc każdy węzeł musi zawierać 10 wskazówek do innych węzłów, do 10 innych węzłów. 

I przechowywania danych mamy jest tylko nazwa uczelni. Więc zbudować TRIE. Miejmy wstawić kilka przedmiotów do naszego trie. Tak więc na samym szczycie, to jest nasz węzeł główny. Jest to prawdopodobnie będzie coś idziesz do globalnej deklaracji. I masz zamiar globalnie utrzymanie wskaźnik do tego węzła zawsze. 

Masz zamiar powiedzieć, Korzeń jest równa, a ty jesteś będzie malloc sobie węzeł TRIE. I nigdy nie będziemy ponownie dotknąć korzeni. Za każdym razem kiedy chcesz rozpocząć nawigację za pośrednictwem, ustawić inny wskaźnik równa korzenia, takich jak trav, która jest przykładem I używać w wielu moich filmów tu na stosy i kolejki i listy linków i tak dalej. 

Ustawić inny wskaźnik nazywa trav do przechodzenia. I używasz TRAV do nawigacji przez strukturę danych. Zobaczmy więc, jak to może wyglądać. Więc teraz, co ma węzeł wygląda? Cóż, tak jak naszych danych Deklaracja struktury wskazane, mamy ciąg, który w tym przypadku jest pusta. Nic tu nie ma. 

A tablica z 10 wskaźników. A teraz, tylko mają 1 węzeł w tym trie. Nie ma nic innego w nim. Więc wszystkie 10 osób wskaźniki punktowe na null. To właśnie czerwony wskazuje. 

Miejmy wstawić ciąg Harvarda. Miejmy włożyć Uniwersytet Harvard do tego trie, które została założona w roku 1636. Chcemy użyć klawisza, 1636 roku, aby powiedzieć nam, gdzie jesteśmy będzie przechowywać Harvard w trie. Teraz, w jaki sposób możemy to zrobić? 

To może wyglądać tak. Zaczynamy u nasady. I mamy te 10 miejsc możemy iść. Korzeń jest tak jak każdy drugi węzeł trie. Jest 10 miejsc, gdzie idziemy stąd. 

Gdzie my prawdopodobnie chcesz iść, jeśli klucz jest 1636? Jest naprawdę dwie opcje. Dobrze. Możemy zbudować klucz z od prawej do lewej i zacząć z 6. Albo możemy budować klucz z od lewej do prawej i zacząć 1. 

To prawdopodobnie więcej Intuicyjny jako człowieka rozumieć będziemy Wystarczy przejść od lewej do prawej. I tak, jeśli chcę wstawić Harvard do tego trie, Pewnie chcą rozpocząć zaczynając od korzenia patrząc na moje 10 opcji przede mną, mówiąc: Chcę iść ścieżką 1. OK. 

Teraz, 1 ścieżka jest aktualnie pusty. Więc jeśli chcę przejść tą drogą wstawić ten element w trie, Muszę malloc nowy węzeł, mają 1 wskazują tam, i to ja jestem dobry, aby przejść. 

Więc ja w zasadzie jestem ze Punkt, w którym stoję u korzeni drzewa i tym trie i istnieje 10 oddziałów. Ale każdy oddział ma bramy przed nim. Dobrze. Bo nie ma nic innego nie ma. Nie bezpieczne przejście. Oznacza to, że nie ma nic dół żadnej z tych oddziałów. Jeśli chcę, aby rozpocząć budowę coś, chcę usunąć bramę. Chcę usunąć bramę przed numerem 1. I chcę iść w dół, że. I chcę zbudować kolejne miejsce dla mnie, aby przejść. 

I to jest to, co zrobiłem tutaj. Tak więc 1 nie wskazuje już na null. Powiedziałem, że to bezpieczne, aby zejść tutaj. I zbudował inny węzeł. A kiedy się do tego węzła, ja mają inną decyzję. Gdzie ja mam dalej? 

Cóż, ja już poszła w dół 1. Więc teraz pewnie chce iść w dół 6. Dobrze. Znów mam 10 lokalizacje mogę wybrać. Więc teraz zejść numer 6. Więc jasne bramę przed numerem 6. I idę tam. I budowa kolejnego węzła. I już dotarł do kolejnego punktu połączenia. 

Znów mam 10 wyborów dla których mogę iść. Mam przeniesiony od 1 do 6. Więc teraz pewnie chce iść do 3. 3, nie ma gdzie mogę iść. Więc muszę oczyścić drogę i zbudować sobie nową przestrzeń. A następnie od 3, gdzie chcę iść? Chcę zejść 6. 

I znowu, musiałem oczyścić drogę, aby to zrobić. Więc teraz użyłem mój klucz do wstawienia stworzyć węzły i zacząć budować ten TRIE. Zacząłem się w katalogu głównym. Poszedłem na dół 1636. A teraz jestem na dnie nie w tym węźle. I może być w stanie zobaczyć go na ekranie. 

Jest podświetlone na żółto. To gdzie ja obecnie jestem. Mój klucz jest wykonywana. Byłem wyczerpany każdą pozycję w moim kluczem. Więc nie mogę iść dalej. Więc w tym momencie, wszystko co naprawdę musisz zrobić, to powiedzieć: OK. To tak jakby patrząc w ziemię, jeśli przewidując siebie jako tego rodzaju ścieżki z różnych połączeń. Rodzaj patrząc w dół i rodzaj Spray malowanie Harvard na ziemi. To jest nazwa tego. Wiesz, że to co jest w tym miejscu. Jeśli zaczynają się od korzenia i idziemy w dół 1 i 6, a następnie 3 i 6, gdzie jesteśmy? Cóż, jeśli spojrzymy w dół i widzimy, Harvard, a następnie wiemy, że Harvard było założona w 1636 roku w oparciu o sposób mamy do realizacji tej struktury danych. Więc mam nadzieję, że to było proste. Mamy zamiar zrobić jeszcze dwie wstawki. I miejmy nadzieję, że to pomoże zobacz to zrobić dwa razy więcej. 

A teraz włóż inną uczelnię. Załóżmy, włóż w to Yale trie. Yale został założony w 1701 roku. Będziemy więc rozpocząć się korzeń, jak zawsze. I ustawiamy wskaźnik przejścia. Mamy zamiar używać, aby poruszać się. Pierwszą rzeczą, którą chcesz zrobić, to przejść ścieżką 1. To pierwsza cyfra nasz klucz. Na szczęście jednak, nie robimy trzeba wykonywać żadnej pracy tym razem. Ścieżka 1 zostały już usunięte. I straciła gola wcześniej, kiedy było wstawienie Harvard w 1636 roku. Więc mogę spokojnie przejść dół 1 i właśnie tam. Jeśli można przesunąć w dół 1. 

Teraz jednak chcę iść do 7. I otworzyło drogę na 6. Wiem, że mogę bezpiecznie postępować ścieżką 6. Ale muszę przejść na ścieżce 7. Więc co mam zrobić? Cóż, tak jak wcześniej, tylko trzeba aby usunąć bramę, dostać się z drogi, i zbudować nowy węzeł z drogą 7. Po prostu tak. 

Więc teraz mam przeniósł 1, a następnie 7. A teraz zauważyć, że jestem jakby w sprawie tego nowego subbranch. Dobrze. Wszystko inne od 16 na, nie dbam o. Nie robię nic 16. Robię 17 rzeczy. 

Więc teraz, z 17 na, muszę rodzaj płoną tu nowe szlaki. Kolejny mój klucz jest cyfra 0. I oczywiście nie można dostać wszędzie. Właśnie zbudował ten węzeł. Tak wiem, że nie ma Ścieżki forward tutaj. Muszę więc zrobić jeden siebie. 

Więc malloc nowy węzeł i mają 0 pkt tam. A potem jeszcze raz, ja malloc Nowy węzeł ma jeden punkt i tam. Ponownie, już wyczerpane mój klucz, 1701. Więc patrzę w dół, a ja lakierniczych Yale. To jest nazwa tego węzła. 

A więc teraz, jeśli kiedykolwiek trzeba sprawdzić, czy Yale trie jest w tym, że zaczynają się od korzenia, Idę w dół 1701, i spojrzeć w dół. A jeśli widzę sprayu Yale malowane na ziemi, po czym Wiem, że istnieje w tej Yale trie. Zróbmy jeszcze jeden. Miejmy włożyć Dartmouth w to trie, która została założona w 1769 roku. 

Zacznij od korzenia ponownie. Moja pierwsza cyfra mojego klucza to 1. Mogę spokojnie przejść tą drogą. To już istnieje. Następna cyfra mojego klucza jest 7. Mogę spokojnie przejść tą drogą. Istnieje również. 

Mój następny jest 6. Stąd, skąd ja aktualnie jestem tam żółty w tym węzeł pośredni, 6 jest zablokowany off. Jeśli chcę iść tą drogą, Mam zbudować go samodzielnie. Więc będę malloc nowy węzeł i mają 6 punkt tam. A potem znowu, jestem płonącego nowe szlaki tutaj. 

Więc malloc nowy węzeł tak, że od że node-- numer trasy 9-- i teraz jeśli podróżujesz 1769, i spojrzeć w dół. Nie ma to obecnie Spray malowane tam. Mogę napisać Dartmouth. A ja włożona Dartmouth w trie. 

Więc to jest wstawianie rzeczy do trie. Teraz chcemy, aby szukać rzeczy. Jak mamy szukać rzeczy w trie? Cóż, to prawie ten sam pomysł. Teraz wystarczy użyć cyfr klucza aby sprawdzić, czy możemy poruszać się od korzenia tam, gdzie chcemy iść w trie. 

Jeśli uderzymy w ślepy zaułek w każdym punkcie, a następnie wiemy, że ten element nie istnieje albo, że ścieżka będzie zostały już usunięte. Jeśli robimy to przez całą drogę do koniec, wszystko co musisz zrobić, jest spojrzeć w dół i zobaczyć, czy to element szukamy. Jeśli tak, to sukces. Jeśli nie, nie. 

Warto więc szukać Harvard w tym trie. Zaczynamy u nasady. I znowu, będziemy utworzyć wskaźnik przejścia zrobić dla nas nasze ruchy. Z katalogu wiemy, że Pierwszym miejscem, musimy udać się 1, możemy to zrobić? Tak możemy. Jeśli bezpiecznie istnieje. Możemy tam iść. 

Teraz, następne miejsce musimy iść to 6. Czy ścieżka 6 istnieje tutaj? Tak, tak. Możemy iść ścieżką 6. A to w końcu tutaj. 

Możemy iść ścieżką stąd 3? Cóż, jak się okazuje, tak, że istnieje też. I możemy się na ścieżce 6 stąd? Tak możemy. 

Nie dość odpowiedział jeszcze pytanie. Jest jeszcze jeden krok, który jest obecnie musimy spojrzeć w dół i zobaczyć, czy to actually-- jeśli szukamy Harvardu, jest to, że co znajdziemy po tym wyczerpuje klucz? W przykładzie używamy tutaj, lata są zawsze cztery cyfry. Ale być może używasz na przykład, w którym warunki przechowywania słownika wyrazów. 

I tak zamiast 10 wskazówek dla mojej lokalizacji, może być 26. Po jednym dla każdej litery alfabetu. I są pewne słowa takie jak bat, który jest podzbiorem partii, na przykład. A więc nawet jeśli się do koniec klucza i spojrzeć w dół, nie może zobaczyć, co szukasz. 

Więc zawsze masz do przejścia cała ścieżka, a następnie jeśli były z powodzeniem w stanie przemierzać całą ścieżkę, spojrzeć w dół i zrobić jedną ostatecznego potwierdzenia. Czy to, co szukam? Cóż, patrzę w dół po uruchomieniu na górze i będzie 1636. Patrzę w dół. Widzę Harvard. Tak, tak, to mi się udało. Co, jeśli to, co szukam nie ma w trie, choć. Co zrobić, jeśli szukam Princeton, która została założona w 1746 roku. I tak 1746 będzie mój klucz poruszać się po trie. Cóż, zaczynają się od korzenia. I pierwsze miejsce chcę by idzie ścieżką 1. Czy mogę to zrobić? Tak, mogę. 

Mogę iść ścieżką stamtąd 7? Tak, mogę. Że istnieje też. Ale mogę iść ścieżką stąd 4? To jak zadać pytanie, może I przejść się, że mały kwadrat że mam podświetlone na żółto? Tam nic nie ma. Dobrze. 

Nie ma mowy, naprzód ścieżką 4. Jeśli Marcin był w tym trie, że 4 zostałby dopuszczony do nas już. A więc w tym momencie dotarliśmy w ślepy zaułek. Nie możemy iść dalej. I tak można powiedzieć, ostatecznie, nie. Marcin nie ma w tym trie. 

Więc co to wszystko znaczy? Dobrze. Jest dużo się tu dzieje. Nie ma wskazówek, w każdym miejscu. I, jak widać tylko z wykresu, jest wiele węzłów, które są rodzajem latają. Zauważmy jednak, za każdym razem chcieliśmy sprawdzić, czy coś jest nie w trie, mieliśmy tylko do 4 ruchy. 

Za każdym razem chcieliśmy wstawić coś w trie, mamy do 4 ruchów, ewentualnie mallocing pewne rzeczy po drodze. Ale jak widzieliśmy, gdy włożona Dartmouth w trie, Czasami pewne ścieżki może już być wyczyszczone dla nas. I tak, jak nasza trie robi się coraz większy i większe, musimy zrobić mniej pracy za każdym razem, aby wstawić nowe rzeczy już, bo mamy zbudowany dużo pośredniego gałęzie po drodze. Jeśli tylko kiedykolwiek spojrzeć na 4 rzeczy, 4 jest po prostu stałą. Naprawdę są rodzajem zbliża stała wstawiania czas Czas i stały wyszukiwania. Wadą oczywiście jest, że tego trie, jak można prawdopodobnie powiedzieć, jest ogromna. Każdy z tych węzłów zajmuje dużo miejsca. 

Ale to jest kompromis. Jeśli chcemy naprawdę szybkie wstawiania, bardzo szybkie usunięcie, i bardzo szybkie wyszukiwanie, musimy mają wiele danych latają. Musimy odłożyć dużo miejsca i pamięć dla tej struktury danych istnieć. 

I tak to jest kompromis. Ale wygląda na to, może ją znaleźli. Możemy odkryli, że Święty Graal struktur danych z szybkim wprowadzeniem, usuwanie i wyszukiwanie. A może będzie to odpowiednie struktury danych do korzystania z jakichkolwiek informacji próbujemy sklepie. Jestem Doug Lloyd, to CS50.