[Muusika mängib] DOUG LLOYD: Nii et me oleme sammkäik lähemale ja lähemale, et Püha Graal andmeid struktuurid, mis meil on võimalik lisada arvesse, kustutada ja otsida konstantse ajaga. Õigus. See on omamoodi eesmärk. Me tahame, et oleks võimalik teha asju väga kiiresti. 

Kas me leidsime siin kui me räägime üritab? Noh, võtame pilk. Nii et me oleme näinud mitmeid erinevad andmestruktuurid et hakkama kaardistamine nn võtme-väärtuse paarid, kaardistada mõned tükk andmed mõne muu tükk andmed nii et me teame, kust leida teabe struktuuri. 

Nii massiiv, näiteks Oluline on elemendi indeks või massiivi asukoha 0 või massiivi 1 ja nii edasi. Ja väärtus on andmed mis on olemas selles kohas. Mis siis salvestatakse massiivi 0? Mis on talletatud rida 1 versus lihtsalt 0 ja 1, mis oleks võtmed. 

Mis hash tabelis on omamoodi sama mõte. Mis hash tabelit, meil on see hash funktsiooni, mis genereerib räsikoodid. Nii et võti on räsikoodiga andmeid. Ja väärtus, eriti me rääkisime aheldamine video kohta hash tabeleid, on see, et seotud andmete loetelu et hashes sellele räsikood. Õigus. Aga teine ​​lähenemine Selle meetodi kuigi? Aga meetod, kus võti on garanteeritud olema unikaalne, Erinevalt hash tabelit, kus saime lõpuks kaks tükki andmeid võttes samal räsikood. Ja siis me peame tegelema et kas sondeerimine või enama soovitavalt aheldamine määrata see probleem. 

Nüüd saame garanteerida et meie peamine on ainulaadne. Ja mis siis, kui meie väärtus oli lihtsalt midagi nii lihtne kui õige ja vale, mis ütleb meile, kas või mitte, et osa teabest olemas struktuur? Tõeväärtus võib olla sama lihtne kui natuke. Reaalselt tähendab see tõenäoliselt byte tõenäolisem kui natuke. Aga see on palju väiksem kui ladustamiseks võibolla 50-märgijada, näiteks. 

Nii katseid sarnaseid räsitabeli, mis ühendavad massiivid ja seotud nimekirja, üritab ühendada massiivid, struktuuride ja suunanäitajaks koos andmete säilitamine huvitav, kuidas see on päris erinev midagi, mida me oleme näinud siiani. Nüüd me kasutame andmeid tegevuskava liikuda andmete struktuuri. Ja kui me suudame järgida tegevuskava, kui me suudame järgige andmeid Algusest lõpuni, siis me tea, kas need andmed olemas Prefiksipuu. 

Ja kui me ei saa järgida kaart alates tähendab lõppu üldse, andmed ei ole olemas. Jällegi, võtmed siin on garanteeritud olema unikaalne. Ja nii erinevalt hash tabelit, me ei saa iial peavad tegelema kokkupõrkeid siin. Ja no kaks tükki andmeid on täpselt sama tegevuskava kui see on andmed identsed. 

Kui me lisada John, siis otsime John. See on kaks ühesugust tükki andmed, õigus, otsime läbi. Aga muidu kõik kaks tükki andmed on tagatud on unikaalne tegevuskavad selle kaudu andmete struktuuri. Ja me ei kavatse võtta pilk visuaalne seda vaid hetkeks. 

Me teeme seda, üritades luua uusi andmeid struktuuri, kaardistada järgmiste põhiväärtus paari. Sel juhul me ei kavatse kasutada midagi nii lihtne kui Boole'i. Me tegelikult salvestab string. Ja see string läheb olla nime ülikoolis. 

Ja võti saab olema aasta kui see ülikool asutati. Kõik aastat ülikoolide hakkavad olema neljakohaline. Ja nii me kasutame neid neli numbrit liikuda andmete struktuuri. Ja me näeme jälle, kuidas me teha vaid teise. 

