Indexatutako zuhaitz bitarra

Honako arazo mota hau topatu nuen. Datuak biltegiratzeko edukiontzi bat inplementatzea beharrezkoa da funtzionalitate hauek eskaintzen dituena:

• elementu berria txertatu
• kendu elementua serie-zenbakiaren arabera
• lortu elementua zenbaki ordinalaren bidez
• datuak modu ordenatuan gordetzen dira

Datuak etengabe gehitzen eta kentzen ari dira, egiturak funtzionamendu-abiadura azkarra bermatu behar du. Hasieran horrelako gauza bat ezartzen saiatu nintzen edukiontzi estandarrak erabiliz orduak. Bide hau ez zen arrakastaz koroatu eta zerbait inplementatu behar nuela ulertu nuen. Burura etorri zitzaidan gauza bakarra bilaketa-zuhaitz bitar bat erabiltzea izan zen. Datuak modu ordenatuan sartzeko, ezabatzeko eta gordetzeko eskakizuna betetzen duelako. Elementu guztiak nola indexatu eta zuhaitza aldatzen denean indizeak berriro kalkulatzea besterik ez da geratzen.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Artikuluak kodea baino irudi eta teoria gehiago izango ditu. Kodea beheko estekan ikus daiteke.

pisua

Hori lortzeko, zuhaitzak aldaketa txiki bat jasan zuen, eta horri buruzko informazio gehigarria gehitu zen pisua nodoa. Nodoaren pisua da nodo honen ondorengo kopurua + 1 (elementu bakar baten pisua).

Nodoaren pisua lortzeko funtzioa:

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

    return 0;
}

Xaflaren pisua berdina da 0.

Jarraian, joan gaitezen halako zuhaitz baten adibide baten irudikapen bisual batera. beltza nodoaren gakoa kolorez erakutsiko da (balioa ez da erakutsiko, hau ez baita beharrezkoa), gorria - korapiloaren pisua, berdea - nodo indizea.

Gure zuhaitza hutsik dagoenean, bere pisua 0 da. Gehi diezaiogun erro-elementu bat:

Zuhaitzaren pisua 1 bihurtzen da, erro-elementuaren pisua 1. Erro-elementuaren pisua zuhaitzaren pisua da.

Gehi ditzagun elementu batzuk gehiago:

Elementu berri bat gehitzen den bakoitzean, nodoetatik jaitsi eta gainditutako nodo bakoitzaren pisu-kontagailua handitzen dugu. Nodo berri bat sortzen denean, pisu bat esleitzen zaio 1. Gako hori duen nodo bat existitzen bada, orduan balioa gainidatziko dugu eta errora itzuliko gara, gainditu ditugun nodo guztien pisuen aldaketak bertan behera utziz.
Nodo bat kentzen ari bada, orduan behera egingo dugu eta gainditutako nodoen pisuak gutxitzen ditugu.

Indizeak

Orain joan gaitezen nodoak nola indexatu. Nodoek ez dute beren indizea esplizituki gordetzen, nodoen pisuaren arabera kalkulatzen da. Euren indizea gordeko balute, beharrezkoa izango litzateke O (n) zuhaitzaren aldaketa bakoitzaren ondoren nodo guztien indizeak eguneratzeko denbora.
Goazen irudikapen bisual batera. Gure zuhaitza hutsik dago, gehitu diezaiogun 1. nodoa:

Lehenengo nodoak indize bat du 0, eta orain 2 kasu posible dira. Lehenengoan, erro-elementuaren indizea aldatuko da, bigarrenean ez da aldatuko.

Erroan, ezkerreko azpizuhaitzak 1 pisatzen du.

Bigarren kasua:

Erroaren indizea ez da aldatu bere ezkerreko azpizuhaitzaren pisua 0 izaten jarraitzen duelako.

Nodo baten indizea bere ezkerreko azpizuhaitzaren pisua + gurasotik pasatu den zenbakia bezala kalkulatzen da. Zein da zenbaki hori?, Hau indize-kontagailua da, hasieran berdina da 0, zeren erroak ez du gurasorik. Orduan dena da ezkerreko haurra edo eskuinera nora jaisten garen araberakoa. Ezkerrean bada, orduan ez da ezer gehitzen kontagailuan. Uneko nodoaren indizea eskuinekoari gehitzen badiogu.

Adibidez, 8 gakoa duen elementu baten indizea (erroaren eskuineko seme-alaba) nola kalkulatzen den. Hau da "Root Indizea" + "8 gakoarekin nodoaren ezkerreko azpizuhaitzaren pisua" + "1" == 3 + 2 + 1 == 6
6 gakoa duen elementuaren indizea "Root Index" + 1 == 3 + 1 == izango da 4

Horren arabera, denbora behar da elementu bat indizeka lortzeko eta ezabatzeko O (erregistroa n), nahi den elementua lortzeko lehenik aurkitu behar dugulako (errotik elementu honetara jaitsi).

sakonera

Pisuaren arabera, zuhaitzaren sakonera ere kalkula dezakezu. Beharrezkoa da orekatzeko.
Horretarako, uneko nodoaren pisua 2-ren potentziara biribildu behar da emandako pisua baino handiagoa edo berdina den eta bertatik logaritmo bitarra hartu. Honek zuhaitzaren sakonera emango digu, orekatua dela suposatuz. Zuhaitza orekatu egiten da elementu berri bat sartu ondoren. Ez dut zuhaitzak orekatzeko moduari buruzko teoriarik emango. Iturburu-kodeek oreka-funtzioa eskaintzen dute.

Pisua sakonera bihurtzeko kodea.

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

Emaitzak

• urtean elementu berri bat txertatzea gertatzen da O (erregistroa n)
• elementu bat serie-zenbakiaren bidez ezabatzea urtean gertatzen da O (erregistroa n)
• serie-zenbakiaren bidez elementu bat lortzea urtean gertatzen da O (erregistroa n)

Abiadura O (erregistroa n) Datu guztiak ordenatuta gordeta egoteagatik ordaintzen dugu.

Ez dakit non izan daitekeen baliagarria horrelako egitura bat. Zuhaitzek nola funtzionatzen duten berriro ulertzeko puzzle bat besterik ez. Eskerrik asko zure arretagatik.

Erreferentziak

• Zuhaitz iturburu-kodea

Proiektuak proba-datuak ditu funtzionamendu-abiadura egiaztatzeko. Zuhaitza betetzen ari da 1000000 elementuak. Eta elementuak ezabatzea, txertatzea eta berreskuratzea sekuentziala dago 1000000 behin. Hori da 3000000 eragiketak. Emaitza nahiko ona izan da ~ 8 segundo.

Iturria: www.habr.com