ProHoster > Blogi > Haldamine > Indekseeritud kahendpuu

Indekseeritud kahendpuu

Indekseeritud kahendpuu

Kohtasin järgmist tüüpi probleemi. On vaja juurutada andmesalvestuskonteiner, mis pakub järgmisi funktsioone:

  • sisestage uus element
  • eemaldage element seerianumbri järgi
  • saada element järjekorranumbri järgi
  • andmed salvestatakse sorteeritud kujul

Andmeid lisatakse ja eemaldatakse pidevalt, struktuur peab tagama kiire töökiiruse. Alguses proovisin sellist asja rakendada, kasutades standardseid konteinereid std. Edu seda teed ei krooninud ja tuli arusaam, et mul on vaja midagi ise ellu viia. Ainus, mis meelde tuli, oli kasutada binaarset otsingupuud. Kuna see vastab andmete kiire sisestamise, kustutamise ja sorteeritud kujul salvestamise nõudele. Jääb vaid välja mõelda, kuidas puu muutumisel kõiki elemente indekseerida ja indeksid ümber arvutada.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Artikkel sisaldab rohkem pilte ja teooriat kui koodi. Koodi saab vaadata allolevalt lingilt.

Kaal

Selle saavutamiseks viidi puu läbi väikese modifikatsiooni, mille kohta lisati täiendavat teavet kaal sõlm. Sõlme kaal on selle sõlme järeltulijate arv + 1 (üksiku elemendi kaal).

Funktsioon sõlme kaalu saamiseks:

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

    return 0;
}

Lehe kaal on vastavalt võrdne 0.

Järgmisena liigume sellise puu näite visuaalse esituse juurde. Must sõlme võti kuvatakse värviliselt (väärtust ei kuvata, kuna see pole vajalik), punane - sõlme kaal, roheline - sõlmede indeks.

Kui meie puu on tühi, on selle kaal 0. Lisame sellele juurelemendi:

Indekseeritud kahendpuu

Puu kaaluks saab 1, juurelemendi kaaluks 1. Juureelemendi kaal on puu kaal.

Lisame veel mõned elemendid:

Indekseeritud kahendpuu
Indekseeritud kahendpuu
Indekseeritud kahendpuu
Indekseeritud kahendpuu

Iga kord, kui lisatakse uus element, läheme sõlmedest alla ja suurendame iga läbitud sõlme kaaluloendurit. Kui luuakse uus sõlm, määratakse sellele kaal 1. Kui sellise võtmega sõlm on juba olemas, siis kirjutame väärtuse üle ja läheme tagasi juure, tühistades kõigi läbitud sõlmede kaalumuutused.
Kui sõlm eemaldatakse, siis läheme alla ja vähendame läbitud sõlmede kaalu.

Indeksid

Liigume nüüd edasi sõlmede indekseerimise juurde. Sõlmed oma indeksit otseselt ei salvesta, see arvutatakse sõlmede kaalu alusel. Kui nad salvestaksid oma indeksi, oleks see nõutav O (n) aeg uuendada kõigi sõlmede indekseid pärast iga muudatust puus.
Liigume edasi visuaalse esituse juurde. Meie puu on tühi, lisame sellele 1. sõlme:

Indekseeritud kahendpuu

Esimesel sõlmel on indeks 0, ja nüüd on võimalikud 2 juhtumit. Esimeses muutub juurelemendi indeks, teises ei muutu.

Indekseeritud kahendpuu

Juures kaalub vasak alampuu 1.

Teine juhtum:

Indekseeritud kahendpuu

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

Sõlme indeks arvutatakse selle vasaku alampuu kaaluna + vanemalt edastatud arvuna. Mis see arv on?, See on indeksi loendur, algselt on see võrdne 0, sest juurel pole vanemat. Siis oleneb kõik sellest, kuhu laskume vasakpoolsesse või õigesse lapsesse. Kui vasakule, siis loendurile ei lisata midagi. Kui lisada õigele praeguse sõlme indeksi.

Indekseeritud kahendpuu

Näiteks kuidas arvutatakse võtmega 8 (juure õige alam) elemendi indeks. See on "juurindeks" + "võtmega 8 sõlme vasakpoolse alampuu kaal" + "1" == 3 + 2 + 1 == 6
6. võtmega elemendi indeks on "juurindeks" + 1 == 3 + 1 == 4

Sellest tulenevalt võtab elemendi hankimine ja kustutamine indeksi järgi aega O (log n), sest soovitud elemendi saamiseks peame selle esmalt üles leidma (juurest selle elemendi juurde minema).

Sügavus

Kaalu järgi saab arvutada ka puu sügavuse. Vajalik tasakaalustamiseks.
Selleks tuleb praeguse sõlme kaal ümardada esimese arvuni 2 astmeni, mis on suurem või võrdne antud kaaluga ja võtta sellest binaarlogaritm. See annab meile puu sügavuse, eeldades, et see on tasakaalus. Puu tasakaalustatakse pärast uue elemendi sisestamist. Ma ei esita teooriat puude tasakaalustamise kohta. Lähtekoodid pakuvad tasakaalustamisfunktsiooni.

Kood kaalu teisendamiseks sügavuseks.

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

Tulemused

  • toimub uue elemendi sisestamine O (log n)
  • elemendi kustutamine seerianumbri järgi toimub aastal O (log n)
  • elemendi saamine seerianumbri järgi toimub aastal O (log n)

Kiirus O (log n) Maksame selle eest, et kõik andmed salvestatakse sorteeritud kujul.

Ma ei tea, kus selline struktuur võiks kasulik olla. Lihtsalt mõistatus, et veel kord mõista, kuidas puud töötavad. Tänan tähelepanu eest.

Viited

Projekt sisaldab katseandmeid töökiiruse kontrollimiseks. Puu täitub 1000000 elemendid. Ja toimub elementide järjestikune kustutamine, sisestamine ja taastamine 1000000 üks kord. See on 3000000 operatsioonid. Tulemus osutus päris heaks ~ 8 sekundit.

Allikas: www.habr.com

Lisa kommentaar