Lõpus tee, me näeme nime ülikooli, mis vastab sellele võtmele, need neli numbrit. Põhiidee Prefiksipuu on meil keskne liinil. Nii mõelda nagu puu. Ja see on sarnane kirjapilt ja mõiste puu. Üldiselt, kui me mõtleme puud reaalses maailmas, nad on juur, mis on ka maa ja nad kasvavad üles ja neil on filiaalid ja neil on lehed. Ja põhimõtteliselt idee Prefiksipuu on täpselt sama, välja arvatud root on ankurdatud kuskil taevas. Ja lehed on allosas. 

Nii et see on selline nagu võttes puu ja lihtsalt flipping tagurpidi. Kuid on veel oksad. Ja need oleks meie teed, need on meie ühendused juurest lehed. Sel juhul on need teed, need oksad on märgistatud numbrit, mis meile mis suunas minna sealt, kus me oleme. 

Kui me näeme 0, me läheme selle filiaal, kui näeme 1, me läheme selle filiaal, ja nii ja nii edasi. Noh, mida see tähendab? Noh, see tähendab, et igal ristmikul punkti ja iga sõlme keskel, igasse filiaali, seal on 10 võimalik kohti, et me ei lähe. Nii on 10 suunanäitajaks igast asukohast. 

Ja see on koht, kus üritab saavad natuke hirmutada keegi kes ei ole palju kogemus infotehnoloogia enne. Vaid püüab tõesti päris vinge. Ja kui teil on võimalus töötada koos nendega ja sa oled valmis kaevama sisse ja katsetada neid, nad tõesti päris huvitav andmestruktuuride töötada. Kui me tahame, et sisestada element arvesse Prefiksipuu, kõik me peame tegema on ehitada õige tee juurest lehed. Siin on, mida igal sammul Muide tunduda. Me läheme määratleda uued andmed struktuuri uue sõlme nimetatakse Prefiksipuu. 

Ja sees, et andmed struktuuri on kaks tükki. Me läheme salvestada nimi ülikooli. Ja me ei kavatse hoida massiivi osuti teiste sõlmede sama tüüpi. Niisiis, jälle see, et sorteerida on mõiste kõikjal oleme, meil on 10 võimalik kohti saame minna. Kui me näeme 0, me läheme selle filiaal. Kui me näeme, 1, selle filiaali, ja nii edasi ja nii edasi ja nii edasi. Kui me ütleme, 9, me läheme selle filiaal. Nii igal ristmikul punkti, saame minna 10 võimalikud kohad. Nii et iga sõlm peab sisaldama 10 suunanäitajaks teiste sõlmede, 10 muude sõlmede. 

Ja andmeid me hoidmiseks on just ülikooli nime. Nii saab ehitada Prefiksipuu. Lisame paar objekte meie Prefiksipuu. Nii tipus, see on meie Juursõlme. See on ilmselt saab olema midagi sa lähed globaalselt kuulutada. Ja sa lähed globaalselt säilitada kursor selle sõlme alati. 

Sa ütled, root võrdne, ja sa oled läheb malloc ise Prefiksipuu sõlme. Ja sa ei saa kunagi puudutada root uuesti. Iga kord, kui soovite alustada navigeerimist läbi, te valite mõne pointer võrdne juur, nagu matk, mis on näiteks mina kasutada väga paljudes oma videos siin korstnad ja järjekorrad ja link nimekirju ja nii edasi. 

Sa valid teise pointer nimetatakse trav eest läbipääsusüsteemid. Ja te kasutate trav navigeerida kaudu andmestruktuur. Vaatame, kuidas see võiks välja näha. Nii kohe, mida ei sõlm välja näeb? Noh, nagu meie andmeid struktuuri deklaratsiooni märgitud, meil on string, mis Sel juhul on tühjad. Siin ei ole midagi. 

Ja massiivi 10 suunanäitajaks. Ja just nüüd, me ainult on 1 sõlm selles Prefiksipuu. Seal on midagi muud seal. Nii et kõik 10 neid viiteid punkti tühjaks. Seda punast näitab. 

Lisame string Harvard. Lisame Ülikooli Harvardi sellesse Prefiksipuu, mis asutati aastal 1636. Me tahame kasutada võtit, 1636, et meile öelda, kus me oleme läheb salvestada Harvardi Prefiksipuu. Nüüd, kuidas võiks seda teha? 

