Arburu binariu indexatu

Aghju trovu u seguente tipu di prublema. Hè necessariu implementà un containeru di almacenamiento di dati chì furnisce e seguenti funziunalità:

• inserisci un novu elementu
• caccià l'elementu da u numeru di serie
• uttene l'elementu per u numeru ordinale
• i dati sò almacenati in forma ordinata

I dati sò constantemente aghjuntu è sguassati, a struttura deve assicurà a veloce di operazione veloce. Prima aghju pruvatu à implementà una tale cosa cù cuntenituri standard da ore. Questa strada ùn era micca coronata di successu è hè vinutu a cunniscenza chì avia bisognu di implementà qualcosa per mè stessu. L'unicu chì hè vinutu in mente era di utilizà un arbulu di ricerca binariu. Perchè risponde à l'esigenza di inserimentu veloce, eliminazione è almacenamiento di dati in forma ordinata. Tuttu ciò chì resta hè di calculà cumu indexà tutti l'elementi è recalculate l'indici quandu l'arbulu cambia.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

L'articulu cuntene più ritratti è teoria chè codice. U codice pò esse vistu à u ligame sottu.

Pesu

Per ottene questu, l'arbulu hà subitu una ligera mudificazione, infurmazione supplementaria hè stata aghjunta pesu nodu. U pesu di u nodu hè numeru di discendenti di stu node + 1 (pesu di un elementu unicu).

Funzione per ottene u pesu di u nodu:

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

    return 0;
}

U pesu di u fogliu hè currispundenu uguali à 0.

Dopu, andemu à una rapprisintazioni visuale di un esempiu di un tali arburu. Neru a chjave di u node serà mostrata in culore (u valore ùn serà micca mostratu, postu chì questu ùn hè micca necessariu), russu - pesu di nodu, verde - indice de node.

Quandu u nostru arbulu hè viotu, u so pesu hè 0. Aghjunghjemu un elementu radicali:

U pesu di l'arbulu diventa 1, u pesu di l'elementu radicali diventa 1. U pesu di l'elementu radicali hè u pesu di l'arbulu.

Aghjunghjemu uni pochi di elementi più:

Ogni volta chì un novu elementu hè aghjuntu, andemu in i nodi è cresce u contatore di pesu di ogni nodu passatu. Quandu un novu node hè creatu, un pesu hè assignatu 1. Se un node cù una tale chjave esiste digià, allora soprascrivite u valore è vulteremu à a radica, annullendu i cambiamenti in i pesi di tutti i nodi chì avemu passatu.
Se un node hè sguassatu, allora andemu è diminuite i pesi di i nodi passati.

Indici

Avà andemu à cumu indicà i nodi. I nodi ùn anu micca esplicitu u so indice, hè calculatu basatu annantu à u pesu di i nodi. S'elli anu guardatu u so indexu, allora serà necessariu O (n) tempu per aghjurnà l'indici di tutti i nodi dopu ogni cambiamentu in l'arbulu.
Passemu à una rappresentazione visuale. U nostru arbre hè viotu, aghjunghjemu u 1u node:

U primu node hà un indice 0, è avà 2 casi sò pussibuli. In u primu, l'indici di l'elementu radicali cambierà, in u sicondu ùn cambia micca.

À a radica, u subtree di manca pesa 1.

Secondu casu:

L'indici di a radica ùn hà micca cambiatu perchè u pesu di u so subtree left restava 0.

L'indici di un node hè calculatu cum'è u pesu di u so subtree left + u numeru passatu da u parent. Chì ghjè stu numeru?, Questu hè u contatore d'indici, inizialmente hè uguali à 0, perchè a radica ùn hà micca parenti. Allora tuttu dipende di induve falà à u zitellu manca o u dirittu. Sè à a manca, allora nunda hè aghjuntu à u cuntatore. Se aghjunghjemu l'indici di u node attuale à u dirittu.

Per esempiu, cumu hè calculatu l'indici di un elementu cù a chjave 8 (u figliolu ghjustu di a radica). Questu hè "Root Index" + "pesu di u subtree left di u node cù a chjave 8" + "1" == 3 + 2 + 1 == 6
L'indici di l'elementu cù a chjave 6 serà "Root Index" + 1 == 3 + 1 == 4

In cunsiquenza, ci vole tempu per uttene è sguassà un elementu per indice O(log n), perchè per avè l'elementu desideratu avemu prima à truvà lu (falà da a radica à questu elementu).

Profundità

Basatu nantu à u pesu, pudete ancu calculà a prufundità di l'arbulu. Necessaria per l'equilibriu.
Per fà questu, u pesu di u node attuale deve esse arrotondatu à u primu numeru à a putenza di 2 chì hè più grande o uguale à u pesu datu è pigliate u logarithm binariu da questu. Questu ci darà a prufundità di l'arbulu, assumendu chì hè equilibratu. L'arbulu hè equilibratu dopu à inserisce un novu elementu. Ùn daraghju micca una teoria nantu à cumu equilibrà l'arburi. I codici fonte furnisce una funzione di equilibriu.

Codice per cunvertisce u pesu à a prufundità.

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

Risultati

• L'inserimentu di un novu elementu si faci in O(log n)
• a cancellazione di un elementu per u numeru di serie si faci in O(log n)
• ottene un elementu per u numeru di seriale si trova in O(log n)

Velocità O(log n) Paghemu per u fattu chì tutti i dati sò almacenati in forma ordinata.

Ùn sò micca sapè induve una tale struttura puderia esse utile. Solu un puzzle per capisce una volta di più cumu funziona l'arburi. Grazie per a vostra attenzione.

referenze

• Arbulu codice fonte

U prughjettu cuntene dati di prova per verificà a velocità di u funziunamentu. L'arburu si riempie 1000000 elementi. È ci hè una eliminazione sequenziale, inserimentu è ricuperazione di elementi 1000000 una volta. Hè 3000000 operazioni. U risultatu hè stata abbastanza bona ~ 8 seconde.

Source: www.habr.com