Endis pye bwa binè

Mwen te rankontre kalite pwoblèm sa a. Li nesesè pou aplike yon veso depo done ki bay fonksyonalite sa yo:

• mete nouvo eleman
• retire eleman pa nimewo seri
• jwenn eleman pa nimewo ordinal
• done yo estoke nan fòm klase

Done yo toujou ap ajoute ak retire, estrikti a dwe asire vitès operasyon rapid. Nan premye mwen te eseye aplike yon bagay konsa lè l sèvi avèk resipyan estanda soti nan èdtan. Chemen sa a pa te kouwone ak siksè ak konpreyansyon a te vin ke mwen te bezwen aplike yon bagay tèt mwen. Bagay la sèlman ki te vin nan tèt ou te sèvi ak yon pye bwa rechèch binè. Paske li satisfè egzijans ensèsyon rapid, efase ak depo done nan fòm klase. Tout sa ki rete se konnen ki jan yo endis tout eleman yo ak rekalkile endis yo lè pye bwa a chanje.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Atik la ap genyen plis foto ak teyori pase kòd. Ou ka wè kòd la nan lyen ki anba a.

Pwa

Pou reyalize sa a, pye bwa a te sibi yon ti modifikasyon, yo te ajoute plis enfòmasyon sou pwa ne. Pwa a ne se kantite pitit pitit sa a ne + 1 (pwa yon sèl eleman).

Fonksyon pou jwenn pwa ne:

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

    return 0;
}

Pwa a nan fèy la se korespondan egal a 0.

Apre sa, ann ale nan yon reprezantasyon vizyèl nan yon egzanp tankou yon pye bwa. nwa kle ne a pral montre an koulè (valè a pa pral montre, paske sa a pa nesesè), an wouj - pwa ne, vèt - endèks ne.

Lè pye bwa nou an vid, pwa li se 0. Ann ajoute yon eleman rasin nan li:

Pwa pye bwa a vin 1, pwa eleman rasin lan vin 1. Pwa eleman rasin lan se pwa pye bwa a.

Ann ajoute kèk eleman plis:

Chak fwa yo ajoute yon nouvo eleman, nou desann nœuds yo epi ogmante kontwa pwa chak nœuds pase. Lè yo kreye yon nouvo ne, yo ba li yon pwa 1. Si yon ne ak yon kle sa a deja egziste, Lè sa a, nou pral kouvri valè a epi tounen moute nan rasin lan, anile chanjman yo nan pwa yo nan tout nœuds ke nou te pase.
Si yo retire yon ne, Lè sa a, nou desann epi diminye pwa yo nan nœuds yo pase.

Endèks

Koulye a, kite a deplase sou ki jan yo endèks nœuds. Nœuds pa klèman estoke endèks yo, li se kalkile ki baze sou pwa a nan nœuds yo. Si yo estoke endèks yo, Lè sa a, li ta dwe obligatwa O (n) tan pou mete ajou endèks yo nan tout nœuds apre chak chanjman nan pye bwa a.
Ann ale nan yon reprezantasyon vizyèl. Pye bwa nou an vid, ann ajoute 1ye nœud la nan li:

Premye ne a gen yon endèks 0, epi kounye a 2 ka posib. Nan premye a, endèks la nan eleman rasin lan pral chanje, nan dezyèm lan li pa pral chanje.

Nan rasin lan, anba pye bwa gòch la peze 1.

Dezyèm ka:

Endèks rasin lan pa t chanje paske pwa sous pyebwa gòch li a rete 0.

Endèks yon ne kalkile kòm pwa nan subtree gòch li + nimewo a pase nan men paran an. Ki sa ki nimewo sa a?, Sa a se kontwa endèks la, okòmansman li egal a 0, paske rasin lan pa gen paran. Lè sa a, tout depann sou kote nou desann nan timoun gòch la oswa youn nan dwa. Si sou bò gòch la, Lè sa a, pa gen anyen ki ajoute nan kontwa an. Si nou ajoute endèks la nan ne aktyèl la nan youn nan dwa.

Pa egzanp, kijan yo kalkile endèks yon eleman ki gen kle 8 (pitit dwat rasin lan). Sa a se "Endèks Rasin" + "pwa nan sous-arbre gòch nan ne ak kle 8" + "1" == 3 + 2 + 1 == 6
Endèks eleman ki gen kle 6 la pral "Root Index" + 1 == 3 + 1 == 4

An konsekans, li pran tan jwenn ak efase yon eleman pa endèks O (boutèy demi lit n), paske pou nou jwenn eleman vle a nou dwe premye jwenn li (desann soti nan rasin nan eleman sa a).

Pwofondè

Ki baze sou pwa a, ou ka tou kalkile pwofondè pye bwa a. Li nesesè pou balanse.
Pou fè sa, pwa a nan ne aktyèl la dwe awondi nan premye nimewo a nan pouvwa a nan 2 ki pi gran pase oswa egal a pwa bay la epi pran logaritm binè a soti nan li. Sa a pral ban nou pwofondè nan pye bwa a, sipoze li balanse. Pye bwa a balanse apre mete yon nouvo eleman. Mwen pa pral bay yon teyori sou fason pou balanse pye bwa. Kòd sous yo bay yon fonksyon balanse.

Kòd pou konvèti pwa nan pwofondè.

/*
 * Возвращает первое число в степени 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));
}

Rezilta

• ensèsyon yon nouvo eleman rive nan O (boutèy demi lit n)
• efase yon eleman pa nimewo seri rive nan O (boutèy demi lit n)
• jwenn yon eleman pa nimewo seri rive nan O (boutèy demi lit n)

Vitès O (boutèy demi lit n) Nou peye pou lefèt ke tout done yo estoke nan fòm klase.

Mwen pa konnen ki kote yon estrikti konsa ta ka itil. Jis yon devinèt yon lòt fwa ankò konprann ki jan pye bwa travay. Mèsi pou atansyon ou.

Referans

• Kòd sous pye bwa

Pwojè a gen done tès pou tcheke vitès operasyon an. Pye bwa a ap ranpli 1000000 eleman. Epi gen yon sipresyon sekans, ensèsyon ak rekipere eleman yo 1000000 yon fwa. Sa vle di 3000000 operasyon yo. Rezilta a te tounen byen bon ~ 8 segonn.

Sous: www.habr.com