See näeks välja umbes selline. Alustame keskmes. Ja meil on neid 10 kohta saame minna. Juur on nagu iga muu sõlme Prefiksipuu. Seal on 10 kohta saame siit edasi minna. 

Kus me ilmselt tahad minna, kui võti on 1636? Seal on tõesti kaks võimalust. Õigus. Me võime ehitada võti paremalt vasakule ja alustada 6. Või me võiks ehitada võti vasakult paremale ja alustada 1. 

See on ilmselt rohkem intuitiivne kui inimene mõista me minge vasakult paremale. Ja nii kui ma tahan lisada Harvardi sellesse Prefiksipuu, Ma ilmselt tahavad alustada alustades keskmes, vaatasin 10 valikud minu ees, ja öelda Ma tahan minna 1 tee. OKEI. 

Nüüd, 1 rada on praegu null. Nii et kui ma tahan minna seda teed lisada seda asjaolu Prefiksipuu, Pean malloc Uue sõlme on 1 juhtida seal, ja siis ma olen hea minna. 

Nii et ma põhimõtteliselt olen juures kus ma seisan keskmes puu või Prefiksipuu ja seal on 10 filiaali. Aga iga haru on värava ees. Õigus. Sest pole midagi seal. No ohutu läbipääsu. See tähendab, et seal on midagi maha kõik need oksad. Kui ma tahan alustada hoone midagi, ma tahan, et eemaldada värava. Ma tahan, et eemaldada värava ees number 1. Ja ma tahan jalutada mööda seda. Ja ma tahan, et ehitada teine ​​koht mul minna. 

Ja see, mida ma olen teinud siin. Nii 1 enam punkte tühjaks. Ma olen öelnud, et see on ohutu minna siin nüüd. Ma ehitasin teise sõlme. Ja kui ma saan, et sõlm, ma on teise otsuse tegema. Kuhu ma lähen minema siit? 

Noh, ma olen juba läinud alla 1. Nüüd ma ilmselt tahad minna 6. Õigus. Jällegi, mul on 10 kohtadesse võin valida. Nii saab nüüd minna number 6. Nii et ma selge värava ees number 6. Ja ma kõnnin seal. Ja ma ehitada teise sõlme. Ja ma olen jõudnud teise ristmikul punkti. 

Jällegi, mul on 10 valikuid jaoks, kus ma ei saa minna. Olen liikunud 1-6. Nüüd ma ilmselt tahad minna 3. 3, seal kuskil ma ei lähe. Nii et mul on selge, kuidas ja ehitada endale uue ruumi. Ja siis 3, kus ma tahan minna? Ma tahan minna 6. 

Ja jällegi, ma pidin selge viis seda teha. Nüüd olen kasutanud minu võti sisestada luua sõlmed ja hakata ehitama seda Prefiksipuu. Olen hakanud keskmes. Olen langenud 1636. Ja nüüd ma olen allosas seal, et sõlme. Ja sa võiksid vaata seda ekraanil. 

See on kollase värviga. See, kui ma praegu olen. Minu peamine tehakse. Olen ära igas asendis minu võti. Nii et ma ei saa minna kaugemale. Nii sel hetkel, ma tõesti vaja teha, on öelda, OK. See on nagu vaadates alla maapinnale, kui sa ette kujutama ise nagu selline tee erinevate ühendustega. Omamoodi vaatab alla ja omamoodi Värvimine Harvard kohapeal. See nimi see. Tea, et just see on see koht. Kui hakkame keskmes ja me läheme 1 ja seejärel 6 ja seejärel 3 ja seejärel 6, kus me oleme? Noh, kui me vaatame alla ja me näeme Harvard, siis me teame, et oli Harvardi asutatud 1636 põhineb viis me rakendatakse andmete struktuuri. Nii et oli loodetavasti arusaadav. Me teeme veel kaks sisestamisel. Ja loodetavasti saad aidata vaata seda teha kaks korda rohkem. 

