Duuma arbo

Ĉi tiu artikolo bezonas poluradon, ĉar ĝi montras stilajn kaj/aŭ gramatikajn kaj/aŭ strukturajn problemojn, kiuj ne konformas al stilogvido.

La priskribo de la problemo troviĝas ĉi tie. Bonvolu ŝanĝi la enhavon por plibonigi la artikolon.

verŝajne (rapide fuŝema) duon-aŭtomata maŝin-tradukaĵo el la angla vikipedio farita per uzanto:Maksim

En komputiko, duuma arbo estas arba datumstrukturo, en kiu ĉiu vertico havas maksimume du infanojn. Ofte la infanaj verticoj estas nomita maldekstra kaj dekstra. Duumaj arboj estas ofte uzata por fari duumajn serĉajn arbojn.

Difinoj por radikhavaj arboj

Direkta eĝo estas la konekto de la gepatro al la infano.

Vertico, kiu ne havas infanojn nomiĝas folio (ankaŭ fin-punkto).

La profundeco de vertico n estas la longo de la vojo de la radiko al la vertico. La aro de ĉiuj verticoj je donita profundeco estas fojfoje mallonge nomita nivelo de la arbo (pli bone: nivelaro, aro de verticoj je nivelo n). Tiel la radiko estas ĉe nivelo nulo.

La alteco de arbo estas la longo de la radiko al la plej profunda folio.

Verticoj, kiuj havas komunan gepatron, estas nomita gefratoj.

Se ekzistas direkta vojo de vertico p al vertico q, tiam p estas pra-ulo de q kaj q estas posteulo de p.

La grandeco de vertico estas la nombro de posteuloj, kiujn ĝi havas inkluzive ĝi mem. Tiel folioj havas grandecon 1.

Tipoj de duumaj arboj

En duuma arbo ĉiuj verticoj havas maksimume du infanojn.

En plena duuma arbo ĉiuj verticoj havas aŭ nulo aŭ du infanojn.

perfekta duuma arbo (fojfoje nomita kompleta duuma arbo) estas plena duuma arbo, en kiu ĉiuj folioj (verticoj kun nul infanoj) estas je la sama profundeco (distanco de la radiko).

preskaŭ perfekta duuma arbo estas arbo, en kiu ĉiu dekstra infano havas ĉiam maldekstran gefraton. Por maldekstra infano ne certe estas dekstra gefrato.

Difino en grafeteorio

En grafeteorio oni uzas la jenan difinon: Duuma arbo estas konektita necikla grafeo tia, ke la grado (nombro de eĝoj) de ĉiu vertico estas ne pli ol 3. Oni povas pruvi, ke en ĉiu duuma arbo estas ekzakte du pli da verticoj de grado unu ol estas de grado tri, sed povas esti iu ajn nombro de verticoj de grado du. radikita duuma arbo estas tia grafeo, kie unu el ĝiaj verticoj de grado ne pli ol 2 estas elektita kiel la radiko.

Kun la radiko tiel elektita, ĉiu vertico havos unikan difinitan gepatron kaj ĝis du infanojn; tamen estas nesufiĉe da informoj por distingi inter maldekstra kaj dekstra infano. Se oni rezignas pri la postulo pri konekteco, tiel permesanta multaj, disaj konektitaj komponentoj en la grafeo, oni nomas la strukturon arbaro.

Alia maniero, difini duumajn arbojn, estas uzi rekursian difinon pri orientitaj grafeoj. Duuma arbo estas aŭ:

Sola vertico.
Grafeo formita per de preni du duumaj arboj, aldoni verticon kaj aldoni eĝojn direktitajn de la nova vertico al la radikoj de da du duumaj arboj. (??)

Tio ĉi ankaŭ ne difinas la ordon de la infanoj, sed fiksas specifan verticon kiel radiko.

Manieroj por stoki duumaj arboj

