[Powered by Google Translate] Kiel vi reprezentas ĉiujn viajn familianojn en komputilo?
Ni povus simple uzi listo,
sed estas klara hierarkio tie.
>> Diru ni komencante kun via praavino, Alice.
Ŝi havas 2 filojn, Bob
kaj via avo, Charlie.
Charlie havas 3 infanojn,
via onklo, Dave, via onklino, Eva, kaj via patro, Fred.
Vi estas Fred nur infano.
>> Kial organizi vian familianoj tiamaniere
esti pli bona ol la simpla listo reprezento?
Unu kialo estas ke tiu hierarkia strukturo,
nomata 'arbo,' enhavas pli da informoj ol simpla listo.
Ni konas la familiara interrilatoj inter ĉiuj
nur ekzameni la arbo.
Ankaŭ, ĝi povas akceli
rigardo-supren tempo terure, se arbo datumoj ordo.
>> Ni ne povas utiligi tiun ĉi tie, sed ni vidos ekzemplon de tiu baldaŭ.
Ĉiu persono estas reprezentita de nodo en la arbo.
Nodoj povas havi infano nodoj
tiel kiel patro nodo.
Tio estas la teknikaj terminoj,
eĉ uzinte arboj por aĵoj krom familii.
Alicia nodo havas 2 infanoj kaj ne gepatroj,
dum Charlie nodo havas 3 filojn kaj 1 patro.
>> Al folio nodo estas unu kiu ne havas ajnan infanoj
sur la ekstera rando de la arbo.
La plejsupra nodo de la arbo, la radiko nodo,
ne havas patro.
>> A duuma arbo estas specifa tipo de arbo,
en kiu ĉiu vertico havas, maksimume, 2 infanojn.
Jen la struct de nodo de duuma arbo en C.
Ĉiu vertico havas iujn datumojn asociitaj al ĝi
kaj 2 punteros al aliaj nodoj.
>> En nia familio arbo,
la asociita datumoj estis ĉiu persono nomo.
Tie estas int, kvankam povus esti io.
Ĉar ĝi rezultas,
duuma arbo ne estus bona reprezento por familio,
ekde homoj ofte havas pli ol 2 infanoj.
>> A duuma serĉarbo
estas speciala, ordigita tipo de duuma arbo
kiu nin permesas rigardi valoroj rapide.
Vi eble rimarkis
ke ĉiu nodo sub la radiko de arbo
estas la radiko de alia arbo, nomata 'subárbol.'
Ĉi tie, la radiko de la arbo estas 6,
kaj lia filo, 2, estas la radiko de subarbo.
>> En duuma serĉarbo
ĉiuj valoroj de nodo pravas subárbol
estas pli grandaj ol la nodo valoron. Ĉi tie: 6.
Nu, la valoroj en nodo la maldekstra subarbo
estas malpli ol la nodo valoron.
Se ni bezonas manipuli duplikatajn valoroj,
ni povas ŝanĝi aŭ de tiuj al malfiksas neegaleco,
signifas identa valoroj povas fali ĉu sur la maldekstra aŭ dekstra,
tiel longe kiel ni estas konsekvenca pri tio tra la tuto.
Ĉi tiu arbo estas duuma serĉarbo
ĉar ĝi sekvas ĉi tiujn regulojn.
>> Tiel estas kiel ĝi aspektus se ni turnis ĉiuj nodoj en C structs.
Rimarku ke se infano mankas,
la puntero estas nula.
Kiel ni kontrolu vidi se 7 estas en la arbo?
Ni komencu ĉe la radiko.
Sep estas pli granda ol 6, do se estas en la arbo, ĝi devas esti por la rajto.
Tiam, ĝi estas malpli ol 8, do ĝi devas esti forlasita.
Jen, ni trovis 7.
Nun, ni kontrolu por 5.
Kvin estas malpli ol 6, do ĝi devas esti al la maldekstra.
Kvin estas pli granda ol 2,
do ĝi devas esti ĝuste,
kaj ĝi estas ankaŭ pli granda ol 4, do ĝi devas esti ĝuste denove.
Tamen, ne estas infano tie.
La montrilo estas nula.
Tio signifas ke 5 ne estas en niaj arbo.
>> Ni povas serĉi la duuma arbo kun la sekva kodo:
Je ĉiu vertico, ni kontrolu vidi se ni trovis
la valoron ni serĉas.
Se ni ne trovos ĝin, ni determini se ĝi devus esti
sur la maldekstra aŭ dekstra kaj kontroli, ke subárbol.
Ĉi buklo daŭrigos laŭ la arbo
ĝis estas ne infano nodo sur ĉu la maldekstra aŭ dekstra.
>> Memoru ke 5 ne estis en la arbo.
Kiel ni enŝovu ĝin?
La procezo aspektas simila al serĉi.
Ni persisti malsupren la arbo ekde 6,
forlasis al 2,
rajton 4,
kaj dekstra denove, sed 4 havas ne infanon sur tiu flanko.
Ĉi tiu estos la nova pozicio por 5,
kaj komencos sen infanoj.
>> Kiel rapida estas la operacioj en duuma serĉo arbo?
Memoru ke Bigohnotation celas provizi supera baro.
En la plej malbona kazo,
nia arbo eblus simple lerta kunligita
signifante ke inserción, forigo, kaj serĉo
povus preni tempon proporcia al la nombro de nodoj en la arbo.
Tiu estas O (n).
>> Ekzemple, jeno estas valida duuma serĉarbo.
Tamen, se ni provos trovi 9,
ni devas trairi ĉiu nodo.
Ĝi estas pli bona ol ligitaj listo.
Ideale, ni volus ĉiu nodo
de nia duuma serĉarbo havi 2 idoj.
Tiamaniere, inserción, forigo kaj serĉo
prenus, en la plej malbona, O (logo n) tempo.
La arbo de antaŭ povus esti pli ekvilibrigita,
kiel ĉi tio.
Nun, supren rigardante neniun valoron portas, maksimume, 3 paŝoj.
Ĉi tiu arbo estas ekvilibra,
signifo kiu estas havas minimuman profundo
relativa al la nombro de nodoj.
>> Serĉante valoro en ekvilibran duuma serĉarbo
estas simila al duuma serĉo sur ordo tabelo.
Fakte, se ni ne bezonas enmeti aŭ forviŝi erojn,
ili kondutas ekzakte la sama maniero.
Tamen, arbo strukturo estas pli bona
por uzado inserciones kaj forigoj
>> Mia nomo estas Bannus Van der Kloot.
Ĉi tiu estas CS50.