[Powered by Google Translate] Kako bi vam predstavlja sve svoje članove obitelji u računalu?
Mi jednostavno mogli koristiti popis,
ali postoji jasna hijerarhija ovdje.
>> Recimo počinjemo s prabaka, Alice.
Ona ima dva sina, Bob
i tvoj djed, Charlie.
Charlie ima 3 djece,
Vaš ujak, Dave, vaša tetka, Eva, i tvoj otac, Fred.
Vi ste Fredov jedino dijete.
>> Zašto bi organizira svoje članove obitelji na ovaj način
biti bolja od jednostavnog popisa reprezentacije?
Jedan od razloga je da je to hijerarhijska struktura,
naziva "stablo", sadrži više informacija nego jednostavan popis.
Znamo obiteljske odnose između svakoga
samo uvidom u stablo.
Također, to može ubrzati
izgled-up vrijeme strahovito, ako stablo podaci razvrstani.
>> Ne možemo iskoristiti da ovdje, ali vidjet ćemo primjer za to uskoro.
Svaka osoba predstavlja čvor na stablu.
Čvorovi mogu imati djecu čvorova
kao i roditelj čvor.
To su tehnički uvjeti,
Čak i ako koristite stabala za stvari osim obitelji.
Alice čvor ima dva djecu i nema roditelje,
dok je Charliejev čvor ima 3 djece i jedan roditelj.
>> Čvor nultog stupnja je onaj koji nema nikakve djecu
na vanjskom rubu stabla.
Najviši čvor stabla, korijen čvor,
nema roditelja.
>> Binarno stablo je specifična vrsta drveta,
u kojem je svaki čvor ima, u najboljem slučaju, 2 djece.
Ovdje je struct od čvora binarnog stabla u C.
Svaki čvor ima neke podatke povezane s njim
i dva upućuje na druge čvorove.
>> U našem obiteljskom stablu,
pridružene podataka je svaka osoba je ime.
Ovdje je int, iako bi to moglo biti ništa.
Kao što se ispostavilo,
stablo binarno neće biti dobra reprezentacija za obitelj,
jer ljudi često imaju više od dva djece.
>> Stablo binarno pretraživanje
je posebna, uređenu vrsta binarnog stabla
koji nam omogućuje da pogledamo vrijednosti brzo.
Možda ste primijetili
da je svaki čvor ispod korijena stabla
je korijen drugog stabla, zove 'podstablo.'
Evo, korijen stabla je 6,
i njegova dijete, 2, je korijen podstablo.
>> U binarnom stablu pretraživanja
sve vrijednosti čvor je pravo podstablo
su veći od čvora vrijednosti. Ovdje: 6.
Pa, vrijednosti u čvor je lijevo podstablo
manje od čvora vrijednosti.
Ako trebamo nositi dvostruke vrijednosti,
možemo promijeniti bilo koji od onih na slobodnom nejednakosti,
znači identične vrijednosti može pasti bilo na lijevo ili desno,
dok smo dosljedni o tome tijekom.
Ovo stablo je binarno pretraživanje stablo
jer slijedi ta pravila.
>> To je, kako bi to izgledalo da smo okrenuli sve čvorove u C tvorevina.
Primjetite da ako je dijete nestalo,
Pokazivač je null.
Kako smo provjerili da li je 7 u stablu?
Krećemo u korijenu.
Sedam je veći od 6, pa ako je to u stablo, to mora biti na desnoj strani.
Zatim, to je manje od 8, tako da mora biti lijevo.
Evo, našli smo sedam.
Sada ćemo provjeriti za pet.
Pet je manje od 6, pa to mora biti na lijevoj strani.
Pet je veći od 2,
tako da mora biti u pravu,
i to je također veći od četiri, tako da mora biti ponovno desno.
Međutim, ne postoji dijete ovdje.
Pokazivač je null.
To znači da 5 nije u našem stablu.
>> Možemo pretraživati ​​binarnog stabla sa sljedeći kod:
Na svakom čvoru, mi provjeriti da li smo našli
vrijednost tražimo.
Ako ga ne pronađete, mi se utvrdilo da li je to trebao biti
lijevo ili desno i provjerite da podstablo.
Ova petlja će se nastaviti niz stablo
dok ne postoji čvor dijete na bilo lijevo ili desno.
>> Sjetite se da je 5 nije bio u stablo.
Kako ćemo ga ubaciti?
Proces sličan pretraživanje.
Mi ponoviti dolje stablo počevši od 6,
lijevo do 2,
pravo na 4,
i opet desno, ali 4 nema dijete na ovoj strani.
To će biti novi položaj za 5,
i počet će bez djece.
>> Koliko brzo su operacije na binarnog stabla pretraživanja?
Zapamtite da Bigohnotation nastoji pružiti gornja granica.
U najgorem slučaju,
naša stablo jednostavno mogla biti povezana popis
što znači da umetanje, brisanje i pretraživanje
moglo potrajati proporcionalan broju čvorova u stablu.
Ovo je O (n).
>> Na primjer, sljedeće je važeća binarno stablo pretraživanja.
Međutim, ako ćemo pokušati pronaći 9,
moramo proći svaki čvor.
To nije ništa bolji od povezane liste.
U idealnom slučaju, mi bi htjeli svaki čvor
našeg stabla binarno pretraživanje imati dva djece.
Na taj način, umetanje, brisanje i pretraživanje
bi, u najgorem slučaju, O (log n) vremena.
Stablo od prije mogao biti uravnotežena,
ovako.
Sada, gledajući bilo koju vrijednost ima, najviše, tri koraka.
Ovo stablo je uravnotežen,
što znači da je ima minimalnu dubinu
u odnosu na broj čvorova.
>> U potrazi za vrijednosti u uravnoteženom binarnog stabla pretraživanja
je sličan binarnom pretraživanje na sortirati niz.
U stvari, ako mi ne treba umetnuti ili izbrisati stavke,
oni se ponašaju na isti način.
Međutim, struktura stabla je bolje
za rukovanje umetanja i brisanja
>> Moje ime je Bannus Van der Kloot.
Ovo je CS50.