[Powered by Google Translate] Kif inti tirrappreżenta l-membri kollha tal-familja tiegħek fil-kompjuter? Aħna jista 'sempliċement jużaw lista, iżda hemm ġerarkija ċara hawnhekk. 

Ejja ngħidu aħna qed jibdew bil tiegħek great-nanna, Alice. Hija għandha 2 wlied, Bob u grandfather tiegħek, Charlie. Charlie għandha 3-tfal, ziju tiegħek, Dave, zija tiegħek, Eve, u missierek, Fred. Inti tifel biss Fred s. 

Għaliex kieku jorganizza membri tal-familja tiegħek b'dan il-mod tkun aħjar minn-rappreżentanza lista sempliċi? Raġuni waħda hija li dan ġerarkika istruttura, imsejħa "siġra," fih informazzjoni aktar minn sempliċi lista. Nafu r-relazzjonijiet familjali bejn kulħadd biss billi teżamina l-siġra. Ukoll, jista 'tħaffef ħarsa-up time bil-kbir, jekk id-data tas-siġar huwa magħżul. 

Aħna ma jistgħux jieħdu vantaġġ ta 'dak hawn, imma aħna ser tara eżempju ta' dan dalwaqt. Kull persuna hija rrappreżentata minn nodu fuq is-siġra. Lymph nodes jista 'jkollhom tfal kif ukoll node ġenitur. Dawn huma t-termini tekniċi, anke meta jużaw siġar għall-affarijiet minbarra familji. Node Alice għandu 2 tfal u l-ebda ġenituri, filwaqt node Charlie ma għandha 3 itfal u 1 ġenitur. 

A node werqa huwa wieħed li ma jkollu ebda tfal fuq il-tarf ta 'barra tas-siġra. Il-node topmost tas-siġra, il-node għerq, m'għandha l-ebda ġenitur. 

A siġra binarju huwa tip speċifiku ta 'siġra, fejn kull node għandha, l-aktar, 2 tfal. Hawn hu l-Struct ta 'nodu ta' siġra binarju fil C. Kull node għandha xi data assoċjata magħha u 2 pointers għal punti strateġiċi oħra. 

Fil siġra tal-familja tagħna, id-dejta assoċjata kien l-isem ta 'kull persuna. Hawnhekk huwa int, għalkemm tista 'tkun xi ħaġa. Kif jirriżulta, siġra binarju ma tkunx rappreżentazzjoni tajba għal familja, billi n-nies spiss ikollhom aktar minn 2 tfal. 

A siġra tfittxija binarju huwa speċjali, tip ordnat ta 'siġra binarju li jippermetti li tħares lejn il-valuri malajr. Inti jista 'jkollok ndunat li kull node taħt l-għerq ta 'siġra huwa l-għerq ta 'xi siġar, imsejħa "subtree." Hawnhekk, l-għerq tal-siġra hija 6, u tat-tfal tagħha, 2, hija l-għerq ta 'subtree. 

Fil siġra tfittxija binarju il-valuri kollha ta 'node id-dritt subtree huma akbar mill-valur tal-node s. Hawn: 6. Ukoll, il-valuri fil subtree xellug node s huma inqas mill-valur tal-node s. Jekk għandna bżonn biex jimmaniġġaw valuri duplikati, nistgħu nbiddlu jew ta 'dawk għal inugwaljanza laxka, jfisser il-valuri identiċi jista 'jaqa' jew fuq il-lemin jew xellug, sakemm aħna konsistenti dwar dan kollu. Dan siġra hija siġra tfittxija binarju għaliex isegwi dawn ir-regoli. 

Dan huwa kif ser tfittex jekk aħna mdawwar l-lymph fis structs Ċ. Avviż li jekk xi tifel ikun nieqes, l-pointer huwa null. Kif nistgħu tikkontrolla biex tara jekk 7 huwa fil-siġra? Nibdew fil-għerq. Seba huwa akbar minn 6, hekk jekk huwa fil-siġra, għandu jkun fuq il-lemin. Imbagħad, huwa inqas minn 8, u għalhekk għandu jitħalla. Hawnhekk, sibna 7. Issa, aħna ser jiċċekkja għal 5. Ħames huwa inqas minn 6, u għalhekk għandu jkun lejn ix-xellug. Ħames huwa akbar minn 2, għalhekk għandu jkun id-dritt, u huwa wkoll akbar minn 4, u għalhekk għandu jkun tajjeb mill-ġdid. Madankollu, m'hemm l-ebda wild hawnhekk. Il-pointer huwa null. Dan ifisser li 5 ma tkunx siġra tagħna. 

Nistgħu tfittxija-siġra binarju bil-kodiċi li ġej: F'kull node, aħna tikkontrolla biex tara jekk sibna il-valur li qed infittxu. Jekk aħna ma jsibuha, aħna jiddeterminaw jekk għandu jkun fuq il-lemin jew xellug u jiċċekkjaw li subtree. Dan loop se tkompli r-siġra sakemm ma jkunx hemm node wild jew fuq il-lemin jew xellug. 

Ftakar li 5 ma kienx fil-siġra. Kif nistgħu daħħal dan? Il-proċess jistenna simili għal tfittxija. Aħna ttenni l-siġra tibda minn 6, xellug għal 2, dritt għall-4, u d-dritt għal darb'oħra, iżda 4 m'għandha l-ebda tfal fuq din in-naħa. Dan se jkun l-pożizzjoni l-ġdida għal 5, u se tibda bl-ebda tfal. 

Kif fast huma operazzjonijiet fuq siġra tfittxija binarju? Ftakar li Bigohnotation tfittex li tipprovdi marbuta fuq. Fl-agħar każ, siġra tagħna tista 'sempliċement tkun lista marbuta li jfisser li inserzjoni, tħassir, u t-tiftix tista 'tieħu żmien proporzjonali għall-għadd ta' punti strateġiċi fil-siġra. Dan huwa O (n). 

Per eżempju, dan li ġej huwa siġra valida tfittxija binarja. Madankollu, jekk aħna tipprova ssib 9, irridu travers kull node. Huwa l-ebda aħjar minn lista marbuta. Idealment, aħna rridu kull node ta 'siġar tagħna tfittxija binarja li jkollha 2 tfal. Dan il-mod, inserzjoni, tħassir u tiftix se tieħu, fl-agħar, O (log n) iż-żmien. Is-siġra minn qabel tista 'tkun aktar ibbilanċjata, bħal dan. Issa, tfittex up xi valur tieħu, l-aktar, 3 passi. Dan siġra hija bilanċjata, fis-sens li huwa għandu fond minimu relattiva għan-numru ta 'nodes. 

Looking for valur fil-siġra bilanċjat tfittxija binarju huwa simili għal tfittxija binarju fuq firxa magħżula. Fil-fatt, jekk aħna ma bżonn li tiddaħħal jew tħassar oġġetti, għandhom iġibu ruħhom eżattament bl-istess mod. Madankollu, struttura ta 'siġra hija aħjar għall inserzjonijiet tqandil u tħassir 

Jisimni Bannus Van der Kloot. Dan huwa CS50.