Duumaj arboj povas esti konstruita de programlingvo en pluraj manieroj. En lingvo kun rikordoj kaj referencoj, duumaj arboj estas tipe konstruita tiel, ke oni faras arban vertican strukturon, kie ĉiu vertico enhavas iujn datumojn kaj referencojn al ĝia maldekstra kaj dekstra infano. Foje ĝi ankaŭ havas referencon al ĝia unika gepatro. Se vertico havas malpli ol du infanojn, kelkaj de la infanaj referencoj povas havi specialan nulan valoron, aŭ ili povas referenci al speciala garda vertico.

Duumaj arboj povas ankaŭ esti konservitaj kiel implica datumstrukturo en tabeloj, kaj se la arbo estas plena duuma arbo, tiu maniero ĉi malŝparas neniun spacon. En tiu ĉi kompakta aranĝo, se vertico havas indekson i, ĝiaj infanoj troviĝas je indeksoj 2i+1 kaj 2i+2, dum ĝia gepatro (se ĝi havas gepatro) troviĝas je indekso $\left\lfloor {\frac {i-1}{2}}\right\rfloor$ (kondiĉe, ke la radiko havas indekson nulo). Ĉi tiu maniero havas avantaĝon de pli kompakta konservo, kaj la verticoj pli facile (rapide) troveblas, precipe dum antaŭorda trairo. Aliflanke ĝi postulas seninterrompan, apudan [memoro]n, estas multekosta por ĝi kreski, kaj malŝparas memorspacon proporcie al 2^h - n por arbo kun alteco h kun n verticoj.

En lingvoj kun etikedaj unioj kiel ML, arba vertico estas ofte etikeda unio de du tipoj de verticoj, unu kun 3-opo da datumoj, maldekstra infano kaj dekstra infano, kaj la alia, kiu estas "folia" vertico, kiu enhavas neniujn datumojn kaj funkcias kiel la nula valoro en lingvoj kun referencoj.

Manieroj de trairado duumajn arbojn

Ofte oni deziras viziti ĉiujn verticojn en arbo kaj ekzameni la valoron tie. Estas pluraj komunaj sinsekvoj, per kiu oni povas viziti la verticojn, kaj ĉiu havas utilajn ecojn, kiuj estas eluzataj en algoritmoj por duumaj arboj.

Antaŭ-orda, en-orda kaj post-orda trairo

Ĉefa artikolo: Arbotrairo.

Antaŭ-orda, en-orda kaj post-orda trairo vizitas ĉiun verticon en arbo per rekuro (rekursio) vizitanta ĉiun verticon en la maldekstra kaj dekstra subarboj de la radiko. Se la radika vertico estas vizitita antaŭ ĝia subarboj, ĉi tiu estu nomata ĉi tie antaŭ-orda trairo; se poste, tiam post-orda; se inter ambaŭ, tiam en-orda trairo. En-orda trairo estas utila en duumaj serĉaj arboj, kie ĉi tiu trairo vizitas la verticojn en pligrandiĝanta ordo.

Profundiĝema ordo

En profunden-unue-ordo ni ĉiam provas, viziti la verticon - kiel eble plej longe - for de la radiko, sed kun la kondiĉo, ke estu infano de vertico, kiun ni jam vizitis. Malvsame al profundiĝema trairo de grafeoj estas neniu bezono memori ĉiujn verticojn jam vizititajn, ĉar la arbo ne povas enhavi ciklojn. Antaŭ-orda, en-orda kaj post-orda trairo estas ĉiuj specialaj okazoj de tiu ĉi. Ridardu Profundiĝema trairo por pli da informo.

Larĝema ordo

Kontrastanta kun profundiĝema ordo estas larĝema ordo, kiu ĉiam provas, viziti la verticon plej proksiman al la radiko, kiu ĝi ne jam vizitis. Ridardu Larĝiĝema trairo por pli da informo.

Enkodigoj (kodoprezentoj)

Koncizaj kodoprezentoj

