🥇Indexable nga binary tree

Nakasugat ko sa mosunod nga matang sa problema. Kinahanglan nga ipatuman ang usa ka sudlanan sa pagtipig sa datos nga naghatag sa mosunod nga gamit:

isulod ang bag-ong elemento
kuhaa ang elemento pinaagi sa serial number
pagkuha elemento pinaagi sa ordinal nga numero
data gitipigan sa sorted porma

Ang datos kanunay nga gidugang ug gitangtang, ang istruktura kinahanglan nga masiguro ang paspas nga katulin sa operasyon. Sa sinugdan gisulayan nako nga ipatuman ang ingon nga butang gamit ang standard nga mga sudlanan gikan sa oras. Kini nga dalan wala gipurongpurongan sa kalampusan ug ang pagsabut miabut nga ako kinahanglan sa pagpatuman sa usa ka butang sa akong kaugalingon. Ang bugtong butang nga naa sa hunahuna mao ang paggamit sa usa ka binary nga punoan sa pagpangita. Tungod kay nakab-ot niini ang kinahanglanon sa paspas nga pagsal-ot, pagtangtang ug pagtipig sa datos sa gihan-ay nga porma. Ang nahabilin mao ang paghunahuna kung giunsa ang pag-indeks sa tanan nga mga elemento ug pagkalkula pag-usab sa mga indeks kung nabag-o ang kahoy.

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

Ang artikulo adunay daghang mga litrato ug teorya kaysa code. Ang code mahimong makita sa link sa ubos.

Timbang

Aron makab-ot kini, ang kahoy miagi sa usa ka gamay nga pagbag-o, dugang nga kasayuran ang gidugang gibug-aton node. Ang gibug-aton sa node gidaghanon sa mga kaliwat niini nga node + 1 (kabug-at sa usa ka elemento).

Function alang sa pagkuha sa gibug-aton sa node:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

Ang gibug-aton sa sheet katumbas nga katumbas sa 0.

Sunod, magpadayon kita sa usa ka biswal nga representasyon sa usa ka pananglitan sa ingon nga kahoy. Itom ang node key ipakita sa kolor (ang kantidad dili ipakita, tungod kay dili kini kinahanglan), pula - gibug-aton sa knot, berde - indeks sa node.

Kung walay sulod ang atong kahoy, ang gibug-aton niini 0. Idugang nato ang usa ka elemento sa gamut niini:

Ang gibug-aton sa kahoy nahimong 1, ang gibug-aton sa gamut nga elemento nahimong 1. Ang gibug-aton sa gamut nga elemento mao ang gibug-aton sa kahoy.

Atong idugang ang pipila pa ka elemento:

Sa matag higayon nga ang usa ka bag-ong elemento idugang, kami moadto sa mga node ug dugangan ang gibug-aton nga counter sa matag node nga gipasa. Kung ang usa ka bag-ong node gihimo, usa ka gibug-aton ang gihatag niini 1. Kung ang usa ka node nga adunay ingon nga yawe anaa na, nan atong i-overwrite ang bili ug mobalik sa gamut, nga kanselahon ang mga pagbag-o sa mga gibug-aton sa tanan nga mga node nga atong naagian.
Kung ang usa ka node gikuha, nan kami moadto ug pagkunhod sa mga gibug-aton sa gipasa nga mga node.

Mga indeks

Karon magpadayon kita sa kung giunsa ang pag-index sa mga node. Ang mga node dili tin-aw nga nagtipig sa ilang indeks, kini gikalkula base sa gibug-aton sa mga node. Kung gitipigan nila ang ilang indeks, kinahanglan kini O (n) oras sa pag-update sa mga indeks sa tanan nga mga node pagkahuman sa matag pagbag-o sa kahoy.
Mopadayon kita sa usa ka biswal nga representasyon. Ang atong kahoy walay sulod, atong idugang ang 1st node niini:

Ang una nga node adunay indeks 0, ug karon 2 ka kaso ang posible. Sa una, ang indeks sa elemento sa ugat mausab, sa ikaduha dili kini mausab.

Sa gamut, ang wala nga subtree adunay gibug-aton nga 1.

Ikaduha nga kaso:

