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