[Powered by Google Translate] Kā Jūs pārstāvēt visus savus ģimenes locekļus ar datoru?
Mēs varētu vienkārši izmanto sarakstu,
bet tur skaidrs hierarhija šeit.
>> Pieņemsim, ka mēs esam sākuši ar savu vecvecmāmiņa, Alice.
Viņai ir 2 dēli, Bob
un jūsu vectēvs, Čārlijs.
Čārlijs ir 3 bērni,
jūsu tēvocis, Deivs, jūsu tante, Ieva, un tavs tēvs, Fred.
Jums ir Freda vienīgais bērns.
>> Kāpēc būtu organizēt savu ģimenes locekļiem šādā veidā
labāk nekā vienkārši saraksts pārstāvniecības?
Viens iemesls ir tas, ka šis hierarhiska struktūra,
sauc par "koku," satur vairāk informācijas nekā vienkāršu sarakstu.
Mēs zinām radnieciskas attiecības starp visiem
vienkārši pārbaudot koku.
Arī tas var paātrināt
meklēt-up laiks vareni, ja koku dati tiek sakārtoti.
>> Mēs nevaram izmantot, ka šeit, bet mēs redzēsim piemēru tas drīz.
Katrs cilvēks ir pārstāvēta ar mezglu uz koku.
Mezgli var būt bērnu mezgliem
kā arī mātes mezglā.
Tie ir tehniski termini,
pat izmantojot koku, lai lietas, bez ģimenēm.
Alises mezgls ir 2 bērni un nav vecāku,
bet Charlie mezgls ir 3 bērni un 1 no vecākiem.
>> Lapu mezgls ir viens, ka nav bērnu
uz ārējās malas no koka.
Augšējais mezgla koka, saknes mezglu,
nav vecāks.
>> Binārs koks ir īpaša veida koku,
kurā katrs mezgls ir, augstākais, 2 bērni.
Šeit ir no mezgla bināro koku C. struct
Katram mezglam ir daži ar to saistītie dati
un 2 norādes uz citiem mezgliem.
>> Mūsu ģimenes koku,
saistītās dati bija katra cilvēka vārdu.
Šeit tas ir int, lai gan tas varētu būt kaut kas.
Kā izrādās,
binārs koks nebūtu labu pārstāvību par ģimeni,
jo cilvēki bieži ir vairāk nekā 2 bērnus.
>> Binārs meklēšanas koks
ir īpašs, piesprieda binārās koku
kas ļauj mums paskatīties uz vērtībām ātri.
Jums var būt ievērojuši
ka katrs mezgls zem saknes koku
ir arī citas koku saknes, ko sauc "apakškoka."
Lūk, no koka sakne ir 6,
un tā bērns, 2, ir sakne apakškoka.
>> Jo bināro meklēšanas koku
visi mezglu vērtības ir labi apakškoka
ir lielāka nekā mezglu vērtības. Šeit: 6.
Nu, vērtībām mezgla kreisā apakškoka
ir mazāk nekā mezglu vērtības.
Ja mums ir nepieciešams, lai apstrādātu dublikātus,
mēs varam mainīt nu no tiem ar vaļēju nevienlīdzību,
nozīmē identiskas vērtības var krist nu pa kreisi vai pa labi,
kamēr mēs esam konsekventi par to visā.
Šis koks ir binārs meklēšanas koks
jo no tā izriet, šos noteikumus.
>> Tas ir, kā tas izskatītos, ja mēs vērsāmies visus mezglus uz C structs.
Ievērojiet, ka, ja bērns ir pazudis,
rādītājs ir nulle.
Kā mēs pārbaudām, vai 7 ir kokā?
Mēs sākam pie saknes.
Septiņi ir lielāks par 6, tāpēc, ja tas ir no koka, tai jābūt tiesībām.
Tad tas ir mazāk nekā 8, tāpēc jāatstāj.
Lūk, mēs esam atraduši 7.
Tagad, mēs pārbaudīsim uz 5.
Pieci ir mazāks par 6, tāpēc tai jābūt pa kreisi.
Pieci ir lielāks par 2,
tāpēc tai jābūt labi,
un tas ir arī lielāka par 4, tāpēc tai jābūt labi atkal.
Tomēr nav bērnu šeit.
Rādītājs ir nulle.
Tas nozīmē, ka 5 nav mūsu koku.
>> Mēs varam meklēt bināro koku ar šādu kodu:
Katrā mezglā, mēs pārbaudām, vai mums ir atrasts
vērtība, mēs meklējam.
Ja mēs nevaram atrast to, mēs noteikt, ja tas būtu
pa kreisi vai pa labi un pārbaudiet apakškoka.
Šī cilpa turpinās pa koku
kamēr nav bērnu mezglu vai nu pa kreisi vai pa labi.
>> Atcerieties, ka 5 bija ne kokā.
Kā mēs ievietot to?
Šis process izskatās līdzīgs meklēt.
Mēs atkārtot pa koku sākot no 6,
kreisi līdz 2,
Tiesības uz 4,
un tiesības vēlreiz, 4 bet nav bērnu uz šo pusi.
Tas būs jauns amats par 5,
un tas sāks bez bērniem.
>> Cik ātri ir operācijas bināro meklēšanas koku?
Atcerieties, ka Bigohnotation cenšas nodrošināt augšējo robežu.
Sliktākajā gadījumā,
Mūsu koks varētu būt vienkārši saistīts saraksts
kas nozīmē, ka ievietošanu, dzēšanu, un meklēt
varētu prasīt laiku proporcionāls skaits mezglu kokā.
Tas ir O (n).
>> Piemēram, šādu derīgs bināro meklēšanas koku.
Taču, ja mēs cenšamies atrast 9,
mums ir traversa katru mezglu.
Tas nav labāka nekā saistīts saraksts.
Ideāli, ja mēs vēlamies katru mezglu
Mūsu binārā meklēšanas koks ir 2 bērni.
Tādā veidā, ievietošanas, dzēšanu un meklēt
varētu veikt, bet sliktākajā, O (log n) laiks.
No pirms koks varētu būt sabalansēts,
kā šis.
Tagad, skatoties uz augšu nekādas vērtības ņem, augstākais, 3 soļi.
Šis koks ir līdzsvarots,
nozīmē, ka ir ir minimāla dziļums
salīdzinot ar mezglu skaita.
>> Meklē vērtību līdzsvarotas bināro meklēšanas koku
ir līdzīgs bināro meklēšanu uz šķiroto masīvs.
Patiesībā, ja mums nav nepieciešams, lai ievietotu vai dzēstu objektus,
viņi uzvedas tieši tāpat.
Tomēr koks struktūra ir labāka
par apstrādes iespraudumi un svītrojumiem
>> Mans vārds ir Bannus van der Kloot.
Tas ir CS50.