Indeksirano binarno drevo

Imel sem nalogo naslednje vrste. Potrebno je implementirati kontejner za shranjevanje podatkov, ki zagotavlja naslednjo funkcionalnost:

• vstaviti nov element
• izbrisati element po vrstnem številu
• pridobiti element po vrstnem številu
• podatki se shranjujejo v urejenem stanju

Podatki se nenehno dodajajo in odstranjujejo, struktura mora omogočati hitro delovanje. Sprva sem poskusil uresničiti to z uporabo standardnih kontejnerjev iz std. Ta pot ni bila uspešna in dojel sem, da moram nekaj razviti sam. Edina misel, ki se je pojavila, je bila uporaba binarnega iskalnega drevesa. Ker zadostuje zahtevam po hitri vstavljanju, brisanju in shranjevanju podatkov v urejenem stanju. Ostalo je le še razmisliti, kako indeksirati vse elemente in ponovno izračunati indekse, ko se drevo spremeni.

struct node_s {
    data_t data;

    uint64_t weight; // teža vozlišča

    node_t *left;
    node_t *right;

    node_t *parent;
};

V članku bo več slik in teorije kot kode. Kode boste lahko videli prek povezave spodaj.

Teža

Za to je drevo doživelo majhno modifikacijo, dodane so bile dodatne informacije o teži vozlišča. Teža vozlišča je število potomcev tega vozlišča + 1 (teža enotnega elementa).

Funkcija za pridobitev teže vozlišča:

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

    return 0;
}

Pri listu je zato teža enaka 0.

Nato bomo prešli k vizualni predstavitvi takega drevesa. Črni barvi bo prikazan ključ vozlišča (vrednost ne bo prikazana, ker to ni potrebno), rdeča — težo vozlišča, zelena — indeks vozlišča.

Ko je drevo prazno, je njegova teža enaka 0. Dodali bomo korenski element:

Teža drevesa postane 1, teža korenskega elementa 1. Teža korenskega elementa je teža drevesa.

Dodali bomo še nekaj elementov:

Vsakič, ko dodamo nov element, se spustimo po vozliščih navzdol in povečamo števec teže vsakega pretečenega vozlišča. Pri ustvarjanju novega vozlišča mu dodelimo težo 1. Če vozlišče s takim ključem že obstaja, bomo prepisali vrednost in se vrnili nazaj do korena, pri čemer bomo razveljavili spremembe tež in pri vseh vozliščih, ki smo jih prešli.
Če pride do brisanja vozlišča, se spustimo navzdol in dekrementiramo teže pretečenih vozlišč.

Indeksi

Zdajmo se k načinu indeksiranja vozlišč. Vozlišča očitno ne shranjujejo svojega indeksa, ta se izračuna na podlagi teže vozlišč. Če bi shranjevala svoj indeks, bi to zahtevalo O(n) čas, da se posodobijo indeksi vseh vozlišč po vsaki spremembi drevesa.
Poglejmo si vizualno predstavitev. Naše drevo je prazno, dodamo prvi vozlišče:

Prvo vozlišče ima indeks 0, zdaj pa sta možna dva primera. V prvem se indeks korenskega elementa spremeni, v drugem pa ne spremeni.

Korena leva poddrevesa tehta 1.

Drug primer:

Indeks korena se ni spremenil, saj je teža njegovega levega poddrevesa ostala 0.

Kako se izračuna indeks vozlišča, je teža njegovega levega poddrevesa + številka, prenesena od starša. Kakšna je ta številka?, To je števec indeksov, sprva je enak 0, ker koren nima starša. Naprej je vse odvisno od tega, ali se spuščamo v levega otroka ali desnega. Če se spuščamo k levemu, se števec ne poveča. Če k desnemu, pa pridamo indeks trenutnega vozlišča.

Na primer, kako se izračuna indeks elementa s ključem 8 (desni otrok korena). To je 'Indeks korena' + 'teža levega poddrevesa vozlišča s ključem 8' + '1' == 3 + 2 + 1 == 6
Indeks elementa s ključem 6 bo 'Indeks korena' + 1 == 3 + 1 == 4

Zato, da pridobimo, odstranimo element po indeksu, je potrebno čas O(log n), saj moramo najprej najti želeni element (se spustiti od korena do tega elementa).

Globina

Na podlagi teže lahko izračunamo tudi globino drevesa. Potrebno za uravnoteženje.
Za to je potrebno težo trenutnega vozlišča zaokrožiti na prvo število v potenci 2, ki je večje ali enako tej teži in vzeti od njega binarni logaritem. Tako bomo dobili globino drevesa, ob predpostavki, da je uravnoteženo. Drevo se uravnoteži po vstavljanju novega elementa. Teorije o tem, kako uravnotežiti drevesa, ne bom navajal. V izvornih kodah je predstavljena funkcija uravnoteženja.

Koda za pretvorbo teže v globino.

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

Zaključki

• vstavljanje novega elementa poteka v O(log n)
• odstranitev elementa po vrstnem številu poteka v O(log n)
• pridobitev elementa po vrstnem številu poteka v O(log n)

Hitrostjo O(log n) plačamo za to, da so vsi podatki shranjeni v urejenem formatu.

Kje bi takšna struktura lahko prišla prav — ne vem. Preprosto naloga, da se še enkrat razjasni, kako delujejo drevesa. Hvala za pozornost.

Povezave

• Izvorna koda drevesa

Projekt vsebuje testne podatke za preverjanje hitrosti delovanja. Drevo se napolni 1000000 elementov. In potekajo zaporedno odstranjevanje, vstavljanje in pridobivanje elementov 1000000 krat. To pomeni 3000000 operacij. Rezultat se je izkazal za čisto dober ~ 8 sekund.

Izvor: habr.com