[Powered by Google Translate] Kouman ou ta reprezante tout manm fanmi an ou a nan yon òdinatè? Nou te ka tou senpleman itilize yon lis, , men tou genyen yon yerachi klè isit la. 

Se pou nou di nou ap kòmanse ak grann gwo-ou a, Alice. Li te gen 2 Men pitit gason, Bob ak granpè ou a, Charlie. Charlie gen 3 timoun yo, tonton ou a, Dave, matant ou a, Èv, e papa ou, Fred. Ou yo, se sèlman pitit Fred a. 

Poukisa ta òganize manm fanmi ou nan fason sa a ka pi bon pase reprezantasyon nan lis ki senp? Youn nan rezon ki se ke estrikti sa a yerarchize, yo te rele yon 'pye bwa,' gen enfòmasyon pi plis pase yon lis ki senp. Nou konnen relasyon ki genyen ant familyal tout moun jis pa ekzamine pyebwa sa a. Epitou, li ka pi vit gade-up tan anpil, si done pyebwa se Klase. 

Nou pa kapab pran avantaj de ki isit la, men nou pral wè yon egzanp sou sa byento. Chak moun reprezante pa yon ne sou pyebwa sa a. Nœuds ka gen nœuds pitit kòm osi byen yon ne paran yo. Sa yo se kondisyon ki teknik, menm lè lè l sèvi avèk pye bwa pou bagay sa yo san konte fanmi yo. Ne Alice an gen 2 timoun yo ak pa gen okenn paran yo, pandan y ap ne Charlie a gen 3 timoun yo ak paran 1. 

Yon ne fèy se youn ki pa gen okenn timoun yo sou kwen deyò an nan pyebwa sa a. Ne nan topmost nan pyebwa a, ne nan rasin, pa gen okenn paran yo. 

Yon pye bwa binè se yon kalite espesifik nan pye bwa yo, kote chak ne gen, nan pi, 2 timoun yo. Isit la se struct a nan yon ne nan yon pyebwa binè nan C. Chak ne gen kèk done ki asosye ak li ak 2 endikasyon nœuds lòt. 

Nan pye bwa fanmi nou an, done ki asosye te non chak moun nan. Men li se yon int, menm si li te kapab anyen. Kòm li vire soti, yon pye bwa binè pa ta dwe yon reprezantasyon bon pou yon fanmi, depi moun souvan gen plis pase 2 timoun yo. 

Yon pye bwa rechèch binè se yon espesyal, ki kalite lòd nan pyebwa binè ki pèmèt nou fè yon gade nan valè byen vit. Ou ka remake gen ke chak ne pi ba a rasin nan yon pye bwa se rasin lan yon lòt pye bwa yo, yo te rele yon 'subtree. Isit la, rasin pyebwa a se 6, ak pitit li yo, 2, se rasin lan nan yon subtree. 

Nan yon pyebwa rechèch binè tout valè sa yo nan yon ne nan dwa subtree se pi gran pase valè ne la. Mwen: 6. Oke, valè yo nan subtree gòch yon ne a yo gen mwens pase valè ne la. Si nou bezwen okipe valè kopi, nou kapab chanje swa nan sa yo nan yon inegalite ki lach, sa vle di valè idantik ka tonbe swa sou bò gòch la oswa dwa, osi lontan ke nou se konsistan sou li nan tout. Pyebwa sa a se yon pye bwa rechèch binè paske li swiv règleman sa yo. 

Sa a se li montre kouman li ta gade si nou vire tout nœuds yo nan C strukt. Remake si gen yon timoun ki manke, konsèy la se nil. Ki jan nou tcheke yo wè si 7 se nan pye bwa a? Nou kòmanse nan rasin lan. Sèt pi gran pase 6, kidonk si li nan nan pye bwa a, li dwe a dwat la. Lè sa a,, li se pi piti pase 8, ki fè li dwe kite. Isit la, nou te jwenn 7. Koulye a, nou pral tcheke pou 5. Senk gen mwens pase 6, se konsa li dwe a gòch la. Senk gen plis pouvwa pase 2, se konsa li dwe dwat, ak li se tou pi gran pase 4, se konsa li dwe dwe gen dwa ankò. Sepandan, pa gen okenn pitit isit la. Konsèy la se nil. Sa vle di ke 5 se pa nan pyebwa nou yo. 

Nou kapab fè rechèch pye bwa a binè ak kòd la sa yo: Nan chak ne, nou tcheke yo wè si nou jwenn valè a nou ap chèche pou. Si nou pa jwenn li, nou detèmine si li ta dwe sou yo ak sou gòch la oswa dwa tcheke ki subtree. Sa a riban ap kontinye desann pye bwa a jiskaske pa genyen okenn ne timoun ki sou swa bò gòch la oswa dwa. 

Sonje ke 5 pa t 'nan pyebwa sa a. Ki jan nou insert li? Pwosesis la sanble menm jan nan rechèch. Nou répétèr desann pye bwa a kòmanse nan 6, kite a 2, dwa 4, e yo gen dwa ankò, men 4 pa gen okenn timoun ki sou bò sa a. Sa a pral pozisyon nan nouvo pou 5, epi li pral kòmanse ki pa gen okenn timoun yo. 

Konbyen vit yo se operasyon a nan yon pyebwa rechèch binè? Sonje ke Bigohnotation ap chèche bay yon mare anwo kay la. Nan ka ki pi mal la, pyebwa nou te kapab tou senpleman gen yon lis lye sa vle di ensèsyon, sipresyon, ak rechèch te kapab pran tan pwopòsyonèl ak kantite nœuds nan pyebwa sa a. Sa a se O (n). 

Pou egzanp, sa ki annapre yo se yon binè pyebwa ki valab rechèch. Sepandan, si nou eseye jwenn 9, nou dwe Traverse chak ne. Li pa gen okenn pi bon pase yon lis lye. Idealman, nou ta vle chak ne nan pyebwa rechèch binè nou yo gen 2 timoun yo. Fason sa a, ensèsyon, sipresyon ak rechèch ta pran, nan pi move, O (boutèy demi lit n) tan. Pyebwa ki sou devan ka pi balanse, tankou sa a. Koulye a, leve je l 'nenpòt ki valè pran, nan pifò, 3 etap. Pyebwa sa a se balanse, siyifikasyon bagay ki se gen yon pwofondè minimòm relatif nan ki kantite nœuds. 

Ap chèche pou yon valè nan yon pyebwa rechèch binè balanse se menm jan ak rechèch binè sou yon etalaj Ranje. An reyalite, si nou pa bezwen insert oswa efase atik, yo konpòte egzakteman menm jan an. Sepandan, yon estrikti pye bwa se pi bon pou parusyon manyen ak reyur 

Non mwen se Bannus van der Kloot. Sa a se CS50.