Nüüd saab sisestada teises ülikoolis. Lisame Yale sellesse Prefiksipuu. Yale asutati 1701.. Nii hakkame juures root, nagu me alati teeme. Ja me seame läbipääsusüsteemid pointer. Me ei kavatse kasutada, et liikuda. Esimene asi, mida me tahame tegema, on minna 1 tee. See on esimene number meie võti. Õnneks aga meil ei ole pea tegema muud tööd sel ajal. 1 tee on juba läbinud. Ma kustutatakse see varem, kui ma oli sisestamist Harvard at 1.636. Nii Võin julgelt liikuda alla 1 ja lihtsalt minna. Kui ei liiguta alla 1. 

Nüüd aga ma tahan minna 7. Ma avab tee 6. Ma tean, et ma ei saa ohutult edasi mööda 6 rada. Aga ma pean toimima 7 teele. Mida ma pean tegema? Noh, nagu enne, ma lihtsalt vaja selge värav, saada välja viis, ja ehitada uus sõlme 7 teele. Just niimoodi. 

Nüüd ma olen liikunud 1 ja seejärel 7. Ja nüüd märgata, ma olen omamoodi on selle uue subbranch. Õigus. Kõik muu on 16 kohta, ma ei hooli. Ma ei tee 16 midagi. Ma teen 17 kraami. 

Nüüd alates 17, ma pean omamoodi lauk uusi siin. Järgmine kohaline minu võti on 0. Ma ei saa ilmselgelt kuhugi. Ma ehitasin selle sõlme. Nii et ma tean, seal ei ole teed edasi siit. Nii et ma pean tegema ühe ise. 

Nii et ma malloc uus sõlm ja on 0 punkti olemas. Ja siis veel üks kord, ma malloc uus sõlm ja üks koht olemas. Jällegi, ma olen ära minu võti, 1701. Nii ma vaatan alla ja ma spreid Yale. See on nimi selle sõlme. 

Ja nii nüüd kui ma kunagi vaja näha, kui Yale on selles Prefiksipuu, ma hakkan keskmes, Ma lähen alla 1701, ja vaata alla. Ja kui ma näen, Yale spray värvitud maapinnale, siis Ma tean, Yale olemas selles Prefiksipuu. Teeme veel ühe. Lisame Dartmouth sellesse Prefiksipuu, mis asutati 1769. 

Alusta keskmes uuesti. Minu esimene number minu võti on 1. Võin julgelt liikuda mööda seda teed. See on juba olemas. Järgmine kohaline minu võti on 7. Võin julgelt liikuda mööda seda teed. See on olemas ka. 

Minu kõrval on 6. Siit kust ma praegu olen kollane seal, et keset sõlme, 6 on praegu lukustatud maha. Kui ma tahan minna seda teed, Mul on ehitada ise. Nii et ma malloc uus sõlm ja on 6 punkti olemas. Ja siis jälle, ma olen lõõskav uus suusarajad siin. 

Nii et ma malloc uus sõlm, et alates et node-- liini number 9-- ja siis nüüd kui ma reisida 1769 ja ma vaatan alla. Pole midagi praegu spray värvitud olemas. Oskan kirjutada Dartmouth. Ja ma olen järele Dartmouth sisse Prefiksipuu. 

Nii et sisestades asju sisse Prefiksipuu. Nüüd tahame otsida asju. Kuidas otsida asju Prefiksipuu? Noh, see on päris palju sama mõte. Nüüd me lihtsalt kasutada numbrit võti et näha, kas me saame liikuda juurest et kuhu me tahame minna Prefiksipuu. 

Kui me tabanud tupikusse üheski punktis, siis me teame, et see element ei eksisteeri või siis, et tee oleks on juba kõrvaldatud. Kui me teeme seda kõik viis Lõpuks kõik me peame tegema on odavnema ja vaata, kas see on element ootame. Kui on, edu. Kui see ei ole, ei suuda. 

Nii saab otsida Harvardi selles Prefiksipuu. Alustame keskmes. Ja jällegi, me ei kavatse luua läbipääsusüsteemid pointer teha oma käigud meile. Juurest me teame, et esiteks me peame minema on 1, me saame seda teha? Jah me saame. Kui turvaliselt olemas. Me ei lähe sinna. 

Nüüd järgmine koht peame minema on 6. Kas 6 rada olemas siit? Jah, nii see on. Me ei saa minna mööda 6 rada. Ja me lõpuks siin. 

