Man bija uzdevums Å”Äda veida. NepiecieÅ”ams izstrÄdÄt datu glabÄÅ”anas konteineru, kas nodroÅ”ina Å”Ädu funkcionalitÄti:
- ievietot jaunu elementu
- izÅemt elementu pÄc secÄ«bas numura
- iegÅ«t elementu pÄc secÄ«bas numura
- dati tiek glabÄti sakÄrtotÄ veidÄ
Dati tiek nepÄrtraukti pievienoti un izÅemti, tÄdÄļ struktÅ«rai jÄnodroÅ”ina Ätra darbÄ«bas Ätrums. SÄkumÄ mÄÄ£inÄju Å”o ideju Ä«stenot, izmantojot standarta konteinerus no std. Å is ceļŔ neizdevÄs un radÄs sapratne, ka ir jÄizstrÄdÄ kaut kas paÅ”am. VienÄ«gais, kas ienÄca prÄtÄ, bija izmantot binÄro mežu meklÄÅ”anai. TÄ kÄ tas atbilst Ätras ievietoÅ”anas, izÅemÅ”anas un datu glabÄÅ”anas sakÄrtotÄ veidÄ prasÄ«bÄm. Palika tikai izdomÄt, kÄ indeksÄt visus elementus un pÄrskaitÄ«t indeksus, kad mežs mainÄs.
struct node_s {
data_t data;
uint64_t weight; // mezgla svars
node_t *left;
node_t *right;
node_t *parent;
};Å ajÄ rakstÄ bÅ«s vairÄk attÄlu un teorijas nekÄ koda. Kodu varÄs apskatÄ«t saitei lejÄ.
Svars
TÄpÄc koks tika nedaudz modificÄts, pievienojot papildu informÄciju par svaru mezglam. Mezgls svars ir pÄcteÄu skaits Å”im mezglam + 1 (viena elementa svars).
Funkcija, kas iegūst mezgla svaru:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Lapu svaram attiecīgi ir 0.
TÄlÄk pÄriesim pie konkrÄta Å”Äda koka piemÄra vizuÄlÄ attÄla. Melns krÄsÄ tiks attÄlots mezgla atslÄga (vÄrtÄ«ba netiks rÄdÄ«ta, jo tam nav vajadzÄ«bas), sarkans ā mezgla svars, zaļŔ ā mezgla indekss.
Kad koks ir tukÅ”s, tad tÄ svars ir 0. Pievienosim tam saknes elementu:
Koka svars kļūst 1, saknes elementa svars ir 1. Saknes elements ir koka svars.
Pievienojam vÄl dažus elementus:
Katru reizi, kad pievieno jaunu elementu, mÄs nokÄpjam pa mezgliem uz leju un palielinÄm katra izietÄ mezgla svara skaitÄ«tÄju. Izveidojot jaunu mezglu, tam tiek pieŔķirts svars 1. Ja mezglam ar Å”Ädu atslÄgu jau pastÄv, tad pÄrrakstÄm vÄrtÄ«bu un dodamies atpakaļ uz sakni, atcÄlot svaru izmaiÅas visos mezglos, kurus mÄs esam izgÄjuÅ”i.
Ja notiek mezgla dzÄÅ”ana, tad mÄs nokÄpjam uz leju un dekremetÄjam izgÄjuÅ”o mezglu svarus.
Indeksi
Tagad pÄriesim pie tÄ, kÄ indeksÄt mezglus. Mezgli acÄ«mredzami nesaglabÄ savu indeksu, tas tiek aprÄÄ·inÄts, pamatojoties uz mezglu svaru. Ja tie saglabÄtu savu indeksu, tas prasÄ«tu O(n) laiku, lai atjauninÄtu visu mezglu indeksus pÄc katras koka izmaiÅas.
PÄriesim pie vizuÄla attÄlojuma. MÅ«su koks ir tukÅ”s, pievienosim tam pirmo mezglu:
Pirmajam mezglam ir indekss 0, un tagad iespÄjami ir 2 gadÄ«jumi. PirmajÄ gadÄ«jumÄ saknes indekss mainÄ«sies, otrajÄ nemainÄ«sies.
Saknes kreisajam apakŔkokam ir svars 1.
Otrais gadījums:
Saknes indekss nemainÄ«jÄs, jo tÄs kreisÄ apakÅ”koka svars palika 0.
KÄ tiek aprÄÄ·inÄts mezgla indekss, tas ir tÄ kreisÄ apakÅ”koka svars + skaitlis, ko nodod vecÄks. Kas tas ir par skaitli?, Tas ir indeksu skaitÄ«tÄjs, sÄkumÄ tas ir 0, jo saknei nav vecÄka. TÄlÄk viss ir atkarÄ«gs no tÄ, uz kurieni mÄs virzÄmies, uz kreiso bÄrnu vai labo. Ja uz kreiso, tad skaitÄ«tÄjam nekas netiek pievienots. Ja uz labo, tad pievienojam paÅ”reizÄjÄ mezgla indeksu.
PiemÄram, kÄ tiek aprÄÄ·inÄts elementa ar atslÄgu 8 indekss (labais bÄrns saknei). Tas ir "Saknes indekss" + "mezgla ar atslÄgu 8 kreisÄ apakÅ”koka svars" + "1" == 3 + 2 + 1 == 6
Elementa ar atslÄgu 6 indekss bÅ«s "Saknes indekss" + 1 == 3 + 1 == 4
TÄdÄjÄdi, lai iegÅ«tu vai dzÄstu elementu pÄc indeksa, nepiecieÅ”ams laiks O(log n), jo, lai iegÅ«tu vajadzÄ«go elementu, mums vispirms ir jÄatrod tas (jÄnonÄk no saknes lÄ«dz Å”im elementam).
Dziļums
Pamatojoties uz svaru, var arÄ« aprÄÄ·inÄt koka dziļumu. NepiecieÅ”ams, lai lÄ«dzsvarotu.
Lai to izdarÄ«tu, paÅ”reizÄjÄ mezgla svars jÄnoapaļo lÄ«dz pirmajam skaitlim, kas ir 2 pakÄpÄ un ir lielÄks vai vienÄds ar dotÄ svara, un jÄÅem tam binÄrais logaritms. TÄdÄjÄdi mÄs iegÅ«sim koka dziļumu, pieÅemot, ka tas ir lÄ«dzsvarots. Koks tiek lÄ«dzsvarots pÄc jauna elementa pievienoÅ”anas. Teoriju par to, kÄ lÄ«dzsvarot kokus, neaprakstÄ«Å”u. Avota kodÄ ir pieejama lÄ«dzsvaroÅ”ana funkcija.
Kods, lai pÄrveidotu svaru par dziļumu.
/*
* ŠŠ¾Š·Š²ŃŠ°ŃŠ°ŠµŃ ŠæŠµŃŠ²Š¾Šµ ŃŠøŃŠ»Š¾ Š² ŃŃŠµŠæŠµŠ½Šø 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));
}SecinÄjumi
- jaunÄ elementa pievienoÅ”ana notiek O(log n)
- elementa dzÄÅ”ana pÄc secÄ«bas notiek O(log n)
- elementa iegÅ«Å”ana pÄc secÄ«bas notiek O(log n)
Ätrums O(log n) mÄs maksÄjam par to, ka visi dati tiek uzglabÄti sakÄrtotÄ formÄ.
Nezinu, kur Å”Äda struktÅ«ra var noderÄt. Tas ir vienkÄrÅ”i uzdevums, lai vÄlreiz saprastu, kÄ darbojas koki. Paldies par uzmanÄ«bu.
Saites
ProjektÄ ir ietverti testÄÅ”anas dati Ätruma pÄrbaudei. Koks tiek aizpildÄ«ts 1000000 elementi. Un notiek secÄ«ga dzÄÅ”ana, ievietoÅ”ana un elementu iegÅ«Å”ana 1000000 reizes. Tas ir 3000000 operÄcijas. RezultÄts izrÄdÄ«jÄs diezgan labs ~ 8 sekundes.
Avots: habr.com
