Mtengo wa binary wolozera

Ndinakumana ndi vuto ili. Ndikofunikira kukhazikitsa chidebe chosungira deta chomwe chimapereka magwiridwe antchito awa:

• lowetsani chinthu chatsopano
• chotsani chinthu ndi serial number
• pezani chinthu ndi nambala ya ordinal
• deta imasungidwa mu mawonekedwe osanjidwa

Deta ikuwonjezeredwa ndikuchotsedwa nthawi zonse, kapangidwe kake kayenera kuonetsetsa kuti ntchitoyo ikuyenda mwachangu. Poyamba ndidayesa kugwiritsa ntchito izi pogwiritsa ntchito zida zokhazikika kuchokera std. Njira iyi sinakhale ndi chipambano ndipo kumvetsetsa kudabwera kuti ndiyenera kuchita china chake ndekha. Chinthu chokha chomwe chinabwera m'maganizo chinali kugwiritsa ntchito mtengo wofufuzira wa binary. Chifukwa chimakwaniritsa zofunikira za kuyika mwachangu, kufufutidwa ndi kusungidwa kwa data mu mawonekedwe osanjidwa. Chotsalira ndikulingalira momwe mungalondolere zinthu zonse ndikuwerengeranso ma indices pamene mtengo ukusintha.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Nkhaniyi idzakhala ndi zithunzi zambiri ndi malingaliro kuposa ma code. Code ikhoza kuwonedwa pa ulalo womwe uli pansipa.

Kulemera

Kuti akwaniritse izi, mtengowo unasinthidwa pang'ono, zina zowonjezera zinawonjezeredwa kulemera mfundo. Kulemera kwa node ndi chiwerengero cha mbadwa za node iyi + 1 (kulemera kwa chinthu chimodzi).

Ntchito yopezera kulemera kwa node:

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

    return 0;
}

Kulemera kwa pepala kumafanana ndi 0.

Chotsatira, tiyeni tipitirire ku chithunzi chowonekera cha chitsanzo cha mtengo woterowo. Wakuda kiyi ya node idzawonetsedwa mumtundu (mtengo wake sudzawonetsedwa, chifukwa izi sizofunikira), wofiira - kulemera kwa thupi, zobiriwira - index ya node.

Mtengo wathu ukakhala wopanda kanthu, kulemera kwake ndi 0. Tiyeni tiwonjezepo mizu yake:

Kulemera kwa mtengo kumakhala 1, kulemera kwa gawo la mizu kumakhala 1. Kulemera kwa chinthu cha mizu ndi kulemera kwa mtengo.

Tiyeni tiwonjezere zina zingapo:

Nthawi iliyonse chinthu chatsopano chiwonjezedwa, timatsika pansi ndikuwonjezera kulemera kwa mfundo iliyonse yomwe yadutsa. Node yatsopano ikapangidwa, kulemera kumaperekedwa kwa iyo 1. Ngati mfundo yokhala ndi fungulo yotere ilipo kale, ndiye kuti tidzalemba mtengowo ndikubwerera ku muzu, kuletsa kusintha kwa zolemera za node zonse zomwe tadutsa.
Ngati node ikuchotsedwa, ndiye timatsika ndikuchepetsa zolemera za node zomwe zadutsa.

Zisonyezero

Tsopano tiyeni tipitirire ku momwe tingasonyezere mfundo. Node sizimasunga momveka bwino index yawo, imawerengedwa motengera kulemera kwa node. Ngati asunga index yawo, ndiye kuti ikufunika O (n) nthawi yosinthira ma index onse amtundu uliwonse pakasintha pamtengo.
Tiyeni tipitirire ku chiwonetsero chazithunzi. Mtengo wathu ulibe kanthu, tiyeni tiwonjezeko mfundo yoyamba:

Node yoyamba ili ndi index 0, ndipo tsopano milandu 2 ndi yotheka. Choyamba, index ya root element idzasintha, chachiwiri sichidzasintha.

Pamizu, mtengo wakumanzere umalemera 1.

Mlandu wachiwiri:

Mndandanda wa muzu sunasinthe chifukwa kulemera kwa mtengo wake wakumanzere kunakhala 0.

Mlozera wa node umawerengedwa ngati kulemera kwa mtengo wake wakumanzere + nambala yomwe yadutsa kuchokera kwa kholo. Nambala iyi ndi chiyani?, Iyi ndiye kauntala, poyambirira imafanana ndi 0, chifukwa muzu ulibe kholo. Ndiye zonse zimatengera komwe timapita kumanzere kapena kumanja. Ngati kumanzere, ndiye kuti palibe chomwe chimawonjezeredwa ku counter. Ngati tiwonjezera index ya node yamakono ku yoyenera.

Mwachitsanzo, momwe index ya chinthu chokhala ndi kiyi 8 (mwana woyenera wa muzu) amawerengedwera. Ichi ndi "Root Index" + "kulemera kwa subtree yamanzere ya node ndi key 8" + "1" == 3 + 2 + 1 == 6
Mndandanda wa chinthu chomwe chili ndi kiyi 6 chidzakhala "Root Index" + 1 == 3 + 1 == 4

Chifukwa chake, zimatenga nthawi kuti mupeze ndikuchotsa chinthu ndi index O (logi n), chifukwa kuti tipeze chinthu chomwe tikufuna tiyenera choyamba kuchipeza (kutsika kuchokera muzu kupita ku chinthu ichi).

Kuzama

Malingana ndi kulemera kwake, mukhoza kuwerengeranso kuya kwa mtengo. Zofunikira pakulinganiza.
Kuti muchite izi, kulemera kwa node yamakono kuyenera kuzunguliridwa mpaka nambala yoyamba ku mphamvu ya 2 yomwe ili yaikulu kapena yofanana ndi kulemera kwake ndikutenga logarithm ya binary kuchokera pamenepo. Izi zidzatipatsa kuya kwa mtengowo, poganiza kuti ndi wokwanira. Mtengowo umakhala wokwanira pambuyo poika chinthu chatsopano. Sindipereka lingaliro la momwe mungalinganizire mitengo. Zizindikiro zoyambira zimapereka ntchito yofananira.

Code yosinthira kulemera kukhala kuya.

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

Zotsatira

• kulowetsedwa kwa chinthu chatsopano kumachitika mu O (logi n)
• Kuchotsa chinthu ndi serial number kumachitika O (logi n)
• kupeza chinthu ndi serial number kumachitika O (logi n)

Liwiro O (logi n) Timalipira chifukwa chakuti deta yonse imasungidwa mu mawonekedwe osanjidwa.

Sindikudziwa komwe kapangidwe kotere kangakhale kothandiza. Chongodabwitsa kuti mumvetsetse momwe mitengo imagwirira ntchito. Zikomo chifukwa chakumvetsera.

powatsimikizira

• Tree source kodi

Pulojekitiyi ili ndi deta yoyesera kuti muwone kuthamanga kwa ntchito. Mtengo ukudzaza 1000000 zinthu. Ndipo pali kufufutidwa motsatizana, kuyika ndi kubwezeretsanso zinthu 1000000 kamodzi. Ndiko kuti 3000000 ntchito. Zotsatira zake zidakhala zabwino ~ 8 masekondi.

Source: www.habr.com