Indeksirano binarno stablo

Naišao sam na sljedeću vrstu problema. Potrebno je implementirati spremnik za pohranu podataka koji pruža sljedeće funkcionalnosti:

• 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 veliku brzinu rada. Isprva sam pokušao implementirati takvu stvar koristeći standardne spremnike iz sati. Ovaj put nije bio okrunjen uspjehom i došlo je do razumijevanja da moram sam nešto implementirati. Jedino što mi je palo na pamet bilo je korištenje binarnog stabla pretraživanja. Zato što ispunjava zahtjeve brzog umetanja, brisanja i pohranjivanja podataka u sortiranom obliku. Sve što preostaje je smisliti kako indeksirati sve elemente i ponovno 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 vidjeti na poveznici ispod.

Težina

Da bi se to postiglo, stablo je podvrgnuto maloj modifikaciji, dodane su dodatne informacije o težina čvor. Težina čvora je broj potomaka ovog čvora + 1 (težina pojedinog 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 lima je odgovarajuće jednaka 0.

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

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

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

Dodajmo još nekoliko elemenata:

Svaki put kada se doda novi element, idemo niz čvorove i povećavamo brojač težine svakog čvora koji prolazi. Kada se stvori novi čvor, dodjeljuje mu se težina 1. Ako čvor s takvim ključem već postoji, tada ćemo prebrisati vrijednost i vratiti se do korijena, poništavajući promjene u težinama svih čvorova koje smo prošli.
Ako se čvor uklanja, tada idemo dolje i smanjujemo težine prošlih čvorova.

Indeksi

Sada prijeđimo na indeksiranje čvorova. Čvorovi ne pohranjuju eksplicitno svoj indeks, on se izračunava na temelju težine čvorova. Ako su pohranili svoj indeks, onda bi to bilo potrebno O (n) vremena za ažuriranje indeksa svih čvorova nakon svake promjene u stablu.
Prijeđimo na vizualni 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 nije se promijenio jer je težina njegovog lijevog podstabla ostala 0.

Indeks čvora izračunava se kao težina njegovog lijevog podstabla + broj proslijeđen od roditelja. Koji je ovo broj?, Ovo je brojač indeksa, inicijalno je jednak 0, jer korijen nema roditelja. Onda sve ovisi gdje se spuštamo do lijevog djeteta ili do desnog. Ako je lijevo, tada se ništa ne dodaje brojaču. Ako desnom dodamo indeks tekućeg čvora.

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

Sukladno tome, potrebno je vrijeme za dobivanje i brisanje elementa po indeksu O (zapisnik n), jer da bismo dobili željeni element moramo ga prvo pronaći (spustiti se od korijena do ovog elementa).

dubina

Na temelju težine možete izračunati i dubinu stabla. Neophodan za balansiranje.
Da biste to učinili, težina trenutnog čvora mora se zaokružiti na prvi broj na potenciju 2 koja je veća ili jednaka zadanoj težini i iz toga uzeti binarni logaritam. To će nam dati dubinu stabla, pod pretpostavkom da je uravnoteženo. 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));
}

Rezultati

• dolazi do umetanja novog elementa O (zapisnik n)
• brisanje elementa po serijskom broju događa se u O (zapisnik n)
• dobivanje elementa serijskim brojem događa se u O (zapisnik n)

Ubrzati O (zapisnik n) Mi plaćamo činjenicu da su svi podaci pohranjeni u sortiranom obliku.

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

reference

• Izvorni kod stabla

Projekt sadrži testne podatke za provjeru brzine rada. Stablo se puni 1000000 elementi. Postoji sekvencijalno brisanje, umetanje i dohvaćanje elemenata 1000000 jednom. To je 3000000 operacije. Rezultat se pokazao prilično dobrim ~ 8 sekundi.

Izvor: www.habr.com