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