Bishiyar binaryar fihirisa

Na ci karo da irin wannan matsala. Wajibi ne don aiwatar da kwandon ajiyar bayanai wanda ke ba da ayyuka masu zuwa:

• saka sabon kashi
• cire kashi ta lambar serial
• sami kashi ta hanyar lamba
• Ana adana bayanai a cikin tsari iri ɗaya

Ana ƙara bayanai akai-akai da cirewa, tsarin dole ne ya tabbatar da saurin aiki da sauri. Da farko na yi ƙoƙari na aiwatar da irin wannan abu ta amfani da daidaitattun kwantena daga std. Wannan hanya ba ta da kambi da nasara kuma fahimtar ta zo cewa ina buƙatar aiwatar da wani abu da kaina. Abinda kawai ya zo a zuciya shine amfani da bishiyar bincike na binary. Domin ya dace da buƙatun shigar da sauri, gogewa da adana bayanai a cikin tsari. Abin da ya rage shi ne gano yadda za a lissafta duk abubuwan da kuma sake ƙididdige fihirisar lokacin da bishiyar ta canza.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Labarin zai ƙunshi ƙarin hotuna da ka'idar fiye da lamba. Ana iya duba lambar a mahaɗin da ke ƙasa.

Weight

Don cimma wannan, bishiyar ta ɗan yi gyare-gyare, an ƙara ƙarin bayani game da nauyi kumburi. Nauyin kumburi shine adadin zuriyar wannan kumburi + 1 (nauyin kashi ɗaya).

Ayyuka don samun nauyin node:

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

    return 0;
}

Nauyin takardar daidai yake daidai da 0.

Na gaba, bari mu matsa zuwa ga wakilcin gani na misalin irin wannan itace. Baki za a nuna maɓallin kumburi a launi (ƙimar ba za a nuna ba, tun da wannan ba lallai ba ne), a ja - kullin nauyi, kore - kumburi index.

Lokacin da bishiyarmu ba ta da komai, nauyinsa ya kai 0. Bari mu ƙara tushen tushensa:

Nauyin bishiyar ya zama 1, nauyin tushen tushen ya zama 1. Nauyin tushen tushen shine nauyin bishiyar.

Bari mu ƙara wasu abubuwa kaɗan:

A duk lokacin da aka ƙara sabon kashi, muna gangarowa cikin nodes kuma mu ƙara ma'aunin nauyi na kowane kumburin da ya wuce. Lokacin da aka ƙirƙiri sabon kumburi, ana sanya masa nauyi 1. Idan kumburi tare da irin wannan maɓalli ya riga ya wanzu, to, za mu sake rubuta darajar kuma mu koma zuwa tushen, soke canje-canje a cikin ma'auni na duk nodes da muka wuce.
Idan ana cire kumburi, sa'an nan kuma mu sauka kuma mu rage ma'auni na nodes da aka wuce.

Fihirisa

Yanzu bari mu matsa zuwa yadda za a index nodes. Nodes ba sa adana fihirisar su a sarari, ana ƙididdige shi bisa nauyin nodes. Idan sun adana fihirisar su, to za a buƙaci Yã (n) lokaci don sabunta fihirisar duk nodes bayan kowane canji a cikin bishiyar.
Bari mu ci gaba zuwa wakilcin gani. Bishiyar mu ba ta da komai, bari mu ƙara kumburi na 1 zuwa gare shi:

Kullin farko yana da fihirisa 0, kuma yanzu lokuta 2 suna yiwuwa. A cikin farko, ma'aunin tushen tushen zai canza, a cikin na biyu ba zai canza ba.

A tushen, ƙananan bishiyar hagu tana da nauyin 1.

Hali na biyu:

Fihirisar tushen bai canza ba saboda nauyin bishiyar hagunsa ya kasance 0.

Ana ƙididdige fihirisar kumburi azaman nauyin nauyin bishiyar ta hagu + lambar da aka wuce daga iyaye. Menene wannan lambar?, Wannan ita ce maƙalar maƙasudin, da farko daidai yake da 0, saboda tushen ba shi da iyaye. Sa'an nan duk ya dogara da inda muka gangara zuwa hagu yaro ko dama. Idan zuwa hagu, to, ba a ƙara kome ba a cikin ma'auni. Idan muka ƙara fihirisar kumburin yanzu zuwa dama.

Alal misali, yadda ake ƙididdige ma'anar wani abu mai maɓalli 8 (ɗan dama na tushen). Wannan shine "Tsarin Tushen" + "nauyin ƙananan bishiyar hagu tare da maɓalli 8" + "1" == 3 + 2 + 1 == 6
Fihirisar sinadari mai maɓalli 6 zai zama "Tsarin Tushen" + 1 == 3 + 1 == 4

Saboda haka, yana ɗaukar lokaci don samun da share wani kashi ta fihirisa O (log n), domin don samun abin da ake so dole ne mu fara nemo shi (sauka daga tushen zuwa wannan element).

Zurfin

Dangane da nauyin nauyi, zaku iya lissafin zurfin bishiyar. Wajibi ne don daidaitawa.
Don yin wannan, dole ne a zagaye nauyin node na yanzu zuwa lambar farko zuwa ikon 2 wanda ya fi girma ko daidai da nauyin da aka ba da kuma ɗaukar logarithm na binary daga gare ta. Wannan zai ba mu zurfin bishiyar, muna tsammanin yana da daidaito. Itacen yana daidaitawa bayan shigar da sabon abu. Ba zan ba da ka'idar yadda ake daidaita bishiyoyi ba. Lambobin tushen suna ba da aikin daidaitawa.

Lambar don canza nauyi zuwa zurfin.

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

Sakamakon

• shigar da wani sabon abu yana faruwa a ciki O (log n)
• share wani kashi ta serial number yana faruwa a ciki O (log n)
• samun kashi ta lambar serial yana faruwa a ciki O (log n)

Gudu O (log n) Muna biya don gaskiyar cewa an adana duk bayanan a cikin tsari mai tsari.

Ban san inda irin wannan tsarin zai iya zama da amfani ba. Kawai wuyar warwarewa don sake fahimtar yadda bishiyoyi ke aiki. Na gode da kulawar ku.

nassoshi

• Lambar tushen itace

Aikin ya ƙunshi bayanan gwaji don duba saurin aiki. Itacen yana cikawa 1000000 abubuwa. Kuma akwai sharewa, sakawa da dawo da abubuwa a jere 1000000 sau ɗaya. Wato 3000000 ayyuka. Sakamakon ya zama mai kyau ~ 8 seconds.

source: www.habr.com