Indeksirano binarno stablo

Naišao sam na sledeću vrstu problema. Potrebno je implementirati kontejner za pohranu podataka koji pruža sljedeću funkcionalnost:

• umetnite novi element
• ukloniti element po serijskom broju
• dobiti element po rednom broju
• podaci se pohranjuju u sortiranom obliku

Podaci se stalno dodaju i uklanjaju, struktura mora osigurati brzu brzinu rada. U početku sam pokušao implementirati takvu stvar koristeći standardne kontejnere iz std. Ovaj put nije bio okrunjen uspjehom i došlo je razumijevanje da moram nešto i sam implementirati. Jedina stvar koja mi je pala na pamet je korištenje binarnog stabla pretraživanja. Zato što ispunjava zahtjeve brzog umetanja, brisanja i skladištenja podataka u sortiranom obliku. Ostaje samo da smislimo kako indeksirati sve elemente i ponovo izračunati indekse kada se stablo promijeni.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Članak će sadržavati više slika i teorije nego koda. Kod se može pogledati na linku ispod.

Težina

Da bi se to postiglo, stablo je podvrgnuto malim modifikacijama, dodane su dodatne informacije o tome težina čvor. Težina čvora je broj potomaka ovog čvora + 1 (težina jednog elementa).

Funkcija za dobivanje težine čvora:

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

    return 0;
}

Težina lista je shodno tome jednaka 0.

Zatim, prijeđimo na vizualni prikaz primjera takvog stabla. Crna ključ čvora će biti prikazan u boji (vrijednost neće biti prikazana, jer to nije potrebno), crvena - težina čvora, zeleno — indeks čvora.

Kada je naše drvo prazno, njegova težina je 0. Dodajmo mu korijenski element:

Težina stabla postaje 1, težina korijenskog elementa postaje 1. Težina korijenskog elementa je težina stabla.

Dodajmo još nekoliko elemenata:

Svaki put kada se doda novi element, spuštamo se niz čvorove i povećavamo brojač težine svakog prođenog čvora. Kada se kreira novi čvor, dodeljuje mu se težina 1. Ako čvor sa takvim ključem već postoji, tada ćemo prepisati vrijednost i vratiti se na korijen, poništavajući promjene u težinama svih čvorova koje smo prošli.
Ako se čvor uklanja, onda se spuštamo i smanjujemo težine prenesenih čvorova.

Indeksi

Sada pređimo na indeksiranje čvorova. Čvorovi ne pohranjuju eksplicitno svoj indeks, on se izračunava na osnovu težine čvorova. Ako bi pohranili svoj indeks, onda bi to bilo potrebno O (n) vrijeme za ažuriranje indeksa svih čvorova nakon svake promjene u stablu.
Pređimo na vizuelni prikaz. Naše stablo je prazno, dodajmo mu 1. čvor:

Prvi čvor ima indeks 0, a sada su moguća 2 slučaja. U prvom će se promijeniti indeks korijenskog elementa, u drugom se neće promijeniti.

U korijenu, lijevo podstablo teži 1.

drugi slučaj:

Indeks korijena se nije promijenio jer je težina njegovog lijevog podstabla ostala 0.

Indeks čvora se izračunava kao težina njegovog lijevog podstabla + broj koji je proslijeđen od roditelja. Koji je ovo broj?, Ovo je brojač indeksa, u početku je jednak 0, jer korijen nema roditelja. Onda sve zavisi gde ćemo se spustiti do levog deteta ili do desnog. Ako je lijevo, onda se ništa ne dodaje na brojač. Ako dodamo indeks trenutnog čvora desnom.

Na primjer, kako se izračunava indeks elementa s ključem 8 (desno dijete korijena). Ovo je "Root Index" + "težina lijevog podstabla čvora sa ključem 8" + "1" == 3 + 2 + 1 == 6
Indeks elementa sa ključem 6 će biti "Root Index" + 1 == 3 + 1 == 4

U skladu s tim, potrebno je vrijeme da se dobije i izbriše element po indeksu O (log n), jer da bismo dobili željeni element moramo ga prvo pronaći (sići od korijena do ovog elementa).

Dubina

Na osnovu težine možete izračunati i dubinu drveta. Neophodan za balansiranje.
Da biste to učinili, težina trenutnog čvora mora se zaokružiti na prvi broj na stepen 2 koji je veći ili jednak datoj težini i iz njega uzeti binarni logaritam. Ovo će nam dati dubinu stabla, pod pretpostavkom da je izbalansirano. Stablo je uravnoteženo nakon umetanja novog elementa. Neću iznositi teoriju o tome kako uravnotežiti drveće. Izvorni kodovi pružaju funkciju balansiranja.

Kod za pretvaranje težine u dubinu.

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

Ishodi

• dolazi do umetanja novog elementa O (log n)
• brisanje elementa po serijskom broju se dešava u O (log n)
• dobijanje elementa po serijskom broju se dešava u O (log n)

Brzina O (log n) Plaćamo činjenicu da se svi podaci pohranjuju u sortiranom obliku.

Ne znam gdje bi takva struktura mogla biti korisna. Samo zagonetka da još jednom shvatite kako drveće funkcionira. Hvala vam na pažnji.

reference

• Izvorni kod stabla

Projekat sadrži testne podatke za provjeru brzine rada. Drvo se puni 1000000 elementi. I postoji sekvencijalno brisanje, umetanje i preuzimanje elemenata 1000000 jednom. To je 3000000 operacije. Rezultat se pokazao prilično dobrim ~ 8 sekundi.

izvor: www.habr.com