Indekseeritav binaarne puu

Mul on selline ülesanne. On vajalik teostada andmete salvestamise konteiner, mis tagab järgmise funktsionaalsuse:

• lisada uus element
• kustutada element järjestiku numbri alusel
• saada element järjestiku numbri alusel
• andmed on salvestatud sorteeritud kujul

Andmeid lisatakse ja kustutatakse pidevalt, struktuur peab tagama kiire töö kiirus. Alguses proovisin sellist asja teostada, kasutades standardseid konteinerid std. See tee ei olnud edukas ja mõistsin, et pean midagi ise välja mõtlema. Ainus idee, mis pähe tuli, oli kasutada otsingubinaarset puud. Kuna see vastab kiirete lisamise, kustutamise ja andmete sorteeritud kujul säilitamise nõudmistele. Alles jäi välja mõelda, kuidas kõik elemendid indekseerida ja indeksid ümber arvutada, kui puu muutub.

struct node_s {    
    data_t data;

    uint64_t weight; // sõlme kaal

    node_t *left;
    node_t *right;

    node_t *parent;
};

Artiklis on rohkem pilte ja teooriat kui koodi. Koodi saab vaadata allpool olevast lingist.

Kaal

Selleks puu veidi muudetud, lisatud täiendav teave kaalu sõlme. Sõlme kaal on antud sõlme järglaste arv + 1 (ühe elemendi kaal).

Sõlme kaalu saamise funktsioon:

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

    return 0;
}

Lehe puhul on tema kaal vastavalt 0.

Siis liigume visuaalse esitlemise juurde selle puu näite osas. Mustas värv näitab sõlme võtit (väärtust ei näidata, kuna selleks pole vajadust), punane — sõlme kaal, roheline — sõlme indeks.

Kui puu on meil tühi, siis on selle kaal 0. Lisame sinna juureelementi:

Puud kaal tõuseb 1, juureelemendi kaal on 1. Juureelemendi kaal on puu kaal.

Lisame veel mõned elemendid:

Igal lisamisel liigume sõlmedes alla ja suurendame iga möödunud sõlme kaalu arvestust. Uue sõlme loomisel määratakse talle kaal 1. Kui sõlm sellise võtmega juba eksisteerib, siis kirjutame väärtuse üle ja läheme tagasi juure üles tühistades kaalu muutused kõigis sõlmedes, mille me läbisime.
Kui sõlm kustutatakse, siis liigume alla ja dekrementeerime möödunud sõlmede kaalu.

Indeksid

Nüüd liigume edasi, kuidas indekseerida sõlmi. Sõlmed ei hoia oma indeksi, see arvutatakse sõlmede kaalude põhjal. Kui nad hoiaksid oma indeksi, oleks vajalik O(n) aega kõigi sõlmede indeksite uuendamiseks pärast puu iga muutmist.
Liigume visuaalse esitlemise juurde. Meie puu on tühi, lisame sinna esimese sõlme:

Esimesel sõlmel on indeks 0, ning nüüd on kaks võimalust. Esimesel juhul muutub juure elemendi indeks, teisel juhul ei muutu.

Juurel on vasak alampuu kaalu 1.

Teine juhtum:

Juure indeks ei muutunud, kuna tema vasaku alampuu kaal jäi 0-ks.

Kuidas arvutatakse sõlme indeks, on see tema vasaku alampuu kaal + erinevate arvu, mis edastatakse vanematelt. Mis number see on? See on indeksite loendaja, algselt on see 0, kuna juurel ei ole vanemat. Edasi sõltub kõik sellest, kuhu me läheme, kas vasakule lapsele või paremale. Kui vasakule, siis loendajale ei lisata midagi. Kui paremale, siis lisame jooksva sõlme indeksi.

Näiteks, kuidas arvutatakse elemendi indeks, millel on võti 8 (juure parem laps). See on "Juure indeks" + "sõlme kaalu 8 vasaku alampuu" + "1" == 3 + 2 + 1 == 6
Elemendi, millel on võti 6, indeks on "Juure indeks" + 1 == 3 + 1 == 4

Seega, et saada, eemaldada element indeksi järgi on vajalik aeg O(log n), kuna soovitud elemendi saamiseks peame esmalt selle leidma (minema juurest kuni sellele elemendile).

Sügavus

Samaaegselt saab ka puu sügavust arvutada kaalu põhjal. Vajalik tasakaalu saavutamiseks.
Selleks tuleb joonistada praeguse sõlme kaal kõige väiksema 2 astme arvuni, mis on suurem või võrdne antud kaaluga, ja võtta sellest binaarlogaritm. Nii saame puu sügavuse, tingimusel et see on tasakaalus. Puu tasakaalustatakse pärast uue elemendi sisestamist. Teooriat puude tasakaalustamise kohta ma siin ei puuduta. Algkoodis on esitatud tasakaalustamise funktsioon.

Kood kaalu viimiseks sügavusse.

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

Summary

• Uue elemendi sisestamine toimub O(log n)
• Elemendi eemaldamine järjestusnumbri alusel toimub O(log n)
• Elemendi saamine järjestusnumbri alusel toimub O(log n)

Kiirus O(log n) me maksame selle eest, et kõik andmed on lõikesorteeritud.

Ma ei tea, kus selline struktuur kasulik võib olla. Lihtsalt ülesanne, et veel kord aru saada, kuidas puud töötavad. Aitäh tähelepanu eest.

Viidatud lingid

• Puu lähtekood

Projekt sisaldab testandmeid töö kiirus kontrollimiseks. Puu täidetakse 1000000 elementidega. Ja toimub elementide järjestikune eemaldamine, sisestamine ja hankimine 1000000 korda. See tähendab 3000000 operatsioone. Tulemuseks oli täiesti korralik ~ 8 sekundit.

Allikas: habr.com