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