Konciza datumstrukturo estas iu, kiu prenas kiel eble plej malmulte da spaco. La nombro de malsamaj duumaj arboj de $n$ verticoj estas $\mathrm {C} _{n}$ , la $n$ a Katalana nombro (alprenanta, ke ni vidas arbojn kun identa strukturo kiel identaj). Por granda $n$ , tiu ĉi estas pli-malpli $4^{n}$ ; tial ni bezonas almenaŭ pli-malpli $\log _{2}4^{n}=2n$ bitojn por enkodi. Konciza duuma arbo pro tio devus okupi nur 2 bitojn je vertico.

Unu simpla reprezento, kiu atingas tiun ĉi limo, estas viziti la verticojn de la arbo en antaŭa ordo, eliganta "1" por interna vertico kaj "0" por folio. [1] Se la arbo enhavas datumojn , ni povas simple samtempe registri ĝin en najbara tabelo en antaŭordo. La sekva funkcio faras tion:

function EnkodiguKoncize(vertico n, bitĉeno strukturo, tabelo datumoj) {
    if n = nil then
        aldonu 0 al strukturo;
    else
        aldonu 1 al strukturo;
        aldonu n.datumoj al datumoj;
        EnkodiguKoncize(n.maldekstra, strukturo, datumoj);
        EnkodiguKoncize(n.dekstra, strukturo, datumoj);
}

Finfine la bitĉeno strukturo havas nur $2n+1$ , kie $n$ estas la nombro de internaj verticoj; ni eĉ ne devas registri ĝian longon. Por montri, ke neniu informo estas perdita, ni povas konverti la rezulton al la originala arbo tiel ĉi:

function ElkodiguKoncize(bitĉeno strukturo, tabelo datumoj) {
    forprenu unuan biton de strukturo kaj metu ĝin en b
    if b = 1 then
        kreu novan verticon n
        forprenu unuan elementon kaj metu ĝin en n.datumoj
        n.maldekstra = ElkodiguKoncize(strukturo, datumoj)
        n.dekstra = ElkodiguKoncize(strukturo, datumoj)
        return n
    else
        return nil
}

Pli malnaiva koncizaj prezentoj permesas ne nur kompaktan registradon de arboj, sed eĉ utilaj operacioj sur tiuj arboj rekte, dum ili estas ankoraŭ en ilia konciza formo.

Enkodigi n-umaj arboj kiel duumaj arboj

Estas bijekcio (unu-al-unu-mapo) inter ĝenerale ordaj arboj kaj duumaj arboj, kiu precipe estas uzitaj de Lisp, por prezenti ĝeneralajn ordajn arbojn kiel duumaj arboj. Ĉiu vertico N en la orda arbo korespondas al vertico N' en la duuma arbo; la maldekstra infano de N' estas la vertico korespondanta al la unua infano de N, kaj la dekstra infano de N' estas la vertico korespondanta al la venonta frato de N --- tio estas, la venonta vertico en ordo inter la infanoj de la gepatro de N.

Unu maniero percepti tion ĉi estas, ke ĉiuj verticaj infanoj estas en ligillisto, ĉenitaj kun iliaj dekstra kampo, kaj la vertico havas nur referencon al la komenco aŭ kapo de tiu ĉi listo, tra ĝia maldekstra kampo.

Ekzemple en la arbo maldekstren, A havas la 6 infanojn {B,C,D,E,F,G}. Ĝi povas esti konvertita al la duuma arbo dekstren.

Oni povas pensi pri la duuma arbo kiel la originala arbo kuŝigita, kun la nigraj maldekstraj eĝoj prezentantaj unua infano kaj la bluaj dekstraj eĝoj prezentantaj venonta gefrato. La folioj de la arbo maldekstre oni skribus en Lisp kiel:

(((M N) H I) C D ((O) (P)) F (L))

kiu estus realigita en memoro kiel la duuma arbo dekstre, sen literoj sur tiuj verticoj, kiuj havas maldekstran infanon.

Referencoj

Donald Knuth. The art of computer programming vol 1. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, especially subsections 2.3.1–2.3.2 (pp.318–348).
Kenneth A Berman, Jerome L Paul. Algorithms: Parallel, Sequential and Distributed. Course Technology, 2005. ISBN 0-534-42057-5. Chapter 4. (pp.113–166).

Vidu ankaŭ