🥇Indexable binary tsob ntoo

Kuv tuaj hla cov teeb meem hauv qab no. Nws yog ib qho tsim nyog los siv lub thawv ntim cov ntaub ntawv uas muab cov haujlwm hauv qab no:

ntxig lub ntsiab tshiab
tshem cov khoom los ntawm serial tooj
tau cov ntsiab lus los ntawm tus lej lej
cov ntaub ntawv muab khaws cia rau hauv daim ntawv txheeb

Cov ntaub ntawv raug ntxiv thiab tshem tawm tas li, cov qauv yuav tsum ua kom muaj kev ua haujlwm ceev ceev. Thaum xub thawj kuv sim ua qhov zoo li no siv cov thawv ntim khoom los ntawm ua std. Txoj kev no tsis tau ua tiav nrog kev ua tiav thiab kev nkag siab tuaj tias kuv yuav tsum tau siv qee yam ntawm kuv tus kheej. Tib yam uas tuaj rau hauv lub siab yog siv binary tshawb nrhiav ntoo. Vim tias nws ua tau raws li qhov yuav tsum tau ua kom nrawm nrawm, tshem tawm thiab khaws cov ntaub ntawv hauv cov ntawv txheeb. Txhua yam uas tseem tshuav yog los xyuas seb yuav ua li cas txhawm rau ntsuas tag nrho cov ntsiab lus thiab rov xam cov indices thaum tsob ntoo hloov.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Cov kab lus yuav muaj ntau cov duab thiab kev xav ntau dua li code. Cov cai tuaj yeem pom ntawm qhov txuas hauv qab no.

Nyhav

Txhawm rau ua tiav qhov no, tsob ntoo tau hloov kho me ntsis, cov ntaub ntawv ntxiv tau ntxiv txog hnyav node. Qhov hnyav ntawm node yog tus naj npawb ntawm cov xeeb leej xeeb ntxwv ntawm node + 1 (qhov hnyav ntawm ib lub caij).

Function kom tau txais node hnyav:

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

    return 0;
}

Qhov hnyav ntawm daim ntawv yog sib npaug sib npaug 0.

Tom ntej no, cia peb mus rau qhov pom kev sawv cev ntawm ib qho piv txwv ntawm tsob ntoo zoo li no. Dub tus yuam sij node yuav pom hauv cov xim (tus nqi yuav tsis pom, vim qhov no tsis tsim nyog), xim liab - luj luj, ntsuab - node index.

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

Qhov hnyav ntawm tsob ntoo ua 1, qhov hnyav ntawm lub hauv paus chiv ua 1. Qhov hnyav ntawm tsob ntoo yog qhov hnyav ntawm tsob ntoo.

Cia peb ntxiv ob peb yam ntxiv:

Txhua lub sij hawm ntxiv cov khoom tshiab, peb mus rau hauv cov nodes thiab nce qhov hnyav ntawm txhua qhov dhau. Thaum tsim ib qho tshiab, qhov hnyav tau muab rau nws 1. Yog hais tias ib lub node nrog xws li ib tug tseem ceeb twb muaj lawm, ces peb yuav overwrite tus nqi thiab rov qab mus rau lub hauv paus, tshem tawm cov kev hloov nyob rau hauv lub luj ntawm tag nrho cov nodes uas peb tau dhau lawm.
Yog tias ib lub node raug tshem tawm, ces peb nqis mus thiab txo qhov hnyav ntawm cov node dhau lawm.

Indexes

Tam sim no cia peb mus rau yuav ua li cas rau index nodes. Nodes tsis qhia meej khaws lawv qhov Performance index, nws yog xam raws li qhov hnyav ntawm cov nodes. Yog tias lawv khaws lawv qhov Performance index, ces nws yuav tsum tau Nws) sij hawm hloov kho cov indexes ntawm tag nrho cov nodes tom qab txhua qhov kev hloov ntawm tsob ntoo.
Cia peb txav mus rau qhov pom kev sawv cev. Peb tsob ntoo yog npliag, cia peb ntxiv qhov thib 1 ntawm nws:

Thawj node muaj qhov ntsuas 0, thiab tam sim no 2 kis tau. Hauv thawj zaug, qhov ntsuas ntawm lub hauv paus ntsiab lus yuav hloov, hauv qhov thib ob nws yuav tsis hloov.

