[Powered by Google Translate] Hvernig myndir þú tákna alla fjölskyldu þína í tölvu? Við gætum einfaldlega nota lista, en það er ljóst stigveldi hér. 

Við skulum segja að við erum farin með langamma þín, Alice. Hún er með 2 syni, Bob og afi þinn, Charlie. Charlie á 3 börn, frændi þinn, Dave, frænka þín, Eva, og faðir þinn, Fred. Þú ert bara barn Fred. 

Hvers vegna vildi að skipuleggja fjölskyldu á þennan hátt vera betri en einföldum lista framsetning? Ein ástæðan er að þetta valdakerfi, kallað "tré, inniheldur fleiri upplýsingar en einföldum lista. Við þekkjum familial tengsl milli allra bara með því að skoða tré. Einnig getur það hraðað líta upp tími ógurlega, ef tré gögn er flokkað. 

Við getum ekki tekið sér það hér, en við munum sjá dæmi um þetta fljótlega. Hver maður er táknuð með hnút á trénu. Hnútar geta hafa barnið hnúður ásamt foreldri hnút. Þetta eru tæknileg hugtök, jafnvel þegar tré fyrir hluti auk fjölskyldna. Tengipunktur Alice hefur 2 börn og enga foreldra, meðan hnút Charlie hefur 3 börn og 1 foreldri. 

A blaða hnút er eitt sem er ekki börn að utan brún tré. Hæstur hnút í tré, rót hnút, hefur ekkert foreldri. 

A tvöfaldur tré er ákveðin tegund af tré, þar sem hver hnútur hefur í mesta lagi 2 börn. Hér er struct í hnút tvíundartrés í C. Sérhver hnútur hefur nokkur gögn í tengslum við það og 2 ábendingum til annarra hnúta. 

Í tré fjölskyldu okkar, í tengslum við þessa upplýsingar var nafn hvers manns. Hér er það int, þótt það gæti verið nokkuð. Eins og það kemur í ljós, tvöfaldur tré myndi ekki vera góð framsetning fyrir fjölskyldu, þar sem fólk hefur oft fleiri en 2 börn. 

Leit tvöfaldur tré er sérstök, pantaði tegund af tré tvöfaldur sem gerir okkur kleift að líta á gildi fljótlega. Þú gætir hafa tekið eftir að sérhver hnútur undir rót á tré er rót annars tré, sem kallast "subtree." Hér er rót af trénu er 6, og barnið hennar, 2, er rót a subtree. 

Í tvöfaldur leita tré öll gildin í hnút er rétt subtree eru meiri en verðmæti hnút á. Hér: 6. Jæja, gildin í vinstri subtree hnúturinn er er minna en verðmæti hnút á. Ef við þurfum að takast á afrit gildi, við getum breytt annaðhvort þeirra að missa misrétti, þýðir sömu gildi geta fallið annaðhvort vinstri eða hægri, svo lengi sem við erum í samræmi um það allan tímann. Þetta tré er tvöfaldur leita tré vegna þess að það fylgir þessum reglum. 

Þetta er hvernig það myndi líta út ef við snúið alla hnúta í C structs. Takið eftir að ef barnið vantar, bendillinn er null. Hvernig athuga við að sjá hvort 7 er í trénu? Við byrjum á rót. Seven er meiri en 6, þannig að ef það er í trénu, þarf það að vera til hægri. Þá er það minna en 8, svo það verður að vera vinstri. Hér höfum við fundið 7. Nú munum við athuga 5. Fimm er minna en 6, svo það verður að vera til vinstri. Fimm er meiri en 2, svo það verður að vera rétt, og það er líka meiri en 4, þannig að það verður að vera rétt aftur. Hins vegar er ekkert barn hér. Bendillinn er null. Þetta þýðir að 5 er ekki í tré okkar. 

Við getum leitað í tvöfaldur tré með eftirfarandi kóða: Á hverjum hnút, athuga við að sjá hvort við höfum fundið gildi sem við erum að leita að. Ef við finn það ekki, ákveðum við hvort það ætti að vera á vinstri eða hægri og athuga hvort subtree. Þessi lykkja heldur áfram niður tréð þangað til það er ekkert barn hnút annaðhvort vinstri eða hægri. 

Mundu að 5 var ekki í tré. Hvernig setja við það? Ferlið líkist leita. Við iterate niður tréð byrjar 6, vinstri til 2, rétt til 4, og aftur til hægri, en 4 er ekki barn á þessu megin. Þetta verður ný staða fyrir 5, og það byrjar með engin börn. 

Hversu hratt er rekstur á tvöfaldur leita tré? Mundu að Bigohnotation leitast við að veita að efri. Í versta tilfelli, tré okkar gæti einfaldlega verið tengda listanum þýðir að innsetningu, eyðingu, og leita gæti tekið tíma hlutfalli við fjölda hnúta í trénu. Þetta er O (n). 

Til dæmis er eftirfarandi er gild tvöfaldur leita tré. Hins vegar, ef við reynum að finna 9, við verðum að fara yfir hverjum hnút. Það er ekkert betra en tengda listanum. Helst myndum við vilja hverjum hnút af tvöfaldur leita tré okkar að hafa 2 börn. This vegur, innsetningu, eyðingu og leita myndi taka, í versta falli, O (log n) tíma. The tré undan gæti verið jafnvægi, eins og þetta. Nú, að horfa upp hvaða gildi tekur í mesta lagi 3 skref. Þetta tré er í jafnvægi, merking sem hefur lágmarks dýpt miðað við fjölda hnúta. 

Útlit fyrir gildi í jafnvægi tvöfaldur leita tré er svipað og tvöfaldur leit á raðað fylki. Í staðreynd, ef við þurfum ekki að setja inn eða eyða hlutum, þeir haga sér nákvæmlega á sama hátt. En tré uppbygging er betri til ísetningar meðhöndlun og úrfellingum 

Ég heiti Bannus Van der Kloot. Þetta er CS50.