Indeksirano binarno drevo

Naletel sem na naslednjo vrsto težave. Potrebno je implementirati vsebnik za shranjevanje podatkov, ki zagotavlja naslednje funkcije:

• vstavite nov element
• odstranite element po serijski številki
• dobimo element po redni številki
• podatki so shranjeni v razvrščeni obliki

Podatki se nenehno dodajajo in odstranjujejo, struktura mora zagotavljati hitro delovanje. Sprva sem poskušal izvesti takšno stvar s standardnimi vsebniki iz std. Ta pot ni bila okronana z uspehom in prišlo je razumevanje, da moram nekaj izvesti sam. Edina stvar, ki mi je prišla na misel, je bila uporaba binarnega iskalnega drevesa. Ker izpolnjuje zahtevo po hitrem vstavljanju, brisanju in shranjevanju podatkov v urejeni obliki. Vse, kar ostane, je ugotoviti, kako indeksirati vse elemente in ponovno izračunati indekse, ko se drevo spremeni.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Članek bo vseboval več slik in teorije kot kode. Kodo si lahko ogledate na spodnji povezavi.

Teža

Da bi to dosegli, je bilo drevo nekoliko spremenjeno, dodane so bile dodatne informacije o utež vozlišče. Teža vozlišča je število potomcev tega vozlišča + 1 (teža posameznega elementa).

Funkcija za pridobivanje teže vozlišča:

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

    return 0;
}

Teža lista je ustrezno enaka 0.

Nato preidimo na vizualno predstavitev primera takšnega drevesa. Črno ključ vozlišča bo prikazan v barvi (vrednost ne bo prikazana, ker to ni potrebno), rdeča — teža vozla, zeleno — indeks vozlišča.

Ko je naše drevo prazno, je njegova teža 0. Dodajmo mu korenski element:

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

Dodajmo še nekaj elementov:

Vsakič, ko je dodan nov element, gremo navzdol po vozliščih in povečamo števec teže vsakega prehojenega vozlišča. Ko je ustvarjeno novo vozlišče, se mu dodeli utež 1. Če vozlišče s takšnim ključem že obstaja, bomo vrednost prepisali in se vrnili do korena ter preklicali spremembe uteži vseh vozlišč, ki smo jih posredovali.
Če je vozlišče odstranjeno, gremo navzdol in zmanjšamo uteži prenesenih vozlišč.

Indeksi

Zdaj pa preidimo na indeksiranje vozlišč. Vozlišča ne shranjujejo eksplicitno svojega indeksa, izračuna se na podlagi teže vozlišč. Če bi shranili svoj indeks, bi bil potreben O (n) čas za posodobitev indeksov vseh vozlišč po vsaki spremembi v drevesu.
Preidimo k vizualni predstavitvi. Naše drevo je prazno, dodamo mu 1. vozlišče:

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

V korenu levo poddrevo tehta 1.

Drugi primer:

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

Indeks vozlišča se izračuna kot teža njegovega levega poddrevesa + število, posredovano od nadrejenega. Kaj je to število?, To je indeksni števec, na začetku je enak 0, Ker koren nima nadrejenega. Potem je vse odvisno od tega, kje se spustimo do levega otroka ali do desnega. Če na levo, se števcu ne doda nič. Če dodamo indeks trenutnega vozlišča desnemu.

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

V skladu s tem je potreben čas za pridobitev in brisanje elementa po indeksu O (dnevnik n), ker da bi dobili želeni element, ga moramo najprej najti (spustiti se od korena do tega elementa).

Globina

Na podlagi teže lahko izračunate tudi globino drevesa. Potreben za uravnoteženje.
Da bi to naredili, je treba težo trenutnega vozlišča zaokrožiti na prvo številko na potenco 2, ki je večja ali enaka dani uteži, in iz tega vzeti binarni logaritem. To nam bo dalo globino drevesa, ob predpostavki, da je uravnoteženo. Drevo je po vstavitvi novega elementa uravnoteženo. Ne bom dal teorije o tem, kako uravnotežiti drevesa. Izvorne kode zagotavljajo funkcijo 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));
}

Rezultati

• pride do vstavitve novega elementa O (dnevnik n)
• brisanje elementa po serijski številki se zgodi v O (dnevnik n)
• pridobivanje elementa po serijski številki se zgodi v O (dnevnik n)

Hitrost O (dnevnik n) Plačamo za to, da so vsi podatki shranjeni v urejeni obliki.

Ne vem, kje bi lahko bila taka struktura uporabna. Samo uganka, da še enkrat razumemo, kako drevesa delujejo. Hvala za vašo pozornost.

reference

• Izvorna koda drevesa

Projekt vsebuje testne podatke za preverjanje hitrosti delovanja. Drevo se polni 1000000 elementi. Obstaja zaporedno brisanje, vstavljanje in pridobivanje elementov 1000000 enkrat. To je 3000000 operacije. Rezultat se je izkazal za kar dobrega ~ 8 sekund.

Vir: www.habr.com