[Powered by Google Translate] Hvordan vil du repræsentere alle dine familiemedlemmer i en computer?
Vi kunne blot bruge en liste,
men der er et klart hierarki her.
>> Lad os sige, at vi er begyndt med din oldemor, Alice.
Hun har 2 sønner, Bob
og din bedstefar, Charlie.
Charlie har 3 børn,
Deres onkel, Dave, din tante, Eva, og din far, Fred.
Du er Fred eneste barn.
>> Hvorfor skulle organisere dine familiemedlemmer på denne måde
være bedre end den simple liste repræsentation?
En grund er, at denne hierarkisk struktur,
kaldes en 'træ', indeholder mere information end en simpel liste.
Vi kender slægtskab mellem alle
blot ved at undersøge træet.
Det kan også fremskynde
look-up tid gevaldigt, hvis træet data er sorteret.
>> Vi kan ikke drage fordel af det her, men vi vil se et eksempel på dette snart.
Hver person er repræsenteret ved et knudepunkt i træet.
Nodes kan have barn noder
samt en forælder node.
Disse er de tekniske udtryk,
selv ved brug af træer for ting udover familier.
Alices knudepunkt har 2 børn og ingen forældre,
mens Charlie knudepunkt har 3 børn og 1 forælder.
>> Et blad node er en, der ikke har nogen børn
på den udvendige kant af træet.
Den øverste node i træet, roden node,
har ingen forælder.
>> Et binært træ er en specifik type af træ,
hvor hver knude har, højst 2 børn.
Her er struct af et knudepunkt i et binært træ i C.
Hvert knudepunkt har nogle data i forbindelse med det
og 2 henvisninger til andre knudepunkter.
>> I vores stamtræ,
de tilhørende data var hver persons navn.
Her er det en int, selvom det kunne være hvad som helst.
Da det viser sig,
et binært træ vil ikke være en god repræsentation for en familie,
da folk ofte har mere end 2 børn.
>> En binær søgning tree
er en særlig, ordnet type binært træ
der giver os mulighed for at se på værdierne hurtigt.
Du har måske lagt mærke til
at hver node under roden af ​​et træ
er roden af ​​et andet træ, en såkaldt »undertræ. '
Her roden af ​​træet er 6,
og dens barn, 2, er roden til et undertræ.
>> I en binær søgning træ
alle værdier af en knude er ret undertræ
er større end knudepunktets værdi. Her: 6.
Nå, værdierne i et knudepunkt venstre undertræ
er mindre end knudepunktets værdi.
Hvis vi er nødt til at håndtere dublerede værdier,
vi kan ændre enten af ​​dem til en løs ulighed,
betyder identiske værdier kan falde enten på venstre eller højre,
så længe vi er konsekvente over det hele.
Dette træ er et binært søgetræ
fordi det følger disse regler.
>> Dette er, hvordan det ville se ud, hvis vi vendte alle de noder til C struct.
Bemærk, at hvis et barn mangler,
markøren er nul.
Hvordan tjekker vi for at se, hvis 7 er i træet?
Vi starter ved roden.
Syv er større end 6, så hvis det er i træet, skal det være til højre.
Derefter er det mindre end 8, og det må være op.
Her har vi fundet 7.
Nu vil vi kontrollere for 5.
Fem er mindre end 6, så det må være til venstre.
Fem er større end 2,
så det må være rigtigt,
og det er også større end 4, så det må være rigtigt igen.
Der er imidlertid ingen børn her.
Markøren er null.
Dette betyder, at 5 ikke er i vores træ.
>> Vi kan søge det binære træ med følgende kode:
Ved hver node, tjekker vi for at se, om vi har fundet
den værdi, vi er på udkig efter.
Hvis vi ikke finder det, vi afgøre, om det skal være
på venstre eller højre, og kontroller, at undertræ.
Denne løkke vil fortsætte ned i træet
indtil der ikke er barneknudepunkt på enten venstre eller højre.
>> Husk, at 5 ikke var i træet.
Hvordan kan vi indsætter det?
Processen ligner søge.
Vi gentage ned i træet startende fra 6,
overlades til 2,
ret til 4,
og til højre igen, men 4 har intet barn på denne side.
Dette vil være den nye position for 5,
og det vil begynde med ingen børn.
>> Hvor hurtigt er operationer på et binært søgetræ?
Husk, at Bigohnotation søger at tilvejebringe en øvre grænse.
I værste fald,
vores træ kunne simpelthen være en sammenkædet liste
hvilket betyder, at indsættelse, sletning og søgning
kunne tage tid er proportional med antallet af knuder i træet.
Dette er O (n).
>> For eksempel er følgende en gyldig binær søgning træ.
Men hvis vi forsøger at finde 9,
Vi er nødt til at krydse hvert knudepunkt.
Det er ikke bedre end en linket liste.
Ideelt set ville vi ønsker hver node
af vores binære søgetræ at have 2 børn.
Denne måde, insertion, deletion og søgning
ville tage i værste fald O (log n) tid.
Træet fra før kunne være mere afbalanceret,
som denne.
Nu ser op nogen værdi tager, højst 3 trin.
Dette træ er afbalanceret,
forstand, at den har en minimal dybde
i forhold til antallet af knudepunkter.
>> Leder du efter en værdi i en balanceret binært søgetræ
ligner binær søgning på en ordnet array.
Faktisk, hvis vi ikke behøver at indsætte eller slette elementer
de opfører sig nøjagtig samme måde.
Men en træstruktur er bedre
for håndtering indsætninger og sletninger
>> Mit navn er Bannus Van der Kloot.
Det er CS50.