Më ra në dorë një detyrë të tillë. Nevojitet realizimi i një kontejneri për ruajtjen e të dhënave që ofron funksionalitete të mëposhtme:
- shto një element të ri
- fshij elementin sipas numrit rendor
- merr elementin sipas numrit rendor
- të dhënat ruhen në formë të renditur
Të dhënat vazhdimisht shtohen dhe fshihen, struktura duhet të sigurojë shpejtësi të lartë. Fillimisht përpiqesha të realizoja një gjë të tillë duke përdorur kontejnerët standardë nga std. Ky rrugë nuk rezultoi me sukses dhe kuptova se duhej të realizoja diçka vetë. E vetmja gjë që më erdhi në mendje ishte të përdorja një pemë binarë kërkimi. Të paktën ajo i përmbush kërkesat për shtim të shpejtë, fshirje dhe ruajtje të të dhënave në formë të renditur. Tani duhet të mendonim se si të indeksojmë të gjithë elementët dhe të ripërllogarisim indeksat kur pema ndryshon.
struct node_s {
data_t data;
uint64_t weight; // pesha e nodit
node_t *left;
node_t *right;
node_t *parent;
};Në këtë artikull do të ketë më shumë figura dhe teori sesa kod. Kodi mund të shikohet në lidhjen më poshtë.
Pesha
Për këtë, pema u nënshtrua një modifikimi të vogël, një informacion shtesë u shtua për peshën nodi. Pesha e nodit është numri i pasardhësve të këtij nodi + 1 (pesha e një elementi).
Funksioni për marrjen e peshës së nodit:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Pesha e gjetheve, përkatësisht, është 0.
Tani kalojmë në paraqitjen vizuale të një shembulli të tillë të pemës. Me ngjyrë të zezë do të tregohet çelësi i nodit (vlera nuk do të tregohet, sepse nuk ka nevojë për këtë), me të kuqe — pesha e nodit, me të verde — indeksi i nodit.
Kur pema është e zbrazët, pesha e saj është 0. Shtojmë një element rrënjësor në të:
Pesha e pemës bëhet 1, pesha e elementit rrënjësor është 1. Pesha e elementit rrënjësor përfaqëson peshën e pemës.
Të shtojmë disa elementë të tjerë:
Sa herë që shtohet një element i ri, ne zbresim përmes nodëve poshtë dhe rrisim numëruesin e peshës për çdo nod të kaluar. Kur krijohet një nod i ri, i jepet pesha 1. Nëse njihet një nod me një çelës të tillë, atëherë ne e ripërshtatim vlerën dhe kthehemi mbrapsht deri në rrënjë duke anuluar ndryshimet e peshave të të gjithë nodëve që kemi kaluar.
Nëse ndodh fshirja e një nodi, ne zbresim poshtë dhe reduktojmë peshat e nodëve të kaluar.
Indeksi
Tani tani kalojmë te si të indeksojmë nodet. Nodet nuk e ruajnë qartë indeksin e tyre, ai llogaritet mbi bazën e peshës së nodit. Po të ruanin indeksin e tyre, do të kërkohej O(n) koha për të azhurnuar indeksat e të gjitha nodave pas çdo ndryshimi në pemë.
Le të kalojmë në një përfaqësim vizual. Pema jonë është bosh, le të shtojmë nodin e parë:
Nodi i parë ka indeksin 0, dhe tani ka dy raste të mundshme. Në rastin e parë, indeksi i elementit rrënjë do të ndryshojë, në rastin e dytë nuk do të ndryshojë.
Nën rrënjën, nëndega e majtë ka peshën 1.
Rasti i dytë:
Indeksi i rrënjës nuk ka ndryshuar, pasi pesha e nëndegës së saj të majtë ka mbetur 0.
Si llogaritet indeksi i nodit, është pesha e nëndegës së saj të majtë + numri i dhënë nga prindi. Çfarë është ky numër? Ky është numri i indekseve, fillimisht ai është 0, pasi rrënja nuk ka prind. Më pas gjithçka varet nga se në cilin anë zhytemi, në fëmijën e majtë apo të djathtë. Nëse shkojmë në të majtë, nuk i shtojmë asgjë këtij numri. Nëse shkojmë në të djathtë, shtojmë indeksi i nodit aktual.
Për shembull, si llogaritet indeksi i elementit me çelës 8 (fëmija i djathtë i rrënjës). Ky është "Indeksi i rrënjës" + "pesha e nëndegës së majtë të nodit me çelës 8" + "1" == 3 + 2 + 1 == 6
Indeksi i elementit me çelës 6 do të jetë "Indeksi i rrënjës" + 1 == 3 + 1 == 4
Përkatësisht, për të marrë, të fshish elementin sipas indeksit kërkohet koha O(log n), pasi për të marrë elementin e nevojshëm, duhet së pari ta gjejmë atë (të zhytemi nga rrënjës te ky element).
Thellësia
Baza peshës gjithashtu mund të llogaritet dhe thellësia e pemës. E nevojshme për balancimin.
Për këtë, pesha e nodit aktual duhet të rroundohet në numrin e parë të fuqisë 2 që është më i madh ose i barabartë me këtë peshë dhe të merret logaritmi dyshifror i saj. Kështu do të marrim thellësinë e pemës, nën kushtin që ajo të jetë e balancuar. Pema balancohet pas shtimit të një elementi të ri. Nuk do të sjellë teorinë se si të balancohet pemët. Në kodet burimore është e pranishme funksioni i balancimit.
Kodi për të kthyer peshën në thellësi.
/*
* Возвращает первое число в степени 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));
}Përfundime
- Shtimi i një elementi të ri ndodh brenda O(log n)
- fshirjes së një elementi sipas numrit të rendit ndodh brenda O(log n)
- marrjes së një elementi sipas numrit të rendit ndodh brenda O(log n)
Shpejtësisë O(log n) shkëmbejmë për faktin se të gjitha të dhënat ruhen në një formë të renditur.
Nuk e di se ku mund të përdoret një strukturë e tillë. Thjesht është një detyrë për t'u theksuar se si funksionojnë pemët. Faleminderit për vëmendjen.
Linket
Projekti përmban të dhëna testuese për të verifikuar shpejtësinë e punës. Pema popullon 1000000 elementëve. Dhe ndodhin fshirje, inserte dhe marrje të elementeve në mënyrë të renditur 1000000 herë. Kështu që 3000000 operacioneve. Rezultati doli të ishte mjaft i mirë ~ 8 sekonda.
Burimi: habr.com
