[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.