Indexed binary tsob ntoo

Kuv tau ntsib nrog txoj haujlwm hauv qab no: Kuv xav tau siv lub thawv cia cov ntaub ntawv uas muab cov haujlwm hauv qab no:

• ntxig ib qho tshiab
• rho tawm ib qho khoom los ntawm tus lej ordinal
• tau ib qho khoom los ntawm tus lej ordinal
• cov ntaub ntawv khaws cia rau hauv daim ntawv txheeb cais

Cov ntaub ntawv raug ntxiv thiab rho tawm tas li, thiab cov qauv yuav tsum ua kom ua haujlwm sai. Thaum xub thawj, kuv sim siv qhov no siv cov thawv txheem los ntawm ua stdTxoj kev no tsis ua tiav, thiab nws tau pom tseeb tias kuv xav tau kev siv qee yam kuv tus kheej. Tib txoj kev daws teeb meem uas los rau hauv siab yog siv tsob ntoo tshawb nrhiav binary, vim nws ua tau raws li qhov yuav tsum tau ua rau kev ntxig thiab rho tawm sai, thiab khaws cov ntaub ntawv raws li kev txiav txim. Txhua yam uas tseem tshuav yog xam seb yuav ua li cas thiaj li ntsuas tau txhua yam ntsiab lus thiab rov suav cov ntsuas thaum twg tsob ntoo hloov pauv.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Tsab xov xwm no yuav muaj ntau cov duab thiab kev xav ntau dua li cov lej. Koj tuaj yeem saib cov lej ntawm qhov txuas hauv qab no.

Nyhav

Rau lub hom phiaj no tsob ntoo tau hloov kho me ntsis thiab cov ntaub ntawv ntxiv tau ntxiv qhov hnyav pob caus. Qhov hnyav ntawm pob caus yog tus naj npawb ntawm cov xeeb ntxwv ntawm lub node no + 1 (qhov hnyav ntawm ib yam khoom).

Muaj nuj nqi kom tau qhov hnyav ntawm ib lub node:

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

    return 0;
}

Qhov hnyav ntawm nplooj yog li ntawd sib npaug rau 0.

Tom ntej no, peb yuav txav mus rau qhov sawv cev ntawm ib qho piv txwv ntawm cov ntoo zoo li no. Dub cov xim yuav qhia tus yuam sij ntawm node (tus nqi yuav tsis pom, vim tsis tas yuav muaj nws), xim liab - qhov hnyav ntawm lub node, ntsuab - index ntawm node.

Thaum peb tsob ntoo khoob, nws qhov hnyav yog 0. Cia peb ntxiv ib qho hauv paus rau nws:

Qhov hnyav ntawm tsob ntoo dhau los ua 1, qhov hnyav ntawm cov hauv paus yog 1. Qhov hnyav ntawm cov hauv paus yog qhov hnyav ntawm tsob ntoo.

Cia peb ntxiv ob peb yam ntxiv:

Txhua zaus uas muaj ib qho tshiab ntxiv, peb nqis los ntawm cov nodes thiab nce qhov hnyav rau txhua lub node uas tau hla mus. Thaum ib lub node tshiab raug tsim, nws qhov hnyav raug muab faib. 1Yog tias ib lub node uas muaj tus yuam sij zoo li no twb muaj lawm, peb sau dua tus nqi thiab rov qab mus rau hauv paus, tshem tawm qhov hnyav hloov pauv rau txhua lub nodes uas peb tau dhau los.
Yog tias ib lub node raug rho tawm, peb nqis mus thiab txo qhov hnyav ntawm cov nodes uas peb tau dhau los.

Indexes

Tam sim no cia peb mus rau yuav ua li cas rau cov nodes index. Cov nodes tsis khaws lawv cov index meej; nws yog xam raws li qhov hnyav ntawm lub node. Yog tias lawv tau khaws lawv cov index, nws yuav xav tau Nws) lub sijhawm los hloov kho cov ntsuas ntawm txhua lub nodes tom qab txhua qhov kev hloov pauv hauv tsob ntoo.
Cia peb mus rau qhov kev sawv cev pom. Peb tsob ntoo khoob lawm, cia peb ntxiv thawj lub node rau nws:

