[MŪZIKA ATSKAŅOTĀSSKAN MŪZIKA]
DUGSDAGS LOIDS: Tāpēc mēs esam kļuvušinokļuvuši arvien tuvāk datu
struktūru svētajam grālam, ko mēs varam ievietot, dzēst un meklēt
nemainīgā laikā.
Pareizi.
Tas ir sava veida mērķis.
Mēs vēlamies, lai mēs varētu paveikt lietas ļoti, ļoti ātri.
Vai mēs to esam atraduši šeit, kad runājam par
mēģinājumiemdigitālajiem kokiem?
Nu, paskatīsimies.
Tāpēc mēs esam redzējušiapskatījuši vairākas dažādas datu struktūras,
kas apstrādā tā saukto atslēgu-vērtību pāru kartēšanu, kartējot kādu
datu daļu ar kādu citu datu daļu, lai mēs zinātu, kur struktūrā
atrast informāciju.
Tātad, piemēram, masīvam atslēga ir elementa indekss vai masīva
atrašanās vieta 0 vai masīvs 1 un tā tālāk.
Un vērtība ir dati, kas pastāv šajā vietā.
Tātad, kas tiek saglabāts masīvā 0?
Kas tiek saglabāts masīvā 1, salīdzinot ar tikai 0 un 1, kas būtu
atslēgas.
Ar hash tabulujaucējtabulu tā ir tāda pati ideja.
Izmantojot hash tabulujaucējtabulu, mums ir šī jaucējfunkcija, kas
ģenerē jaucējkodus.
Tātad galvenaisatslēga ir datu jaucējkods.
Un vērtība, jo īpaši mēs runājām par ķēdes pievienošanu video par
hash tabulāmjaucējtabulām, ir saistītais datu saraksts, kas
sajaucsajaucas ar šo jaucējkodu.
Pareizi.
Bet kā ar citu pieeju šai metodei?
Kā ir ar metodi, kurā atslēga tiek garantēta unikālatiek garantēta
unikāla atslēga, atšķirībā no jaucēj tabulasjaucējtabulas, kur mēs
varētu nonākt pie diviem datu vienumiem ar vienu un to pašu
jaucējkodu.
Un tad mums tas ir jārisina, veicot zondēšanuizpēti vai, vēlams,
ķēdivirknēšanu, lai atrisinātu šo problēmu.
Tāpēc tagad mēs varam garantēt, ka mūsu atslēga būs unikāla.
Un kā būtu, ja mūsu vērtība būtu tikpat vienkārša kā patiesība un
nepatiesībapatiesi un nepatiesi, kas mums norāda, vai šī informācija
struktūrā pastāv vai nēne?
Būla vērtība varētu būt tikpat vienkārša kā mazlietbits.
Reāli tas, iespējams, ir par baitu, visticamāk, nekā mazlietdroši
vien ir baits, kas ir ticamāks par bitu.
Bet tas ir daudz mazāk nekā, piemēram, 50 rakstzīmju virknes
saglabāšana.
Tādējādi mēģinājumidigitālie koki, līdzīgi kā jaucējtabulas, kas
apvieno masīvus un saistītos sarakstus, mēģina apvienot masīvus,
struktūras un norādes kopā, lai saglabātu datus interesantā veidā,
kas ievērojami atšķiras no visa, ko esam redzējuši līdz šim.
Tagad mēs izmantojam datus kā ceļvedi, lai pārvietotos šajā datu
struktūrā.
Un, ja mēs varam sekot ceļvedim, ja mēs varam sekot datiem no sākuma
līdz beigām, mēs uzzināsim, vai šie dati pastāv
izmēģinājumādigitālajā kokā.
Un, ja mēs vispār nevaram sekot kartei no nozīmes līdz galam, dati
nevar pastāvēt.
Atkal, atslēgas šeit ir garantētas unikālas.
Un tāpēc atšķirībā no hash tabulasjaucējtabulas mums šeit nekad nebūs
jāsaskaras ar sadursmēm.
Un nevienam divām datu daļām nav tieši tāda paša ceļveža, ja vien šie
dati nav identiski.
Ja ievietojam JāniJohn, tad meklējam JāniJohn.
Tie ir divi identiski datidatu fragmenti, pareizi, mēs skatāmiesko
mēs apskatām.
Bet pretējā gadījumā jebkurām divām datu daļām tiek garantēta
unikālagarantēts unikāls ceļvedis, izmantojot šo datu struktūru.
Un mēs pēc mirkļa apskatīsim šo vizuālo attēlu.
Mēs to darīsim, mēģinot izveidot jaunu datu struktūru, kartējot tālāk
norādītos atslēgu vērtību pārus.
Šajā gadījumā mēs neizmantosim kaut ko tik vienkāršu kā Būla vērtību.
Mēs faktiski uzglabāsim virkni.
Un šī virkne būs universitātes nosaukums.
Un galvenaisatslēga būs gads, kad šī universitāte tika dibināta.
Visi universitāšu gadi būs četri cipari.
Un tāpēc mēs izmantosim šos četrus ciparus, lai pārvietotos pa šo
datu struktūru.
Un mēs atkal redzēsim, kā mēs to paveiksim tikai pēc sekundes.
Ceļa beigās mēs redzēsim universitātes nosaukumu, kas atbilst šai
atslēgai, šie četri ciparišiem četriem cipariem.
IzmēģinājumaDigitālā koka pamatideja ir tāda, ka mums ir centrālais
maršruts.
Tāpēc domādomājiet par to kā par koku.
Un tas pēc pareizrakstības un koncepcijas ir līdzīgs kokam.
Parasti, kad mēs domājam par kokiem reālajā pasaulē, tiem ir sakne,
kas atrodas zemē, un tie aug uz augšu, un tiem ir zari un lapas.
Un būtībā triedigitālā koka ideja ir tieši tāda pati, izņemot to, ka
sakne ir noenkurota kaut kur debesīs.
Un lapas ir apakšā.
Tātad tas ir līdzīgi kā paņemt koku un vienkārši apgriezt to otrādi.
Bet joprojām ir filiāleszari.
Un tie būtu mūsu ceļi, tie būs mūsu savienojumi no saknēm līdz lapām.
Šajā gadījumā tie ceļi, tie atzari ir apzīmēti ar cipariem, kas mums
norāda, uz kuru pusi jāiet no vietas, kur atrodamies.
Ja mēs redzam 0, mēs ejam lejup pa šo zaru, ja mēs redzam 1, mēs ejam
uz leju pa šo zaru, un tā un tā tālāk.
Nu, ko tas nozīmē?
Tas nozīmē, ka katrā krustojuma punktā un katrā mezglā vidū un katrā
atzarojumā ir 10 iespējamās vietas, kur mēs varam doties.
Tātad no katras vietas ir 10 norādes.
Un šeit mēģinājumidigitālie koki var nedaudz iebiedēt kādu, kam
iepriekš nav bijusi liela pieredze datorzinātnēs.
Bet mēģinājumidigitālie koki ir patiešām lieliski.
Un, ja jums ir iespēja ar tiem strādāt un vēlaties ar tiem
iedziļināties un eksperimentēt ar tiem, tās patiešām ir diezgan
interesantas datu struktūras, ar kurām strādāt.
Ja mēs vēlamies ievietot elementu triedigitālajā kokā, viss, kas mums
jādara, ir izveidot pareizo ceļu no saknes līdz lapai.
Lūk, kā varētu izskatīties katrs solis ceļā.
Mēs definēsim jaunu datu struktūru jaunam mezglam, ko sauc par
triedigitālo koku.
Un šīs datu struktūras iekšpusē ir divas daļas.
Mēs saglabāsim universitātes nosaukumu.
Un mēs saglabāsim norādes uz citiem tāda paša veida mezgliem.
Tātad, tas atkal ir tāds jēdziens par,ka visur, kur atrodamies, ir 10
iespējamās vietāsvietas, kur varam doties.
Ja mēs redzam 0, mēs ejam lejup pa šo zaru.
Ja mēs redzam 1, pa šo zaru un tā tālāk, un tā tālāk, un tā tālāk.
Ja sakām 9, mēs ejam lejā pa šo zaru.
Tātad katrā krustojuma punktā mēs varam doties 10 iespējamās vietāsuz
10 iespējamām vietām.
Tātad katrā mezglā ir jāsatur 10 norādes uz citiem mezgliem, uz 10
citiem mezgliem.
Un dati, ko mēs glabājam, ir tikai universitātes nosaukums.
Tāpēc izveidosim mēģinājumudigitālo koku.
Ievietosim pāris vienumus mūsu izmēģinājumādigitālajā kokā.
Tātad pašā augšā šis ir mūsu saknes mezgls.
Tas, iespējams, būs kaut kas tāds, par ko jūs paziņosit visā
pasaulēglobāli.
Un jūs globāli vienmēr uzturēsitsaglabāsiet rādītāju uz šo mezglu
visā pasaulē.
Jūs sacīsit, sakne ir vienāda, un jūs iegūsit malloc sevi izmēģināt
mezglupiešķirsiet atmiņu digitālā koka mezglā vai piesaistīsiet jaunu
mezglu.
Un jūs nekad vairs nepieskarsities saknei.
Katru reizi, kad vēlaties sākt navigāciju, jūs iestatāt citu
rādītāju, kas ir vienāds ar rootsakni, piemēram, trav, kas ir
piemērs, ko izmantoju daudzos savos videoklipos šeit par
skursteņiemstekiem un rindām, saišu saistītiem sarakstiem un tā
tālāk.
Jūs iestatāt citu rādītāju ar nosaukumu trav pārvietošanaigrafa
apstaigāšanai - traversal.
Un jūs izmantojat trav, lai pārvietotos pa datu struktūru.
Tātad, redzēsimpaskatīsimies, kā tas varētu izskatīties.
Tātad, kā šobrīd izskatās mezgls?
Tāpat kā norādīts mūsu datu struktūras deklarācijā, mums ir virkne,
kas šajā gadījumā ir tukša.
Šeit nekā nav.
Un 10 rādītāju masīvs.
Un šobrīd šajā mēģinājumādigitālajā kokā mums ir tikai 1 mezgls.
Nekā cita tajā nav.
Tātad visi 10 no šiem rādītājiemrādītāji norāda uz nulli.
To norāda sarkanais.
Ieliksim virkni Harvard.
Ievietosim šajā digitālajā kokā Hārvardas Universitāti šajā
izmēģinājumā, kas tika dibināta 1636. gadā.
Mēs vēlamies izmantot atslēgu 1636, lai pateiktu mums, kur mēs
glabāsim Hārvardu digitālajā kokā.
Tagad, kā mēs to varētu izdarīt?
Tas varētu izskatīties apmēram šādi.
Mēs sākam no saknes.
Un mums ir šīs 10 vietas, kur varam doties.
Sakne ir tāda pati kā jebkurš cits triedigitālā koka mezgls.
No šejienes varam doties uz 10 vietām.
Kur mēs, iespējams, vēlamies doties, ja atslēga ir 1636?
Ir tiešām divas iespējas.
Pareizi.
Mēs varam izveidot atslēgu no labās puses uz kreiso un sākt ar 6.
Vai arī mēs varam izveidot atslēgu no kreisās puses uz labo un sākt
ar 1.
Iespējams, ka cilvēkam ir daudz intuitīvāk saprast, ka mēs vienkārši
ejam no kreisās uz labo pusi.
Un tāpēc, ja es vēlos iekļaut Hārvardu šajā mēģinājumādigitālajā
kokā, es, iespējams, vēlos sākt, sākot ar sakni, aplūkojot manas 10
iespējas un sakot, ka vēlos iet pa 1. ceļu.
Labi.
Pašlaik 1 ceļš ir nulle.
Tātad, ja es vēlos turpināt šo ceļu, lai ievietotu šo elementu
izmēģinājumādigitālajā kokā, man ir jāatrod jauns mezgls, jāiegūst
1 punkts, un tad man ir labies varu sākt.
Tātad es būtībā esmu vietā, kur es stāvu pie koka vai digitālā koka
saknes vai zariem un ir 10 zari.
Bet katram zaram priekšā ir vārti.
Pareizi.
Jo nekā cita tur nav.
Nav drošas pārejas.
Tas nozīmē, ka nevienā no šīm nozarēmšiem zariem nav nekā.
Ja es gribu sākt kaut ko būvētveidot, es gribu noņemt vārtus.
Es vēlos noņemt vārtus numuraskaitļa 1 priekšā.
Un es gribu iet pa to.
Un es vēlos uzceltizveidot citu vietu, kur man doties.
Un to es šeit esmu darījis.
Tātad 1 vairs nenorāda uz nulli.
Es teicu, ka tagad šeit ir droši doties.
Es uzbūvējuizveidoju vēl vienu mezglu.
Un, kad es nonāku pie šī mezgla, man ir jāpieņem cits lēmums.
Kurp es no šejienes došos?
Nu, es jau esmu samazinājies pargājis pa 1.
Tāpēc tagad es droši vien vēlos nokāptiet pa 6.
Pareizi.
Atkal, man ir 10 vietas, kuras varu izvēlēties.
Tātad tagad ejam uz leju ar 6. numurupa skaitli 6.
Tāpēc es atbrīvoju vārtus 6. numuraskaitļa 6 priekšā.
Un es eju tur lejāpa to.
Un es izveidoju vēl vienu mezglu.
Un esmu sasniedzis citu krustpunktu.
Atkal, man ir 10 izvēles iespējas, kur es varu doties.
Esmu pārcēlies no 1 uz 6.
Tāpēc tagad es droši vien vēlos doties uz 3.
3, es nekur nevaru iet.
Tāpēc man ir jāatbrīvo ceļš un jāveido sev jauna telpa.
Un tad no 3, kur es gribu doties?
Es gribu nolaistiesdoties pa 6.
Un atkal man bija jāatbrīvo ceļš, kā to izdarītlai to izdarītu.
Tāpēc tagad esmu izmantojis savu atslēgu, lai ievietotu
izveidesizveidotu mezglus un sāktu veidot šo mēģinājumudigitālo koku.
Es sāku no saknes.
Esmu samazinājies pardevies pa 1636.
Un tagad es esmu apakšā, tajā mezglā.
Un jūs, iespējams, varēsit to redzēt savā ekrānā.
Tas ir iezīmēts dzeltenā krāsā.
Tieši tur es šobrīd esmu.
Mana atslēga ir gatava.
Esmu izsmēlis visas savas atslēgas pozīcijas.
Tāpēc es nevaru iet tālāk.
Tāpēc šobrīd viss, kas man patiešām jādara, ir pateikt: Labi.
Tas ir līdzīgi kā skatīties uz zemi, ja jūs iztēlojaties sevi kā šāda
veida ceļu ar dažādiem savienojumiem.
Tāda veidakā skatīšanās uz leju un Hārvardas smidzināšanas
krāsošanaiekrāsošana ar aerosolu uz zemes.
Tāds ir šīs lietas nosaukums.
Uzziniet, kas atrodas šajā vietā.
Ja mēs sākam no saknes un ejam uz leju arpa 1 un tad 6, un tad 3, un
tad 6, kur mēs atrodamies?
Ja mēs skatāmies uz leju un redzam Hārvardu, tad mēs zinām, ka
Hārvarda tika dibināta 1636. gadā, pamatojoties uz veidu, kā mēs
ieviešam šo datu struktūru.
Tātad, cerams, tas bija vienkārši.
Mēs veiksim vēl divus ievietojumus.
Un cerams, ka tas palīdzēs redzēt, ka tas tiek darīts vēl divas
reizes.
Tagad ievietosim citu universitāti.
Ievietosim Jēlu - Yale - šajā mēģinājumādigitālajā kokā.
Jēla tika dibināta 1701. gadā.
Tātad, kā vienmēr, mēs sāksim no saknes.
Un mēs uzstādījām šķērsošanasgrafa apstaigāšanas rādītāju.
Mēs to izmantosim, lai pārvietotos cauri.
Pirmā lieta, ko mēs vēlamies darīt, ir iet pa 1 ceļu.
Tas ir mūsu atslēgas pirmais cipars.
Tomēr, par laimi, šoreiz mums nekas nav jādara.
1. ceļš jau ir atbrīvots.
Es to notīrīju iepriekš, kad ievietoju Hārvardu 1636. gadā.
Tāpēc es varu droši pārvietoties uz lejupa 1 un vienkārši doties uz
turieni.
Ja var pārvietoties uz leju pa 1.
Tomēr tagad es gribu doties uz 7.
Es atbrīvoju ceļu pulkstenpie 6.
Es zinu, ka varu droši turpināt 6 ceļu.
Bet man jāturpina pa 7 ceļu.
Tātad, kas man jādara?
Nu, tāpat kā iepriekš, man vienkārši jāattīra vārti, jānokļūstjāiziet
no ceļa un jāuzbūvējāizveido jauns mezgls no 7 ceļa.
Gluži kā šis.
Tāpēc tagad esmu pārcēlisvirzījies pa 1 un pēc tam 7.
Un tagad ievērojiet, es esmu šajā jaunajā apakšnozarēapakšzarā.
Pareizi.
Viss pārējais, sākot no 16, man vienalganerūp.
Es 16 neko nedaru.
Es daru 17 lietas.
Tāpēc tagad no pulksten 17 man šeit ir jāveido jaunas takas.
Nākamais cipars mana atslēgamanā atslēgā ir 0.
Skaidrs, ka es nekur nevaru tikt.
Es tikko izveidoju šo mezglu.
Tāpēc es zinu, ka no šejienes nav ceļu uz priekšu.
Tāpēc man pašam tas ir jāizgatavojāizveido.
Tāpēc es piesaistu jaunu mezglu un tur ir 0 punkts.
Un tad vēl vienu reizi es piesaistu jaunu mezglu un tur ir viens
punkts.
Es atkal esmu izsmēlis savu atslēgu, 1701.
Tāpēc es skatos uz leju un izsmidzinu ar krāsu Yale.
Tas ir šī mezgla nosaukums.
Un tāpēc tagad, ja man kādreiz vajadzēs redzēt, vai Jēla ir šajā
mēģinājumādigitālajā kokā, es sāku no saknes, nokāpjueju pa 1701 un
skatos uz leju.
Un, ja es redzu, ka Jēla aerosolsar aerosolu ir krāsotsiekrāsota uz
zemes, tad es zinu, ka Jēla pastāv šajā mēģinājumādigitālajā kokā.
DarīsimIzdarīsim vēl vienu.
Ievietosim šajā digitālajā kokā Dartmutu - Dartmouth - šajā trie, kas
tika dibināta 1769. gadā.
Sāciet vēlreiz no saknes.
Mans atslēgas pirmais cipars ir 1.
Es varu droši virzīties pa šo ceļu.
Tas jau pastāv.
Nākamais manas atslēgas cipars ir 7.
Es varu droši virzīties pa šo ceļu.
TāTas arī pastāv.
Mans nākamais ir 6.
No šejienes, kur es pašlaik esmu dzeltenā, tajā vidējā mezglā 6
pašlaik ir bloķēts.
Ja es gribu iet pa šo ceļu, man tas ir jābūvējāizveido pašam.
Tāpēc es izvēlēšos jaunu mezglu un tur iegūšu 6 punktus.
Un tad atkal es te svilinuieminu jaunas takas.
Tāpēc es piesaistu jaunu mezglu, lai no šī mezgla — ceļa numurs 9 —
un tad tagad, ja es ceļoju 1769, es skatos uz leju.
Pašlaik tur nekas nav krāsotsiekrāsots ar aerosolu.
Es varu rakstīt Dartmouth.
Un es esmu ievietojis Dartmouth triedigitālajā kokā.
Tā ir lietu ievietošana izmēģinājumādigitālajā kokā.
Tagad mēs vēlamies meklēt lietas.
Kā mēs meklējam lietas, kas atrodas izmēģinājumādigitālajā kokā?
Nu, tā ir gandrīz tāda pati ideja.
Tagad mēs vienkārši izmantojam atslēgas ciparus, lai redzētu, vai mēs
varam virzīties no saknes uz vietu, kur vēlamies, lai mēģinātu
nokļūtdoties digitālajā kokā.
Ja kādā brīdī nonākam strupceļā, mēs zinām, ka šis elements nevar
pastāvēt, pretējā gadījumā šis ceļš jau būtu notīrīts.
Ja tiekam līdz galam, mums atliek tikai skatīties uz leju un
noskaidrot, vai tas ir tas elements, ko mēs meklējam.
Ja tā, tad veiksme.
Ja tā nav, izgāziesneveiksme.
Tāpēc šajā mēģinājumā meklēsim Hārvardu.
Mēs sākam no saknes.
Un atkal mēs izveidosim šķērsošanasgrafa apstaigāšanas rādītāju, kas
veiks mūsu kustības mūsu vietā.
No saknes mēs zinām, ka pirmā vieta, kur mums jāiet, ir 1, vai mēs
varam to izdarīt?
Jā, mēs varam.
JaTā droši pastāv.
Mēs varam doties tur.
Tagad nākamā vieta, kur mums jāiet, ir 6.
Vai 6 ceļš pastāv no šejienes?
Jā, tā darair.
Mēs varam iet pa 6 taku.
Un mēs nonākam šeit.
Vai mēs varam no šejienes iet pa 3 ceļu?
Nu, kā izrādās, jā, arī tādatas pastāv.
Un vai mēs no šejienes varam nokļūt 6 takā?
Jā, mēs varam.
Mēs vēl neesam līdz galam atbildējuši uz šo jautājumu.
Joprojām ir vēl viens solis, un tagad mums ir jāpaskatās uz leju un
jānoskaidro, vai tas tiešām ir — ja mēs meklējam Hārvardu, vai tas ir
tas, ko mēs atrodam pēc atslēgas izsmelšanas?
Piemērā, ko mēs izmantojam šeit, gadi vienmēr ir četri cipari.
Bet jūs varētu izmantot piemēru, kur glabājat vārdu vārdnīcu.
Tā vietā, lai 10 rādītāji norādītu manu atrašanās vietu, jums varētu
būt 26 norādes.
ViensViena katram alfabēta burtam.
Un ir daži vārdi, piemēram, sikspārnisbat, kas ir, piemēram,
partijasbatch apakškopa.
Un pat tad, ja nonākat līdz atslēgas galam un skatāties uz leju,
iespējams, neredzēsit to, ko meklējat.
Tāpēc jums vienmēr ir jāšķērso viss ceļš un tad, ja esat veiksmīgi
spējis šķērsot visu ceļu, skatieties uz leju un veiciet vienu pēdējo
apstiprinājumu.
Vai tas ir tas, ko es meklēju?
Nu, es skatos uz leju pēc tam, kad sākšusāku no augšas un dodos uz
1636.
Es skatos uz leju.
Es redzu Hārvardu.
Tātad, jā, man izdevās.
Ko darīt, ja tas, ko es meklēju, tomēr nav iekļauts digitālajā kokā.?
Ko darīt, ja es meklējuJa nu es meklētu Prinstonu - Princeton -, kas
tika dibināta 1746. gadā.
Un tā 1746 kļūst par manu atslēgu, lai pārvietotos pa
mēģinājumudigitālo koku.
Nu, es sāku no saknes.
Un pirmā vieta, kur es vēlos doties, iet pa 1 ceļu.
Vai es varu to izdarīt?
Jā, es varu.
Vai no turienes es varu iet pa 7 taku?
Jā, es varu.
TasTā arī pastāv.
Bet vai es varu no šejienes iet pa 4 ceļu?
Tas ir tāpat kā uzdot jautājumu, vai es varu doties lejup pa mazo
kvadrātu, ko esmu iezīmējis dzeltenā krāsā?
Tur nekā nav.
Pareizi.
Nav ceļa uz priekšu pa 4 ceļu.
Ja Prinstona būtu šajā mēģinājumādigitālajā kokā, šiešis 4 mums jau
būtu dzēstinotīrīts.
Un tāpēc šajā brīdī mēs esam nonākuši strupceļā.
Mēs nevaram iet tālāk.
Un tāpēc mēs varam teikt, galīgi, nē.
Prinstona šajā mēģinājumādigitālajā kokā nepastāv.
Tātad, ko tas viss nozīmē?
Pareizi.
Šeit daudz kas notiek.
Visur ir norādes.
Un, kā jūs varat redzēt tikai no diagrammas, ir daudz mezglu, kas it
kā lido apkārt.
Taču ievērojiet, ka katru reizi, kad vēlējāmies pārbaudīt, vai kaut
kas ir triedigitālajā kokā, mums bija jāveic tikai 4 kustības.
Ikreiz, kad vēlējāmies kaut ko ievietot mēģinājumādigitālajā kokā,
mums ir jāveic 4 gājieni, iespējams, pa ceļam iznīcinot dažas
lietaspiešķirot atmiņu dažām lietām vai izveidojot dažas lietas..
Bet, kā mēs redzējām, ievietojot Dartmutu triejādigitālajā kokā,
dažkārt daļa ceļa mums jau var būt atbrīvota.
Tā kā mūsu mēģinājumsdigitālais koks kļūst arvien lielāks, mums katru
reizi ir jādara mazāk darba, lai ievietotu jaunas lietas, jo mēs jau
esam izveidojuši daudz starpzaru.
Ja mums kādreiz ir jāskatās tikai uz 4 lietām, 4 ir tikai konstante.
Mēs patiešām tuvojastuvojamies pastāvīgai laika ievietošanai un
pastāvīgai laika meklēšanai.
Protams, kompromiss ir tāds, ka šis mēģinājumsdigitālais koks, kā jūs
droši vien varat pateikt, ir milzīgs.
Katrs no šiem mezgliem aizņem daudz vietas.
Bet tas ir kompromiss.
Ja mēs vēlamies patiešām ātru ievietošanu, ļoti ātru dzēšanu un
patiešām ātru meklēšanu, mums ir jāpārvietojasvajadzīgi daudz datu.
Mums ir jāatvēl daudz vietas un atmiņas, lai šī datu struktūra
pastāvētu.
Un tas ir kompromiss.
Bet šķiet, ka mēs to varētu atrastbūt atraduši.
Mēs, iespējams, atradām šo datu struktūru svēto grālu ar ātru
ievietošanu, dzēšanu un uzmeklēšanu.
Un varbūt šī būs piemērota datu struktūra, ko izmantot jebkurai
informācijai, ko mēs cenšamies saglabāt.
Es esmu Dags Loids, šis ir cs50.