ProHoster > Blog > Stjórnsýsla > Verðtryggt tvíundartré

Verðtryggt tvíundartré

Verðtryggt tvíundartré

Ég rakst á eftirfarandi tegund af vandamálum. Nauðsynlegt er að útfæra gagnageymsluílát sem veitir eftirfarandi virkni:

  • setja inn nýjan þátt
  • fjarlægja frumefni eftir raðnúmeri
  • fá stak með raðtölu
  • gögn eru geymd í flokkuðu formi

Gögn eru stöðugt bætt við og fjarlægð, uppbyggingin verður að tryggja hraðan vinnsluhraða. Í fyrstu reyndi ég að útfæra slíkt með því að nota staðlaða ílát frá klukkustundir. Þessi leið var ekki krýnd árangri og sá skilningur kom að ég þyrfti að útfæra eitthvað sjálfur. Það eina sem kom upp í hugann var að nota tvíleitartré. Vegna þess að það uppfyllir kröfuna um hraða innsetningu, eyðingu og geymslu gagna í flokkuðu formi. Það eina sem er eftir er að finna út hvernig á að skrá alla þættina og endurreikna vísitölurnar þegar tréð breytist.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Greinin mun innihalda fleiri myndir og fræði en kóða. Kóðann má skoða á hlekknum hér að neðan.

Þyngd

Til að ná þessu fram fór tréð í smá breytingu, viðbótarupplýsingum var bætt við um þyngd hnút. Hnútaþyngdin er fjölda afkomenda þessa hnúts + 1 (þyngd eins frumefnis).

Virkni til að fá hnútþyngd:

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

    return 0;
}

Þyngd blaðsins er samsvarandi jöfn 0.

Næst skulum við fara í sjónræna framsetningu á dæmi um slíkt tré. Svartur hnútalykillinn verður sýndur í lit (gildið verður ekki sýnt, þar sem þetta er ekki nauðsynlegt), rauður - hnútaþyngd, grænn — hnútavísitala.

Þegar tréð okkar er tómt er þyngd þess 0. Við skulum bæta rótarefni við það:

Verðtryggt tvíundartré

Þyngd trésins verður 1, þyngd rótarþáttarins verður 1. Þyngd rótarþáttarins er þyngd trésins.

Við skulum bæta við nokkrum þáttum í viðbót:

Verðtryggt tvíundartré
Verðtryggt tvíundartré
Verðtryggt tvíundartré
Verðtryggt tvíundartré

Í hvert sinn sem nýr þáttur er bætt við förum við niður hnúðana og hækkum þyngdarteljarann ​​fyrir hvern hnút sem fer framhjá. Þegar nýr hnút er búinn til er honum úthlutað þyngd 1. Ef hnútur með slíkan lykil er þegar til, þá munum við skrifa yfir gildið og fara aftur upp í rótina og hætta við breytingar á þyngd allra hnúta sem við höfum farið framhjá.
Ef verið er að fjarlægja hnút, þá förum við niður og lækkum þyngd þeirra hnúta sem hafa farið framhjá.

Vísitölur

Nú skulum við halda áfram að því hvernig á að skrá hnúta. Hnútar geyma ekki beinlínis vísitöluna sína, hún er reiknuð út frá þyngd hnútanna. Ef þeir geymdu vísitöluna sína, þá væri þess krafist O (n) tími til að uppfæra vísitölur allra hnúta eftir hverja breytingu á trénu.
Við skulum halda áfram í sjónræna framsetningu. Tréð okkar er tómt, við skulum bæta 1. hnút við það:

Verðtryggt tvíundartré

Fyrsti hnúturinn hefur vísitölu 0, og nú eru 2 tilvik möguleg. Í því fyrsta breytist vísitalan á rótarhlutanum, í þeirri seinni breytist hún ekki.

Verðtryggt tvíundartré

Í rótinni vegur vinstra undirtréð 1.

Annað mál:

Verðtryggt tvíundartré

Vísitala rótarinnar breyttist ekki vegna þess að þyngd vinstri undirtrés hennar hélst 0.

Vísitala hnúts er reiknuð út sem þyngd vinstri undirtrés hans + talan sem send er frá foreldri. Hver er þessi tala?, Þetta er vísitöluteljarinn, upphaflega er hann jöfn 0, vegna þess rótin á ekkert foreldri. Svo fer þetta allt eftir því hvar við förum niður á vinstra barnið eða það hægri. Ef til vinstri, þá er engu bætt við teljarann. Ef við bætum vísitölu núverandi hnút við þann rétta.

Verðtryggt tvíundartré

Til dæmis hvernig vísitala staks með lykil 8 (hægra barn rótarinnar) er reiknað út. Þetta er "Root Index" + "þyngd vinstri undirtrés hnúts með lykli 8" + "1" == 3 + 2 + 1 == 6
Vísitala frumefnisins með lykli 6 verður "Root Index" + 1 == 3 + 1 == 4

Í samræmi við það tekur það tíma að fá og eyða þætti eftir vísitölu O (log n), vegna þess að til þess að fá viðkomandi frumefni verðum við fyrst að finna hann (fara niður frá rótinni í þennan þátt).

Dýpt

Byggt á þyngdinni er einnig hægt að reikna út dýpt trésins. Nauðsynlegt fyrir jafnvægi.
Til að gera þetta þarf að námunda þyngd núverandi hnúts að fyrstu tölu í veldi 2 sem er stærra en eða jafnt uppgefnu vægi og taka tvíundarlogaritminn af henni. Þetta mun gefa okkur dýpt trésins, að því gefnu að það sé jafnvægi. Tréð er í jafnvægi eftir að nýr þáttur er settur inn. Ég mun ekki gefa kenningu um hvernig á að halda jafnvægi á trjám. Frumkóðarnir veita jafnvægisaðgerð.

Kóði til að breyta þyngd í dýpt.

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

Niðurstöður

  • innsetning nýs þáttar á sér stað í O (log n)
  • að eyða einingu eftir raðnúmeri á sér stað í O (log n)
  • að fá frumefni með raðnúmeri á sér stað í O (log n)

Hraði O (log n) Við borgum fyrir að öll gögn séu geymd í flokkuðu formi.

Ég veit ekki hvar slík uppbygging gæti verið gagnleg. Bara púsluspil til að skilja enn og aftur hvernig tré virka. Takk fyrir athyglina.

tilvísanir

Verkefnið inniheldur prófunargögn til að athuga hraða aðgerðarinnar. Tréð er að fyllast 1000000 þættir. Og það er raðbundin eyðing, innsetning og endurheimt þátta 1000000 einu sinni. Það er 3000000 aðgerðir. Niðurstaðan reyndist vera nokkuð góð ~ 8 sekúndur.

Heimild: www.habr.com

Bæta við athugasemd