Tus node thawj zaug muaj ib qho index 0, thiab tam sim no muaj ob qho xwm txheej uas ua tau. Hauv thawj qhov, cov ntsiab lus hauv paus yuav hloov pauv, hauv qhov thib ob, nws yuav tsis hloov pauv.

Ntawm cov hauv paus hniav, sab laug subtree hnyav 1.

Rooj plaub thib ob:

Tus lej ntsuas hauv paus tsis tau hloov pauv vim tias qhov hnyav ntawm nws sab laug subtree tseem yog 0.

Yuav suav tus lej ntsuas ntawm lub node li cas? Nws yog qhov hnyav ntawm nws sab laug subtree ntxiv rau tus lej dhau los ntawm nws niam txiv. Tus lej no yog dab tsi? Nws yog lub index counter, thiab nws thaum pib sib npaug rau 0, vim tias cov hauv paus tsis muaj niam txiv. Los ntawm qhov ntawd, txhua yam nyob ntawm seb peb puas nqis mus rau sab laug tus menyuam lossis sab xis. Yog tias peb nqis mus rau sab laug tus menyuam, tsis muaj dab tsi ntxiv rau lub txee. Yog tias peb nqis mus rau sab xis tus menyuam, peb ntxiv cov node tam sim no tus lej ntsuas.

Piv txwv li, tus lej ntsuas ntawm ib qho khoom nrog tus yuam sij 8 (tus menyuam sab xis ntawm lub hauv paus) raug suav li cas? Qhov no yog "Tus lej ntsuas hauv paus" + "qhov hnyav ntawm sab laug subtree ntawm lub node nrog tus yuam sij 8" + "1" == 3 + 2 + 1 == 6
Cov ntsuas ntawm lub ntsiab lus nrog tus yuam sij 6 yuav yog "Root Index" + 1 == 3 + 1 == 4

Yog li ntawd, kom tau txais thiab rho tawm ib qho khoom los ntawm cov ntsuas, nws siv sijhawm O(log n), vim tias yuav kom tau txais cov khoom xav tau peb yuav tsum nrhiav nws ua ntej (mus nqis los ntawm hauv paus mus rau cov khoom no).

Qhov tob

Raws li qhov hnyav, qhov tob ntawm tsob ntoo, uas yuav tsum muaj rau kev sib npaug, kuj tuaj yeem suav tau.
Yuav ua li no, qhov hnyav ntawm qhov node tam sim no yuav tsum tau muab sib npaug rau lub zog thawj zaug ntawm 2 uas loj dua lossis sib npaug rau qhov hnyav uas tau muab thiab tom qab ntawd yuav tsum tau coj tus lej binary logarithm ntawm tus lej ntawd. Qhov no yuav muab qhov tob ntawm tsob ntoo rau peb, xav tias nws sib npaug. Tsob ntoo sib npaug tom qab ntxig ib qho tshiab. Kuv yuav tsis mus rau hauv txoj kev xav ntawm yuav ua li cas kom sib npaug cov ntoo. Cov lej qhov chaw muab kev ua haujlwm sib npaug.

Qhov hnyav mus rau qhov tob hloov pauv code.

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

Cov txiaj ntsim tau los

• kev ntxig ntawm ib qho khoom tshiab tshwm sim hauv O(log n)
• rho tawm ib qho khoom los ntawm nws tus lej serial tshwm sim O(log n)
• tau txais ib qho khoom los ntawm nws tus lej serial tshwm sim hauv O(log n)

Ceev O(log n) Peb them rau txhua cov ntaub ntawv kom khaws cia rau hauv daim ntawv txheeb cais.

Kuv tsis paub tias qhov kev tsim kho zoo li no yuav pab tau qhov twg. Nws tsuas yog ib qho kev sib tw kom nkag siab ntxiv txog seb cov ntoo ua haujlwm li cas. Ua tsaug rau koj qhov kev mloog.

ua tim khawv

• Cov lej qhov chaw ntawm tsob ntoo

Qhov project muaj cov ntaub ntawv sim rau kev sim ceev. Tsob ntoo tab tom raug muab tso rau hauv. 1000000 cov ntsiab lus. Thiab qhov kev rho tawm, kev ntxig, thiab kev rov qab tau cov ntsiab lus tshwm sim. 1000000 lub sijhawm. Ntawd yog 3000000 kev ua haujlwm. Qhov tshwm sim zoo heev: ~ 8 vib nas this.

Tau qhov twg los: www.hab.com