
Naišao sam na zadatak sledeće vrste. Potrebno je implementirati kontejner za skladištenje podataka koji obezbeđuje sledeću funkcionalnost:
- dodati novi element
- isključiti element po rednom broju
- dobiti element po rednom broju
- podaci se čuvaju u sortiranoj formi
Podaci se konstantno dodaju i uklanjaju, struktura treba da osigura brzu brzinu rada. Prvo sam pokušao da realizujem to koristeći standardne kontejnere iz std. Ovaj put nije uspeo i došao sam do zaključka da moram nešto da implementiram sam. Jedina ideja koja mi je pala na pamet bila je korišćenje binarnog pretraživačkog stabla. Ono zadovoljava zahtev za brzim dodavanjem, uklanjanjem i čuvanjem podataka u sortiranoj formi. Ostalo je samo da se smisli kako indeksirati sve elemente i ponovo izračunati indekse kada se stablo menja.
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 će moći da se pogleda putem linka na dnu.
Težina
Za to je stablo podvrgnuto maloj modifikaciji, dodate su dodatne informacije o težini čvora. Težina čvora je broj potomaka datog čvora + 1 (težina pojedinačnog elementa).
Funkcija za dobijanje težine čvora:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Za listu težina iznosi 0.
Dalje ćemo preći na vizuelno predstavljanje primera takvog stabla. Crnom bojom će biti prikazan ključ čvora (vrednost neće biti prikazana, jer nije potrebna), crvenom — težina čvora, zelenom — indeks čvora.
Kada je stablo prazno, njegova težina iznosi 0. Dodajemo mu korenski element:

Težina stabla postaje 1, težina korenskog elementa je 1. Težina korenskog elementa predstavlja težinu stabla.
Dodajmo još nekoliko elemenata:




Svaki put kada se dodaje novi element, spuštamo se niz čvorove i povećavamo brojač težine svakog proći čvora. Kada se stvara novi čvor, dodeljuju mu se težine 1. Ako čvor sa tim ključem već postoji, prepisujemo njegovu vrednost i vraćamo se unazad do korena, poništavajući promene težina kod svih čvorova koje smo prošli.
Ako se vrši brisanje čvora, spuštamo se niz i smanjujemo težine prošlih čvorova.
Indeksi
Sada ćemo preći na to kako indeksirati čvorove. Čvorovi očigledno ne čuvaju svoj indeks, on se izračunava na osnovu težine čvorova. Da ih čuvaju, bilo bi potrebno O(n) vremena, da se ažuriraju indeksi svih čvorova nakon svake promene stabla.
Pređimo na vizualni prikaz. Naše stablo je prazno, dodajemo prvi čvor:

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

Koren ima levu podstablo težine 1.
Drugi slučaj:

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 prenesen od roditelja. Šta je to za broj?, To je brojač indeksa, koji je prvobitno jednak 0, pošto koren nema roditelja. Dalje, sve zavisi od toga gde se spuštamo do levog deteta ili desnog. Ako se spuštamo do levog, onda se brojaču ne dodaje ništa. Ako se spuštamo do desnog, onda dodajemo indeks trenutnog čvora.

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 će biti "Indeks korena" + 1 == 3 + 1 == 4
Prema tome, da bismo dobili, uklonili element po indeksu, potrebno je vreme O(log n), pošto da bismo dobili željeni element prvo moramo da ga pronađemo (da se spustimo od korena do tog elementa).
Dubina
Na osnovu težine se takođe može izračunati i dubina stabla. Potrebna za balansu.
Za to treba težinu trenutnog čvora zaokružiti na prvo broj u eksponentu 2 koje je veće ili jednako datoj težini i uzeti njegov binarni logaritam. Tako ćemo dobiti dubinu stabla, pod uslovom da je ono izbalansirano. Stablo se balansira nakon umetanja novog elementa. Teoriju o tome kako balansirati stabla neću iznositi. U izvor kodovima je predstavljena funkcija za balansiranje.
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 se dešava za O(log n)
- Uklanjanje elementa po rednom broju se dešava za O(log n)
- Dobijanje elementa po rednom broju se dešava za O(log n)
Brzina O(log n) plaćamo za to što su svi podaci pohranjeni u sortiranom obliku.
Gdje može biti korisna takva struktura — ne znam. Samo zadatak da ponovo razjasnim kako funkcionišu stabla. Hvala na pažnji.
Linkovi
U projektu se nalaze testni podaci za proveru brzine rada. Stablo se popunjava 1000000 elemenata. I dešava se sekvencijalno brisanje, umetanje i dobijanje elemenata 1000000 puta. To jest 3000000 operacija. Rezultat se pokazao sasvim dobrom ~ 8 sekundi.
Izvor: habr.com
