Indekseeritav binaarpuu

Tekkis mulle järgmine ülesanne. On vajalik luua andmete salvestus konteiner, mis tagab järgmised funktsioonid:

• uus element sisestada
• eemaldada element järjekorranumbriga
• saada element järjekorranumbriga
• andmed hoitakse sorteeritud kujul

Andmed lisatakse ja eemaldatakse pidevalt, struktuur peab tagama kiire töö kiirus. Esiteks proovisin midagi sellist rakendada, kasutades standardseid konteinerite mooduleid std. See tee ei viinud edu, ja mul tekkis arusaam, et tuleb midagi ise rakendada. Ainus, mis mõtteis oli, oli kasutada binaarset otsingupuud. Kuna see vastab kiire sisestamise, eemaldamise ja andmete hoiustamise sorteeritud kujul nõudmistele. Jäigi ainult välja mõelda, kuidas indekseerida kõik elemendid ja ümber arvutada indeksid, 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 allolevalt lingilt.

Kaal

Selleks läbiviidud puu väikesele modifikatsioonile, lisati täiendav teave kaalu kohta sõlm. Sõlme kaal on selle sõlme järglaste arv + 1 (üksiku 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 kaal vastavalt 0.

Liigume edasi, et visuaalselt tutvuda sellise puu näitega. Must värv näitab sõlme võtme (väärtust ei näidata, kuna sellega pole mingit vajadust), punane – sõlme kaal, roheline – sõlme indeks.

Kui puu on tühi, on selle kaal 0. Lisame sellesse juursõlme:

Puud on kaalu 1, juursõlme kaal on 1. Juursõlme kaal on puu kaal.

Lisame veel mõned elemendid:

Iga kord, kui lisame uue elemendi, laskume allapoole sõlmedes ja suurendame iga läbitud sõlme kaalu. Uuele sõlmele määratakse kaal 1. Kui sõlm sellise võtmega juba eksisteerib, siis kirjutame väärtuse üle ja liigume tagasi juure poole, tühistades kõigi läbitud sõlmede kaalu muutmised.
Kui sõlme kustutatakse, liigume alla ja vähendame läbitud sõlmede kaalu.

Indeksid

Nüüd liigume edasi selle juurde, kuidas indekseerida sõlmed. Sõlmed ei hoia oma indeksi, see arvutatakse sõlmede kaalu põhjal. Kui nad hoidsid oma indeksi, siis oleks vaja O(n) aega, et värskendada kõigi sõlmede indekseid pärast iga puu muutust.
Liigume visuaalse esituse juurde. Meie puu on tühi, lisame sellesse 1. sõlme:

Esimese sõlme indeks on 0, ja nüüd on võimalikud 2 juhtumit. Esimeses muutub juure elemendi indeks, teises ei muutu.

Juurel kaal vasakul alampuul on 1.

Teine juhtum:

Juure indeksi ei muudetud, kuna tema vasaku alampuu kaal jäi 0-ks.

Kuidas arvutatakse sõlme indeks, see on tema vasaku alampuu kaal + number, mis on edasi antud vanemalt. Mis see number on? See on indeksise suvand, algselt on see 0, kuna juurel ei ole vanemat. Edasi sõltub kõik sellest, kuhu me laskume - vasakule lapsele või paremale. Kui vasakule, siis indeksile ei lisata midagi. Kui paremale, siis lisame praeguse sõlme indeksi.

Näiteks, kuidas arvutatakse element, millel on võtme number 8 (juure parempoolne laps). See on "Juure indeks" + "vasaku alampuu kaal sõlmega, millel on võtme number 8" + "1" == 3 + 2 + 1 == 6
Elemendi võtme 6 indeks on „Juure indeks” + 1 == 3 + 1 == 4

Seega vajab elemendi indeksi põhjal saamine ja eemaldamine aega O(log n), kuna et saada vajalik element, peame selle esmalt leidma (pärandama juurest sellele elemendile).

Sügavus

Kaalust lähtudes saab samuti arvutada puu sügavuse, mis on vajalik tasakaalustamiseks.
Sel eesmärgil tuleb praeguse sõlme kaal ümardada lähima 2 astme numbrini, mis on suurem või võrdne antud kaaluga, ja selle põhjal võtta binaarlogarütm. Nii saame puu sügavuse, eeldusel et see on tasakaalus. Puu tasakaalustatakse uue elemendi lisamise järel. Teooriat sellest, kuidas puid tasakaalustada, ma ei too. Allika koodides on esitatud tasakaalustamise funktsioon.

Koodi kaalude viimist sügavusesse.

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

Kokkuvõte

• uue elemendi lisamine toimub O(log n)
• elemendi eemaldamine järjestusnumbriga toimub O(log n)
• elemendi saamine järjestusnumbriga toimub O(log n)

Kiirus O(log n) maksame selle eest, et kõik andmed on salvestatud sorteeritud kujul.

Kus see struktuur võiks olla kasulik — ma ei tea. Lihtsalt ülesanne, et veel kord aru saada, kuidas puud töötavad. Aitäh tähelepanu eest.

Lingid

• Algne puukood

Projekt sisaldab testandmeid töökiirusest kontrollimiseks. Puu täidetakse 1000000 elementidega. Ja toimub järjestikune kustutamine, sisestamine ja elementide saamine 1000000 kord. See tähendab 3000000 operatsioonide arvu. Tulemuseks osutus üsna hea ~ 8 sekundit.

Allikas: habr.com