Indeksirano binarno stablo

Indeksirano binarno stablo

Naišla sam na zadatak sljedeće vrste. Potrebno je implementirati kontejner za pohranu podataka koji omogućava sljedeću funkcionalnost:

  • dodati novi element
  • ukloniti element prema rednom broju
  • dobiti element prema rednom broju
  • podaci se pohranjuju u sortiranom obliku

Podaci se stalno dodaju i uklanjaju, struktura mora osigurati brzo vrijeme obrade. Najprije sam pokušala implementirati nešto koristeći standardne kontejnere iz std. Ovaj put nije bio uspješan, a spoznaja je došla da moram implementirati nešto sama. Jedina ideja koja mi je pala na pamet bila je korištenje binarnog stabla pretraživanja. Budući da zadovoljava zahtjev za brzim dodavanjem, uklanjanjem i pohranjivanjem podataka u sortiranom obliku. Ostalo je samo smisliti kako indeksirati sve elemente i recalculirati indekse kada se stablo mijenja.

struct node_s {    
    data_t data;

    uint64_t weight; // težina čvora

    node_t *left;
    node_t *right;

    node_t *parent;
};

U članku će biti više slika i teorije nego koda. Kod možete pogledati na linku ispod.

Težina

U tu svrhu stablo je podvrgnuto maloj modifikaciji, dodane su dodatne informacije o težini čvora. Težina čvora je broj potomaka ovog čvora + 1 (težina jediničnog elementa).

Funkcija za dobivanje težine čvora:

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

    return 0;
}

Za list odgovarajuće težina iznosi 0.

Nakon toga prelazimo na vizualno predstavljanje primjera takvog stabla. Crnom bojom bit će prikazan ključ čvora (vrijednost neće biti prikazana, jer za to nema potrebe), crvenom — težina čvora, zelenom — indeks čvora.

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

Indeksirano binarno stablo

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

Dodajmo još nekoliko elemenata:

Indeksirano binarno stablo
Indeksirano binarno stablo
Indeksirano binarno stablo
Indeksirano binarno stablo

Svaki put kada se dodaje novi element, silazimo niz čvorove i povećavamo brojač težine svakog čvora kroz koji prolazimo. Kada se stvori novi čvor, dodjeljuje mu se težina 1. Ako čvor s tim ključem već postoji, prepisujemo vrijednost i vraćamo se prema korijenu poništavajući promjene težina svih čvorova kroz koje smo prošli.
Ako se vrši brisanje čvora, silazimo dolje i smanjujemo težine prokušanih čvorova.

Indeksi

Sada pređimo na to kako indeksirati čvorove. Čvorovi očigledno ne čuvaju svoj indeks, on se izračunava na osnovu težine čvorova. Da čuvaju svoj indeks, bilo bi potrebno O(n) vremena da se ažuriraju indeksi svih čvorova nakon svake promene drveta.
Pređimo na vizualni prikaz. Naše drvo je prazno, dodajmo mu prvi čvor:

Indeksirano binarno stablo

Prvi čvor ima indeks 0, a sada su moguća dva slučaja. U prvom se indeks korenskog elementa menja, u drugom ne menja.

Indeksirano binarno stablo

Kod korena levi podstablo ima težinu 1.

Drugi slučaj:

Indeksirano binarno stablo

Indeks korena se nije promenio, jer je težina njegovog levog podstabla ostala 0.

Kako se računa indeks čvora, to je težina njegovog levog podstabla + broj prenet od roditelja. Šta je to za broj? To je brojač indeksa, u početku je jednak 0, jer koren nema roditelja. Sve dalje zavisi od toga da li se spuštamo levom detetu ili desnom. Ako se spuštamo levom, brojaču se ništa ne dodaje. Ako se spuštamo desnom, onda dodajemo indeks trenutnog čvora.

Indeksirano binarno stablo

Na primer, kako se računa indeks elementa sa ključem 8 (desno dete korena). To je "Indeks korena" + "težina levog podstabla čvora sa ključem 8" + "1" == 3 + 2 + 1 == 6
Indeks elementa sa ključem 6 biće "Indeks korena" + 1 == 3 + 1 == 4

Shodno tome, da bismo dobili, obrisali element po indeksu potrebno je vreme O(log n), budući da da bismo dobili potrebni element prvo moramo da ga pronađemo (da se spustimo od korena do tog elementa).

Dubina

Na osnovu težine takođe se može izračunati i dubina drveta. Potrebna za balansiranje.
Za to treba zaokružiti težinu trenutnog čvora na prvo broj u stepeni 2 koje je veće ili jednako datoj težini i uzeti od njega binarni logaritam. Tako ćemo dobiti dubinu drveta, pod uslovom da je izbalansirano. Drvo se balansira nakon umetanja novog elementa. Teoriju o tome kako balansirati drveće neću navoditi. U izvoru koda predstavljena je funkcija balansiranja.

Kod za prevođenje 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));
}

Zaključci

  • Umetanje novog elementa dešava se za O(log n)
  • Brisanje elementa po redoslednom broju dešava se za O(log n)
  • Dobijanje elementa po redoslednom broju dešava se za O(log n)

Brzina O(log n) plaćamo za to što su svi podaci pohranjeni u sortiranom obliku.

Gdje bi takva struktura mogla biti korisna — ne znam. Samo zadatak da se još jednom razjasni kako rade stabla. Hvala na pažnji.

Linkovi

U projektu se nalaze testni podaci za provjeru brzine rada. Stablo se popunjava 1000000 elemenata. Dogodila se sekvencijalna brisanja, umetanja i dohvaćanja elemenata 1000000 puta. Dakle, 3000000 operacija. Rezultat je bio prilično dobar ~ 8 sekundi.

Izvor: habr.com

Kupite pouzdan hosting za web stranice s DDoS zaštitom, VPS VDS servere 🔥 Kupite pouzdan hosting za web stranice s DDoS zaštitom, VPS VDS servere | ProHoster