[Powered by Google Translate] Kuidas te esindada kõiki oma pereliikmetele arvuti?
Me võiksime lihtsalt kasutada nimekirja,
kuid seal on selge hierarhia siin.
>> Oletame, et me hakkame oma vanavanaema, Alice.
Tal on 2 poega, Bob
ja oma vanaisa, Charlie.
Charlie on 3 last,
oma onu, Dave, oma tädi, Eve, ja oma isa, Fred.
Olete Fredi ainus laps.
>> Miks peaks korraldama oma pereliikmetele sel viisil
parem kui lihtne nimekiri esindus?
Üks põhjus on see, et hierarhiline struktuur,
nimega "puu" sisaldab rohkem infot kui lihtsalt loetelu.
Me teame põlvnemissuhete vahel kõigile
lihtsalt uurides puu.
Samuti võib kiirendada
look-up aega tohutult, kui puu andmeid sorteerida.
>> Me ei saa ära, et siin, kuid eks me näeme näide sellest varsti.
Iga inimene on esindatud sõlme puul.
Sõlmed võivad tütartippu
samuti vanem sõlme.
Need on tehnilised terminid,
isegi kui kasutate puud asju peale peredele.
Alice'i sõlm on 2 last ja vanemaid,
samas Charlie sõlm on 3 last ja 1 vanem.
>> Lehed on üks, mis ei ole ka lapsi
väljastpoolt serva puu.
Tähtsaim sõlm puu, juur sõlme,
puudub tema vanem.
>> Kahendpuu on teatud tüüpi puu,
kus iga tipp on kõige rohkem 2 last.
Siin on struct kohta sõlme kahendpuu in C.
Iga sõlm on mõned andmed sellega seotud
ja 2 viiteid teistele tippe.
>> Meie sugupuu,
seotud andmed oli iga isiku nimi.
Siin see on keskmine, kuigi see võiks olla midagi.
Nagu selgub,
kahendpuu ei oleks hea esitus perele,
kuna inimesed on sageli rohkem kui 2 last.
>> Kahendotsingupuu
on eriline, tellitud tüüpi kahendpuu
mis võimaldab meil vaadata väärtused kiiresti.
Olete ehk märganud
et iga sõlme allpool puu juurt
on root teise puu, mida nimetatakse "alampuu."
Siin just puu on 6,
ja oma lapse, 2, on just alampuu.
>> Aastal Kahendotsingupuu
kõik väärtused sõlm on parempoolne alampuu
on suurem kui sõlme väärtusest. Siin: 6.
Noh, väärtused sõlme vasaku alampuu
on väiksem kui sõlme väärtusest.
Kui me peame hakkama duplikaatväärtusi,
saame muuta kumbki neist on lahtine ebavõrdsus,
mis tähendab identsed väärtused võivad langeda kas vasakule või paremale,
nii kaua kui meil on kooskõlas selle peale kogu.
See puu on Kahendotsingupuu
sest see järgib neid eeskirju.
>> See on kuidas see näeks välja kui me pöördusime kõik sõlmed arvesse C structs.
Pange tähele, et kui laps on kadunud,
pointer on null.
Kuidas vaadata, kui 7 on puus?
Alustame keskmes.
Seitse on suurem kui 6, nii et kui see on puu, see peab olema õige.
Siis on vähem kui 8, seega tuleb jätta.
Siin me oleme leidnud 7.
Nüüd vaatan 5.
Viis on väiksem kui 6, seega tuleb vasakule.
Viis on suurem kui 2,
seepärast peab olema õigus,
ja see on ka suurem kui 4, seega tuleb uuesti paremale.
Samas ei ole lapse siin.
Pointer on null.
See tähendab, et 5 ei ole meie puu.
>> Me ei otsi kahendpuu koos järgmise koodi abil:
Igas tipus, me vaadata, kui oleme leidnud
väärtus otsime.
Kui me ei leia seda, me kindlaks teha, kas see peaks olema
vasakule või paremale ja kontrollige, et alampuu.
See silmus jätkab puu otsast alla
kuni ei ole laps sõlme kas vasakule või paremale.
>> Pea meeles, et 5 ei olnud puu.
Kuidas lisada see?
Protsess sarnaneb otsida.
Me itereerima puu otsast alla alates 6
Vasakult 2
õigus 4,
ja uuesti paremale, kuid 4 ei ole lapse siinpool.
See on uus positsioon 5,
ja siis hakkab kellel ei ole lapsi.
>> Kui kiiresti on operatsioonid Kahendotsingupuu?
Pea meeles, et Bigohnotation püütakse anda ülemise.
Halvimal juhul,
meie puu võiks lihtsalt seotud nimekirja
mis tähendab, et sisestamise, kustutamise ja otsing
võib võtta aega proportsionaalne arv tippe puu.
See on O (n).
>> Näiteks järgmised on kehtiv Kahendotsingupuu.
Siiski, kui me püüame leida 9,
meil läbida iga sõlme.
See ei ole parem kui seotud nimekirja.
Ideaalis tahaksime iga sõlme
meie Kahendotsingupuu on 2 last.
Nii, sisestamise, kustutamise ja otsing
võtaks, halvimal juhul O (log n) ajaga.
Puud enne võiks olla rohkem tasakaalustatud,
niimoodi.
Nüüd, vaadates üles mingit väärtust võtab kõige rohkem 3 astet.
See puu on tasakaalustatud,
mis tähendab, et tal on minimaalne sügavus
võrreldes sõlmede arvul.
>> Otsid väärtus tasakaalustatud Kahendotsingupuu
on sarnane binaarne otsing sorteeritud massiiv.
Tegelikult, kui me ei vaja lisada või eemaldada,
nad käituvad täpselt samamoodi.
Kuid puu struktuuri on parem
käitlemise lisamised ja kustutamised
>> Minu nimi on Bannus Van der kloot.
See on CS50.