🥇Mti wa binary unaoweza kuorodheshwa

Nilikutana na aina ifuatayo ya shida. Ni muhimu kutekeleza chombo cha kuhifadhi data ambacho hutoa utendaji ufuatao:

ingiza kipengele kipya
ondoa kipengele kwa nambari ya serial
pata kipengele kwa nambari ya kawaida
data huhifadhiwa katika fomu iliyopangwa

Data inaongezwa mara kwa mara na kuondolewa, muundo lazima uhakikishe kasi ya operesheni ya haraka. Mwanzoni nilijaribu kutekeleza kitu kama hicho kwa kutumia vyombo vya kawaida kutoka std. Njia hii haikuwa na taji la mafanikio na ufahamu ulikuja kwamba nilihitaji kutekeleza kitu mwenyewe. Kitu pekee kilichokuja akilini ni kutumia mti wa utaftaji wa binary. Kwa sababu inakidhi mahitaji ya kuingizwa haraka, kufuta na kuhifadhi data katika fomu iliyopangwa. Kilichobaki ni kujua jinsi ya kuorodhesha vitu vyote na kuhesabu tena fahirisi wakati mti unabadilika.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Nakala hiyo itakuwa na picha na nadharia zaidi kuliko kanuni. Nambari inaweza kutazamwa kwenye kiungo hapa chini.

Uzito

Ili kufikia hili, mti ulipata marekebisho kidogo, maelezo ya ziada yaliongezwa kuhusu uzito nodi. Uzito wa nodi ni idadi ya wazao wa nodi hii + 1 (uzito wa kipengele kimoja).

Kazi ya kupata uzito wa nodi:

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

    return 0;
}

Uzito wa karatasi ni sawa sawa na 0.

Ifuatayo, wacha tuendelee kwenye uwakilishi wa kuona wa mfano wa mti kama huo. Nyeusi ufunguo wa nodi utaonyeshwa kwa rangi (thamani haitaonyeshwa, kwani hii sio lazima), nyekundu - uzito wa fundo, kijani - index ya nodi.

Wakati mti wetu ni tupu, uzito wake ni 0. Hebu tuongeze kipengele cha mizizi kwake:

Uzito wa mti unakuwa 1, uzito wa kipengele cha mizizi inakuwa 1. Uzito wa kipengele cha mizizi ni uzito wa mti.

Hebu tuongeze vipengele vichache zaidi:

Kila wakati kipengele kipya kinaongezwa, tunashuka chini ya nodes na kuongeza counter counter ya kila node kupita. Wakati nodi mpya imeundwa, uzani hupewa 1. Ikiwa nodi iliyo na ufunguo kama huo tayari ipo, basi tutaandika juu ya thamani na kurudi kwenye mizizi, kufuta mabadiliko katika uzito wa nodi zote ambazo tumepita.
Ikiwa node inaondolewa, basi tunashuka na kupunguza uzito wa nodes zilizopitishwa.

Faharisi

Sasa hebu tuendelee kwenye jinsi ya kuashiria nodi. Nodes hazihifadhi kwa uwazi index yao, inahesabiwa kulingana na uzito wa nodes. Ikiwa walihifadhi index yao, basi ingehitajika O (n) wakati wa kusasisha faharisi za nodi zote baada ya kila mabadiliko kwenye mti.
Wacha tuendelee kwenye uwakilishi wa kuona. Mti wetu hauna kitu, wacha tuongeze nodi ya 1 kwake:

Nodi ya kwanza ina index 0, na sasa kesi 2 zinawezekana. Katika kwanza, index ya kipengele cha mizizi itabadilika, kwa pili haitabadilika.

Kwenye mzizi, mti mdogo wa kushoto una uzito 1.

Kesi ya pili:

Fahirisi ya mzizi haikubadilika kwa sababu uzani wa mti mdogo wa kushoto ulibaki 0.

Faharasa ya nodi huhesabiwa kama uzito wa mti mdogo wa kushoto + nambari iliyopitishwa kutoka kwa mzazi. Nambari hii ni nini?, Hii ni kihesabu cha faharisi, mwanzoni ni sawa na 0, kwa sababu mzizi hana mzazi. Kisha yote inategemea wapi tunashuka kwa mtoto wa kushoto au wa kulia. Ikiwa upande wa kushoto, basi hakuna chochote kinachoongezwa kwenye counter. Ikiwa tunaongeza index ya node ya sasa kwa moja sahihi.

Kwa mfano, jinsi index ya kipengele na ufunguo 8 (mtoto sahihi wa mizizi) inavyohesabiwa. Hii ni "Kielezo cha Mizizi" + "uzito wa mti mdogo wa kushoto wa nodi na ufunguo 8" + "1" == 3 + 2 + 1 == 6
Faharisi ya kitu kilicho na ufunguo 6 itakuwa "Kielelezo cha Mizizi" + 1 == 3 + 1 == 4

Ipasavyo, inachukua muda kupata na kufuta kipengee kwa index O (logi n), kwa sababu ili kupata kipengele kinachohitajika lazima kwanza tupate (kwenda chini kutoka kwenye mizizi hadi kipengele hiki).

Uthabiti

Kulingana na uzito, unaweza pia kuhesabu kina cha mti. Muhimu kwa kusawazisha.
Ili kufanya hivyo, uzito wa nodi ya sasa lazima iwe mviringo kwa nambari ya kwanza kwa nguvu ya 2 ambayo ni kubwa kuliko au sawa na uzito uliopewa na kuchukua logarithm ya binary kutoka kwake. Hii itatupa kina cha mti, ikizingatiwa kuwa ni usawa. Mti ni usawa baada ya kuingiza kipengele kipya. Sitatoa nadharia kuhusu jinsi ya kusawazisha miti. Misimbo ya chanzo hutoa kazi ya kusawazisha.

Kanuni ya kubadilisha uzito hadi kina.

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

Matokeo ya

kuingizwa kwa kipengele kipya hutokea ndani O (logi n)
kufuta kipengele kwa nambari ya serial hutokea O (logi n)
kupata kipengele kwa nambari ya serial hutokea O (logi n)

Kasi O (logi n) Tunalipa kwa ukweli kwamba data zote zimehifadhiwa katika fomu iliyopangwa.

Sijui ni wapi muundo kama huo unaweza kuwa muhimu. Kitendawili tu ili kuelewa tena jinsi miti inavyofanya kazi. Asante kwa umakini wako.

marejeo

Nambari ya chanzo cha mti

Mradi una data ya majaribio ili kuangalia kasi ya utendakazi. Mti umejaa 1000000 vipengele. Na kuna kufuta mfululizo, kuingizwa na kurejesha vipengele 1000000 mara moja. Hiyo ni 3000000 shughuli. Matokeo yake yaligeuka kuwa mazuri ~ sekunde 8.

Chanzo: mapenzi.com

Mti wa binary ulioorodheshwa

Uzito

Faharisi

Uthabiti

Matokeo ya

marejeo

Kuongeza maoni Kufuta kujibu