[Powered by Google Translate] Kaip jūs atstovauti visus savo šeimos narius į kompiuterį? Mes galime tiesiog naudoti sąrašą, bet čia yra aiški hierarchija. 

Tarkime, mes pradėjome su savo puikiai močiutė, Alice. Ji turi 2 sūnus, BOB ir tavo senelis, Čarlis. Čarlis turi 3 vaikus, tavo dėdė, Dave, jūsų teta, Ieva, ir tavo tėvas, Fredas. Esate Fredo vienintelis vaikas. 

Kodėl gi organizuoti savo šeimos narius tokiu būdu būti geriau nei paprastas sąrašas atstovavimo? Viena iš priežasčių yra tai, kad hierarchinė struktūra, vadinamas "medis", pateikiama daugiau informacijos nei paprastą sąrašą. Mes žinome, kad šeimos santykius tarp visiems tik nagrinėjant medį. Be to, ji gali pagreitinti peržiūroje laikas labai, jei medžių duomenys rūšiuojami. 

Mes negalime pasinaudoti, kad čia, bet mes pamatyti šio pavyzdžiu netrukus. Kiekvienas žmogus yra atstovaujamos ant medžio mazgas. Mazgai gali turėti vaikų mazgų taip pat patronuojančios mazgas. Tai yra techniniai terminai, net naudojant medžių dalykų, be šeimų. Alisos mazgas turi 2 vaikus ir neturi tėvų, o Čarlio mazgas turi 3 vaikus ir 1 iš tėvų. 

Lapų mazgas yra vienas, kad neturi vaikų išorinio krašto medžio. Viršutinis medžio mazgas, šakninis mazgas, neturi tėvų. 

Dvejetainis medis yra tam tikros rūšies medžio, , kurioje kiekvienas mazgas turi ne daugiau kaip 2 vaikus. Čia yra dvejetainis medis, C mazgas struct Kiekvienas mazgas turi tam tikrus duomenis, susijusius su juo ir 2 rodykles į kitus mazgus. 

Mūsų šeimos medį, susiję duomenys buvo kiekvieno žmogaus vardas. Čia jis yra int, nors ji gali būti bet kas. As it turns out, dvejetainis medis nebūtų geras atstovavimas šeimai, nes žmonės dažnai turi daugiau nei 2 vaikus. 

Dvejetainis paieškos medis yra išskirtinis, sutvarkyta dvejetainis medis tipas , kuri leidžia mums greitai pažvelgti į vertybes. Galbūt jūs pastebėjote, kad kiekvienas žemiau medžio šaknų mazgas yra kito medžio šaknis, vadinama "šaka". Čia iš medžio šaknis yra 6, ir jo vaikas, 2, šaka šaknis. 

Dvejetainis paieškos medis visi mazgas vertės teisė šaka yra didesnė nei mazgas vertės. Čia: 6. Na, mazgo kairėje šaka vertės yra mažiau nei mazgas vertės. Jei mums reikės tvarkyti pasikartojančius vertybes, mes galime pakeisti arba tų, kurios prarasti nelygybės, identiški dydžiai gali nukristi arba į kairę arba į dešinę, tol, kol mes nuosekliai visoje. Šis medis yra dvejetainis paieškos medis , nes jis šias taisykles. 

Tai, kaip jis atrodys, jei mes kreipėmės į visus mazgus C structs. Atkreipkite dėmesį, kad, jei vaikas nėra, rodyklė yra tuščias. Kaip mes patikrinti, norėdami pamatyti, jei 7 į medį? Mes pradedame ne šaknis. Septyni yra didesnis kaip 6, todėl, jei jis yra medžio, ji turi būti į dešinę. Tada, tai yra mažiau nei 8, todėl jis turi būti paliktas. Čia, mes nustatėme, 7. Dabar mes patikrinti 5. Penki yra mažiau nei 6, todėl ji turi būti į kairę. Penkių yra didesnis kaip 2, todėl ji turi būti teisinga, ir ji taip pat yra didesnės nei 4, todėl ji turi būti vėl dešinėn. Tačiau yra ne vaikas čia. Rodyklė yra tuščias. Tai reiškia, kad 5 yra ne mūsų medžio. 

Mes galime ieškoti dvejetainį medį su šį kodą: Kiekviename mazge, mes patikrinti, norėdami pamatyti, jei mes turime rasti vertė, mes ieškome. Jei mes negalime rasti tai, mes nustatyti, ar ji turėtų būti kairę arba į dešinę ir patikrinti, kad šaka. Šis ciklas bus toliau medį kol nėra vaikas mazgas arba į kairę arba į dešinę. 

Atminkite, kad 5 buvo ne į medį. Kaip mes jį įterpti? Procesas yra panašus ieškoti. Mes pakartoti medį nuo 6, kairės į 2, teisę į 4, ir vėl dešinėn, bet 4 turi vaikų neturi šioje pusėje. Tai bus nauja pozicija 5, ir jis pradės be vaikų. 

Kaip greitai yra dvejetainis paieškos medis operacijos? Atminkite, kad Bigohnotation siekia teikti viršutinė riba. Blogiausiu atveju, mūsų medis gali tiesiog būti susieta sąrašas tai reiškia, kad papildymui, ištrynimui ir ieškoti gali užtrukti, proporcingą medžio mazgų skaičių. Tai yra O (n). 

Pavyzdžiui, taip yra galiojantis dvejetainis paieškos medis. Tačiau, jei mes stengiamės rasti 9 turime išanalizuoti kiekvieną mazgą. Tai ne geriau nei susietą sąrašą. Idealiu atveju, mes norime, kad kiekvienas mazgas mūsų dvejetainis paieškos medis turi 2 vaikus. Tokiu būdu, įterpimas, ištrynimo ir paieškos imsis, blogiausiu atveju, O (log n) laiko. Nuo iki medis gali būti labiau subalansuota, kaip šis. Dabar, žiūrint kokią nors vertę užima ne daugiau kaip 3 žingsniai. Šis medis yra subalansuotas, tai reiškia, kad turi minimalų gylį , palyginti su mazgų skaičius. 

Domina subalansuotą dvejetainis paieškos medis vertės yra panaši į dvejetainį paieškos rūšiuotų masyvo. Iš tiesų, jei mes neturime reikia įterpti ar ištrinti elementus, jie elgiasi lygiai taip pat. Tačiau, medžio struktūra yra geriau tvarkymo įterpimus ir panaikinti 

Mano vardas yra Bannus Van der Kloot. Tai CS50.