Es saskÄros ar Å”Äda veida problÄmu. Ir nepiecieÅ”ams ieviest datu uzglabÄÅ”anas konteineru, kas nodroÅ”ina Å”Ädas funkcijas:
- ievietot jaunu elementu
- noÅemt elementu pÄc sÄrijas numura
- iegÅ«t elementu pÄc kÄrtas skaitļa
- dati tiek glabÄti sakÄrtotÄ veidÄ
Dati tiek nepÄrtraukti pievienoti un noÅemti, struktÅ«rai jÄnodroÅ”ina Ätrs darbÄ«bas Ätrums. SÄkumÄ es mÄÄ£inÄju ieviest Å”Ädu lietu, izmantojot standarta konteinerus no std. Å is ceļŔ nav vainagojies panÄkumiem un nÄca sapratne, ka vajag kaut ko Ä«stenot paÅ”am. VienÄ«gais, kas ienÄca prÄtÄ, bija izmantot binÄro meklÄÅ”anas koku. Jo tas atbilst prasÄ«bai par Ätru datu ievietoÅ”anu, dzÄÅ”anu un glabÄÅ”anu sakÄrtotÄ veidÄ. Atliek tikai izdomÄt, kÄ indeksÄt visus elementus un pÄrrÄÄ·inÄt indeksus, kad koks mainÄs.
struct node_s {
data_t data;
uint64_t weight; // Š²ŠµŃ ŃŠ·Š»Š°
node_t *left;
node_t *right;
node_t *parent;
};RakstÄ bÅ«s vairÄk attÄlu un teorijas nekÄ koda. Kodu var apskatÄ«t zemÄk esoÅ”ajÄ saitÄ.
Svars
Lai to panÄktu, koks tika nedaudz pÄrveidots, tika pievienota papildu informÄcija svaru mezgls. Mezgla svars ir Ŕī mezgla pÄcnÄcÄju skaits + 1 (viena elementa svars).
Funkcijas mezgla svara iegūŔanai:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Loksnes svars ir attiecÄ«gi vienÄds ar 0.
TÄlÄk pÄriesim pie Å”Äda koka piemÄra vizuÄla attÄlojuma. Melns mezgla atslÄga tiks parÄdÄ«ta krÄsÄ (vÄrtÄ«ba netiks rÄdÄ«ta, jo tas nav nepiecieÅ”ams), sarkans - mezgla svars, zaļŔ ā mezglu indekss.
Kad mÅ«su koks ir tukÅ”s, tÄ svars ir 0. Pievienosim tam saknes elementu:
Koka svars kļūst par 1, saknes elementa svars kļūst par 1. Saknes elementa svars ir koka svars.
Pievienosim vÄl dažus elementus:
Katru reizi, kad tiek pievienots jauns elements, mÄs ejam uz leju pa mezgliem un palielinÄm katra nodotÄ āāmezgla svara skaitÄ«tÄju. Kad tiek izveidots jauns mezgls, tam tiek pieŔķirts svars 1. Ja mezgls ar Å”Ädu atslÄgu jau pastÄv, mÄs pÄrrakstÄ«sim vÄrtÄ«bu un atgriezÄ«simies lÄ«dz saknei, atceļot visu mÅ«su nodoto mezglu svaru izmaiÅas.
Ja mezgls tiek noÅemts, mÄs ejam uz leju un samazinÄm nodoto mezglu svaru.
Indeksi
Tagad pÄriesim pie mezglu indeksÄÅ”anas. Mezgli nepÄrprotami neuzglabÄ savu indeksu, tas tiek aprÄÄ·inÄts, pamatojoties uz mezglu svaru. Ja viÅi saglabÄtu savu indeksu, tad tas bÅ«tu vajadzÄ«gs O (n) laiks atjauninÄt visu mezglu indeksus pÄc katrÄm izmaiÅÄm kokÄ.
PÄriesim pie vizuÄlÄ attÄlojuma. MÅ«su koks ir tukÅ”s, pievienosim tam 1. mezglu:
PirmajÄ mezglÄ ir indekss 0, un tagad ir iespÄjami 2 gadÄ«jumi. PirmajÄ saknes elementa indekss mainÄ«sies, otrajÄ tas nemainÄ«sies.
SaknÄ kreisais apakÅ”koks sver 1.
Otrais gadījums:
Saknes indekss nemainÄ«jÄs, jo tÄs kreisÄ apakÅ”koka svars palika 0.
Mezgla indekss tiek aprÄÄ·inÄts kÄ tÄ kreisÄ apakÅ”koka svars + no vecÄka nodotais skaitlis. KÄds ir Å”is skaitlis?, Å is ir indeksa skaitÄ«tÄjs, sÄkotnÄji tas ir vienÄds ar 0, jo saknei nav vecÄku. Tad viss ir atkarÄ«gs no tÄ, kur mÄs nolaižamies pie kreisÄ bÄrna vai labÄ. Ja pa kreisi, tad skaitÄ«tÄjam nekas netiek pievienots. Ja mÄs pievienojam paÅ”reizÄjÄ mezgla indeksu pareizajam mezglam.
PiemÄram, kÄ tiek aprÄÄ·inÄts elementa indekss ar atslÄgu 8 (saknes labais bÄrns). Tas ir "Saknes indekss" + "mezgla kreisÄ apakÅ”koka svars ar atslÄgu 8" + "1" == 3 + 2 + 1 == 6
Elementa indekss ar taustiÅu 6 bÅ«s "Saknes indekss" + 1 == 3 + 1 == 4
AttiecÄ«gi ir nepiecieÅ”ams laiks, lai iegÅ«tu un izdzÄstu elementu pÄc indeksa O (log n), jo, lai iegÅ«tu vÄlamo elementu, vispirms tas ir jÄatrod (no saknes jÄiet uz leju lÄ«dz Å”im elementam).
Dziļums
Pamatojoties uz svaru, varat arÄ« aprÄÄ·inÄt koka dziļumu. NepiecieÅ”ams lÄ«dzsvaroÅ”anai.
Lai to izdarÄ«tu, paÅ”reizÄjÄ mezgla svars ir jÄnoapaļo lÄ«dz pirmajam skaitlim lÄ«dz pakÄpei 2, kas ir lielÄks vai vienÄds ar doto svaru, un jÄÅem no tÄ binÄrais logaritms. Tas dos mums koka dziļumu, pieÅemot, ka tas ir lÄ«dzsvarots. Koks tiek lÄ«dzsvarots pÄc jauna elementa ievietoÅ”anas. Es nesniegÅ”u teoriju par to, kÄ lÄ«dzsvarot kokus. Avota kodi nodroÅ”ina lÄ«dzsvaroÅ”anas funkciju.
Kods svara pÄrvÄrÅ”anai dziļumÄ.
/*
* ŠŠ¾Š·Š²ŃŠ°ŃŠ°ŠµŃ ŠæŠµŃŠ²Š¾Šµ ŃŠøŃŠ»Š¾ Š² ŃŃŠµŠæŠµŠ½Šø 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));
}RezultÄti
- notiek jauna elementa ievietoŔana O (log n)
- elementa dzÄÅ”ana pÄc sÄrijas numura notiek O (log n)
- elementa iegÅ«Å”ana pÄc sÄrijas numura notiek O (log n)
Ätrums O (log n) MÄs maksÄjam par to, ka visi dati tiek glabÄti sakÄrtotÄ veidÄ.
Es nezinu, kur Å”Äda struktÅ«ra varÄtu bÅ«t noderÄ«ga. Tikai mÄ«kla, lai vÄlreiz saprastu, kÄ darbojas koki. Paldies par jÅ«su uzmanÄ«bu.
atsauces
ProjektÄ ir testa dati, lai pÄrbaudÄ«tu darbÄ«bas Ätrumu. Koks piepildÄs 1000000 elementi. Un notiek elementu secÄ«ga dzÄÅ”ana, ievietoÅ”ana un izgÅ«Å”ana 1000000 vienreiz. Tas ir 3000000 operÄcijas. RezultÄts izrÄdÄ«jÄs diezgan labs ~ 8 sekundes.
Avots: www.habr.com