Ang indeks sa gamut wala mausab tungod kay ang gibug-aton sa wala nga subtree nagpabilin nga 0.

Ang indeks sa usa ka node gikalkulo ingon nga gibug-aton sa wala nga subtree + ang gidaghanon nga gipasa gikan sa ginikanan. Unsa kini nga numero?, Kini ang index counter, sa sinugdan kini katumbas sa 0, kay ang gamot walay ginikanan. Unya ang tanan nagdepende kung asa kita moadto sa wala nga bata o sa tuo. Kung sa wala, wala’y idugang sa counter. Kung atong idugang ang index sa kasamtangan nga node sa tuo.

Pananglitan, kung giunsa pagkalkulo ang indeks sa usa ka elemento nga adunay yawe 8 (ang tuo nga bata sa gamut). Kini ang "Root Index" + "gibug-at sa wala nga subtree sa node nga adunay yawe 8" + "1" == 3 + 2 + 1 == 6
Ang indeks sa elemento nga adunay yawe 6 mao ang "Root Index" + 1 == 3 + 1 == 4

Tungod niini, nagkinahanglag panahon aron makuha ug matangtang ang usa ka elemento pinaagi sa indeks O (pag-log n), tungod kay aron makuha ang gitinguha nga elemento kinahanglan una naton pangitaon kini (kanaog gikan sa gamut hangtod niini nga elemento).

Giladmon

Base sa gibug-aton, mahimo usab nimo kuwentahon ang giladmon sa kahoy. Gikinahanglan alang sa pagbalanse.
Sa pagbuhat niini, ang gibug-aton sa kasamtangan nga node kinahanglan nga rounded sa unang numero ngadto sa gahum sa 2 nga mas dako pa kay sa o katumbas sa gihatag nga gibug-aton ug sa pagkuha sa binary logarithm gikan niini. Kini maghatag kanato sa giladmon sa kahoy, sa paghunahuna nga kini balanse. Balanse ang kahoy human makasulod ug bag-ong elemento. Dili ko mohatag og teorya kon unsaon pagbalanse ang mga kahoy. Ang mga source code naghatag usa ka function sa pagbalanse.

Code alang sa pag-convert sa gibug-aton ngadto sa giladmon.

/*
 * Возвращает первое число в степени 2, которое больше или ровно x
 */
uint64_t bntree::cpl2(uint64_t x) {
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    x = x | (x >> 32);

    return x + 1;
}

/*
 * Двоичный логарифм от числа
 */
long bntree::ilog2(long d) {
    int result;
    std::frexp(d, &result);
    return result - 1;
}

/*
 * Вес к глубине
 */
uint64_t bntree::weight_to_depth(node_t *p) {
    if (p == NULL) {
        return 0;
    }

    if (p->weight == 1) {
        return 1;
    } else if (p->weight == 2) {
        return 2;
    }

    return this->ilog2(this->cpl2(p->weight));
}

Mga resulta

Ang pagsulod sa usa ka bag-ong elemento mahitabo sa O (pag-log n)
Ang pagtangtang sa usa ka elemento pinaagi sa serial number mahitabo sa O (pag-log n)
ang pagkuha sa usa ka elemento pinaagi sa serial number mahitabo sa O (pag-log n)

Bilis O (pag-log n) Nagbayad kami alang sa kamatuoran nga ang tanan nga datos gitipigan sa lainlain nga porma.

Wala ko kahibalo kung asa mahimong mapuslanon ang ingon nga istruktura. Usa lang ka puzzle aron masabtan pag-usab kung giunsa ang pagtrabaho sa mga kahoy. Salamat sa imong pagtagad.

mga pakisayran

Punoan nga source code

Ang proyekto adunay sulud nga datos sa pagsulay aron masusi ang katulin sa operasyon. Ang kahoy napuno 1000000 mga elemento. Ug adunay sunod-sunod nga pagtangtang, pagsal-ot ug pagkuha sa mga elemento 1000000 kausa. Kana mao 3000000 mga operasyon. Ang resulta nahimo nga maayo kaayo ~ 8 segundos.

Source: www.habr.com

Gi-index nga binary nga kahoy

Timbang

Mga indeks

Giladmon

Mga resulta

mga pakisayran

Idugang sa usa ka comment Отменить ответ