[Powered by Google Translate] Kako bi zastopa vse svoje družinske člane v računalniku? Lahko bi enostavno uporabite seznam, vendar pa je jasna hierarhija tukaj. 

Recimo, da smo začeli s svojo prababica, Alice. Ima 2 sinova, Bob in tvoj dedek, Charlie. Charlie ima 3 otroke, tvoj stric, Dave, tvoja teta, Eve, in tvoj oče, Fred. Vi ste edini otrok Fred. 

Zakaj bi organiziranje vaših družinskih članov na ta način bolje kot preprosto zastopanje seznama? Eden od razlogov je, da je to hierarhična struktura, imenovano "drevo" vsebuje več informacij kot preprosti seznam. Vemo, sorodstvenih odnosov med vsemi samo s preučevanjem drevo. Prav tako lahko pospeši Navlake čas strašen, če je razvrščen podatke o drevesu. 

Ne moremo izkoristiti, da tukaj, pa bomo videli zgled za to kmalu. Vsaka oseba, ki se predstavlja vozlišče v drevesu. Vozlišča lahko otrok vozlišč kot tudi matično vozlišču. To so tehnične izraze, tudi z uporabo dreves za stvari, poleg družine. Vozlišče Alice ima 2 otroka in ne staršev, medtem ko je vozlišče Charliejeva ima 3 otroke in 1 starš. 

Listov vozlišča je tisti, ki nima otrok na zunanjem robu drevo. Je najvišje vozlišče v drevesu, vozlišče koren, nima staršev. 

Binarno drevo je posebna vrsta drevesa, v katerem vsako vozlišče ima največ 2 otroka. Tukaj je struct za vozlišče binarno drevo C. Vsako vozlišče ima nekatere podatke, povezane z njim in 2 kazalci na drugih vozlišč. 

V našem družinskem drevesu pridruženih podatki so bili vsi ime osebe. Tukaj je int, čeprav bi lahko bilo karkoli. Kot se je izkazalo, binarno drevo ne bi bila dobra predstavitev za družino, saj ljudje pogosto imajo več kot 2 otroka. 

Binarno iskalno drevo je posebna, urejena vrsta drevesa binarnem ki nam omogoča, da pogled na vrednote hitro. Morda ste opazili, da vsako vozlišče pod koren drevesa je koren drevesa drugega, imenovanega "poddrevo." Tu so korenine drevesa je 6, in njena otroka, 2, je koren poddrevesa. 

V dvojiškega drevesa vse vrednosti vozlišča je desno poddrevo večje od vrednosti vozlišča. Tukaj: 6. No, vrednosti v levo poddrevo vozlišča manj kot vrednosti vozlišča. Če moramo ravnati podvojene vrednosti, moremo spremeniti niti tistih, ki se ohlapno neenakosti, kar pomeni, enake vrednosti se lahko bodisi padel na levo ali desno, tako dolgo, kot smo dosledno o njem po vsej. To drevo je dvojiško iskalno drevo ker naj bi se ta pravila. 

To je, kako bi bilo videti, če smo se obrnili vsa vozlišča v konstrukti C. Obvestilo, da če otrok ni, kazalec je nična. Kako preverite, ali 7 je na drevesu? Začnemo pri korenu. Sedem je več kot 6, tako da če je na drevesu, mora biti na desni strani. Potem pa je manj kot 8, zato mora ostati. Tu smo ugotovili, 7. Sedaj bomo preverite, 5. Pet je manj kot 6, tako da mora biti na levi strani. Pet je večje od 2, zato mora biti v redu, prav tako pa je večje od 4, zato mora biti spet v redu. Vendar pa ni otrok tukaj. Kazalec je nična. To pomeni, da je 5 ni v našem drevesu. 

Mi lahko iščete binarno drevo z naslednjo kodo: Na vsakem vozlišču, preverimo, če smo našli vrednota, ki jo iščete. Če ne bomo našli, bomo ugotovili, če je treba na levo ali desno in preverite, ali poddrevo. Ta krog se bo nadaljeval z drevesa dokler ni otrok vozlišče bodisi na levo ali desno. 

Ne pozabite, da je 5 ni v drevesu. Kako ga vstavite? Postopek je podoben iskanje. Mi Ponovil navzdol drevesa od 6, levo 2, Pravica do 4, in še enkrat desno, ampak 4 nima otroka na tej strani. To bo nov položaj 5, in bo začela brez otrok. 

Kako hitro so operacije na dvojiškega drevesa? Ne pozabite, da Bigohnotation želi zagotoviti zgornja meja. V najslabšem primeru, naše drevo lahko preprosto povezani seznam kar pomeni, da vstavljanje, brisanje in iskanje lahko traja nekaj časa, sorazmeren s številom vozlišč v drevesu. To je O (n). 

Na primer, tole ni veljavno binarno iskalno drevo. Vendar, če bomo poskušali najti 9, imamo za prečkanje vsako vozlišče. Ni boljšega kot povezan seznam. Idealno bi bilo, bi si želeli vsako vozlišče naše drevo binarno iskalno da ima 2 otroka. Na ta način, vstavljanje, brisanje in iskanje bi se v najslabšem primeru O (log n) časa. Drevo od prej bi mogla biti bolj uravnotežen, kot je ta. Zdaj pa gledal kakšno vrednost ima v največ 3 koraki. To drevo je uravnotežen, kar pomeni, da je ima minimalno globino glede na število vozlišč. 

Iščete vrednost v binarno iskalno drevo uravnoteženo Podobno je pri binarnem iskanju na razvrščeni matrike. V bistvu, če nam ni treba, da vstavite ali izbrišete elemente, se obnašajo natanko na enak način. Vendar pa je drevesna struktura je bolje za ravnanje z vstavki in izbrisi 

Moje ime je Bannus Van der Kloot. To je CS50.