Hauv paus, sab laug subtree hnyav 1.

Case thib ob:

Qhov ntsuas ntawm cov hauv paus hniav tsis hloov vim qhov hnyav ntawm nws sab laug subtree tseem yog 0.

Qhov Performance index ntawm node yog xam raws li qhov hnyav ntawm nws sab laug subtree + tus lej dhau los ntawm niam txiv. Tus lej no yog dab tsi?, Qhov no yog qhov ntsuas ntsuas, pib nws yog sib npaug 0, vim cag tsis muaj niam txiv. Tom qab ntawd txhua yam nyob ntawm qhov chaw peb mus rau sab laug tus me nyuam los yog txoj cai. Yog tias sab laug, ces tsis muaj dab tsi ntxiv rau lub txee. Yog tias peb ntxiv qhov Performance index ntawm qhov tam sim no node mus rau sab xis.

Piv txwv li, yuav ua li cas qhov Performance index ntawm ib qho tseem ceeb 8 (tus me nyuam txoj cai ntawm lub hauv paus) yog xam. Qhov no yog "hauv paus Index" + "qhov hnyav ntawm sab laug subtree ntawm node nrog qhov tseem ceeb 8" + "1" == 3 + 2 + 1 == 6
Qhov Performance index ntawm lub ntsiab nrog qhov tseem ceeb 6 yuav yog "Root Index" + 1 == 3 + 1 == 4

Raws li, nws yuav siv sij hawm kom tau thiab rho tawm ib lub ntsiab lus los ntawm index O (cav n), vim hais tias nyob rau hauv thiaj li yuav tau lub yam xav tau peb yuav tsum xub nrhiav nws (mus nqis los ntawm lub hauv paus mus rau lub caij no).

Qhov tob

Raws li qhov hnyav, koj tuaj yeem xam qhov tob ntawm tsob ntoo. Tsim nyog rau kev sib npaug.
Txhawm rau ua qhov no, qhov hnyav ntawm cov node tam sim no yuav tsum tau muab sib npaug rau thawj tus lej mus rau lub zog ntawm 2 uas ntau dua lossis sib npaug ntawm qhov hnyav thiab muab lub logarithm binary los ntawm nws. Qhov no yuav ua rau peb qhov tob ntawm tsob ntoo, xav tias nws yog qhov sib npaug. Tsob ntoo yog sib npaug tom qab ntxig ib lub caij tshiab. Kuv yuav tsis muab ib txoj kev xav txog yuav ua li cas sib npaug ntoo. Cov kab lis kev cai muab qhov ua haujlwm sib npaug.

Code hloov qhov hnyav rau qhov tob.

/*
 * Возвращает первое число в степени 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 nkag ntawm lub ntsiab lus tshiab tshwm sim hauv O (cav n)
rho tawm ib lub caij los ntawm serial tooj tshwm sim nyob rau hauv O (cav n)
tau ib lub caij los ntawm serial tooj tshwm sim nyob rau hauv O (cav n)

Ceev O (cav n) Peb them nyiaj rau qhov tseeb tias tag nrho cov ntaub ntawv khaws cia hauv daim ntawv txheeb.

Kuv tsis paub qhov twg cov qauv no yuav pab tau. Tsuas yog ib qho kev sib dhos kom rov nkag siab tias tsob ntoo ua haujlwm li cas. Ua tsaug rau koj mloog.

ua tim khawv

Tsob ntoo qhov chaws

Qhov project muaj cov ntaub ntawv xeem los xyuas qhov ceev ntawm kev ua haujlwm. Tsob ntoo puv 1000000 cov ntsiab lus. Thiab muaj ib tug sequential deletion, insertion thiab retrieval ntawm lub ntsiab 1000000 ib zaug. Qhov ntawd yog 3000000 kev ua haujlwm. Cov txiaj ntsig tau ua tau zoo heev ~ 8 vib nas this.

Tau qhov twg los: www.hab.com

Indexed binary tsob ntoo

Nyhav

Indexes

Qhov tob

Cov txiaj ntsim tau los

ua tim khawv

Ntxiv ib saib Отменить ответ