Kas me saame minna 3 tee siin? Noh, kui selgub, jah, et on olemas ka. Ja me saame on 6 teed siit? Jah me saame. 

Me ei ole päris vastas küsimus veel. Seal on veel üks etapp, mis on nüüd vajame odavnema ja kas see on actually-- Kui me otsime Harvard, on see, et mida leiame pärast me ammendab võti? Näites me kasutame siin Aastate on alati neli numbrit. Aga siis võiks kasutada näiteks siis, kui olete ladustamiseks sõnastik sõnu. 

Ja nii asemel 10 suunanäitajaks minu asukohta, siis võib-olla 26. Üks iga täht. Ja seal on mõned sõnad, nagu nahkhiir, mis on alamhulk partii, näiteks. Ja nii ka siis, kui sa saad lõpuks võtme ja sa vaatad alla, sa ei pruugi näha, mida otsite. 

Nii et teil on alati läbida kogu tee ja seejärel kui sa olid edukalt suudab läbida kogu tee, odavnema ja teha üks lõpliku kinnituse. Kas see, mida ma otsin? Noh, ma vaatan alla pärast käivitamist tipus ja läheb 1636. Ma vaatan maha. Ma näen Harvard. Nii et jah, ma õnnestus. Mis siis, kui see, mida ma otsin ei asu Prefiksipuu, kuigi. Mis siis, kui ma otsin Princeton, mis asutati 1746. Ja nii 1746 muutub minu võti liikuda Prefiksipuu. Noh, ma hakkan keskmes. Ja esimene koht, kus ma tahan et läheb alla 1 rada. Kas ma saan seda teha? Jah, ma saan. 

Kas ma saan minna 7 tee seal? Jah, suudan. See kehtib ka. Aga ma saan minna 4 tee siin? See on nagu küsib küsimuse, saab Ma sõita alla, et vähe kandiline et ma olen kollase värviga? Pole midagi seal. Õigus. 

Ei ole nii edasi mööda 4 teed. Kui Princetoni oli selles Prefiksipuu, et 4 oleks läbinud meile juba. Ja et selles kohas oleme jõudnud tupikusse. Me ei saa minna kaugemale. Ja nii võib öelda, lõplikult ei. Princetoni ei ole selles Prefiksipuu. 

Mida see kõik tähendab? Õigus. Seal on palju siin toimub. Seal on suunanäitajaks kogu koht. Ja nagu näed lihtsalt skeemilt, seal on palju tippe, et on selline sõidavad ringi. Aga teate iga kord, kui me tahtsime kas midagi oli Prefiksipuu, meil oli ainult teha 4 liigutust. 

Iga kord, kui me tahtsime lisada midagi Prefiksipuu, peame 4 liigub, võib-olla mallocing mõned asjad mööda teed. Aga nagu me nägime, kui me sisestatud Dartmouth sisse Prefiksipuu, mõnikord mõned teed võiks juba kustutatud meile. Ja nii nagu meie Prefiksipuu muutub suuremaks ja suurem, on meil teha vähem tööd iga kord lisada uusi asju sest me oleme juba ehitatud palju vahepealse oksad mööda teed. Kui me ainult kunagi vaadata 4 asju, 4 on lihtsalt konstant. Me tõesti on selline läheneb pidev aja sisestamise ja pidev aja otsing. Miinuseks muidugi on see, et Selle Prefiksipuu, kui saad ilmselt öelda, on suur. Igaüks neist sõlmed võtab palju ruumi. 

Aga see on kompromiss. Kui me tahame tõesti kiire sisestamise tõesti kiire kustutamise, ja tõesti kiire otsing, peame on palju andmeid sõidavad ringi. Me peame kõrvale palju ruumi ja mälu andmete struktuur eksisteerida. 

Ja nii see on kompromiss. Aga tundub, et me oleks leidnud. Me võime on leidnud, et Püha Graal andmestruktuurid kiire sisestamine, kustutamise ja otsimise. Ja võib-olla see olla asjakohaste andmete struktuur kasutada mis tahes teavet me üritame poodi. Ma olen Doug Lloyd, see on CS50.