Më ra një detyrë e këtij lloji. Duhet të realizoj një enë ruajtjeje të të dhënave që ofron funksionalitetin e mëposhtëm:
- shtoni një element të ri
- fshini elementin sipas numrit rendor
- merrni elementin sipas numrit rendor
- të dhënat ruhen në një formë të renditur
Të dhënat vazhdimisht shtohen dhe fshihen, struktura duhet të ofrojë shpejtësi të shpejtë funksionimi. Fillimisht u përpoqa të realizoj një gjë të tillë duke përdorur enët standarde nga std. Ky rrugë nuk kishte sukses dhe erdhi kuptimi se duhej të realizoja diçka vetë. E vetmja gjë që më erdhi në mend është të përdorja një pemë kërkimi binar. Sepse ajo përmbush kërkesën për një shtim të shpejtë, fshirje dhe ruajtje të dhënash në një formë të renditur. Mbeti vetëm të shpikja si të indeksoja të gjitha elementet dhe të rivlerësoja indeksat kur pemë 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 se kod. Kodu mund të shihet në lidhjen më poshtë.
Pesha
Për këtë, pema iu nënshtrua një modifikimi të vogël, u shtua informacion shtesë mbi pesha e nodit. Pesha e nodit është numri i pasardhësve të këtij nodi + 1 (pesha e një elementi të vetëm).
Funksioni për të marrë pesha e nodit:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Pesha e gjethit përkatësisht është 0.
Më pas, do të kalojmë në një paraqitje vizive të këtij lloji të peme. Me ngjyrë të zezë në të do të tregohen çelësi i nodit (vlera nuk do të tregohet, pasi nuk ka nevojë), me të kuqe - pesha e nodit, me të绿- indeks i nodit. Kur pema është bosh, pesha e saj është 0. Do të shtojmë një element rrënjë në të:
Pesha e pemës bëhet 1, pesha e elementit rrënjë është 1. Pesha e elementit rrënjë është pesha e pemës.
Do të shtojmë edhe disa elementë të tjerë:
Çdo herë kur shtohet një element i ri, ne zbresim përgjatë nodave poshtë dhe rritim numëruesin e pesha të çdo nodi që kalojmë. Kur krijohet një nod i ri, duhet ti caktohet pesha
. Nëse një nod me një çelës të tillë ekziston tashmë, atëherë do ta rrewrite vlerën dhe do të shkojmë prapa deri tek rrënja duke anuluar ndryshimet e peshave në të gjitha nodet që kemi kaluar. 1Nëse ndodhet një fshirje e nodit, atëherë zbresim poshtë dhe dekremetojmë peshat e nodave të kaluar.
Kur, kur rrëshqet një nod, ne zbresim poshtë dhe zvogëlojmë peshat e nodëve të kaluar.
Indeksat
Tani të kalojmë në mënyrën se si të indeksojmë nyjet. Nyjet nuk ruajnë në mënyrë të qartë indeksin e tyre, i cili llogaritet në bazë të peshës së nyjeve. Sikur ato të ruanin indeksin e tyre, do të kërkonte O(n) kohë për të përditësuar indeksin e të gjitha nyjeve pas çdo ndryshimi të pemës.
Tani le të kalojmë në një përfaqësim vizual. Pema jonë është bosh, le të shtojmë nyjën e parë:
Nyja e parë ka indeksin 0, dhe tani ka dy raste. Në rastin e parë, indeksi i elementit rrënjor do të ndryshojë, në rastin e dytë nuk do të ndryshojë.
Në rrënjë, nënpema e majtë ka peshë 1.
Rasti i dytë:
Indeksi i rrënjës nuk ndryshoi, pasi pesha e nënpemës së saj të majtë mbeti 0.
Si llogaritet indeksi i një nyjeje, është pesha e nënpemës së saj të majtë + numri i dhënë nga prindi. Cili është ky numër? Është numëruesi i indekseve, fillimisht ai është 0, pasi rrënja nuk ka prind. Më pas, gjithçka varet nga se ku zbresim, te fëmija e majtë apo e djathtë. Nëse te e majta, atëherë numëruari nuk shtohet. Nëse te e djathta, shtojmë indeksin e nyjës aktuale.
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ënçelë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
Prandaj, për të marrë, fshirë një element sipas indeksit kërkohet kohë O(log n), pasi që për të marrë elementin e nevojshëm duhet të gjejmë fillimisht atë (të zbresim nga rrënja deri te ky element).
Thellësia
Në bazë të pesha gjithashtu mund të llogaritet thellësia e pemës. E nevojshme për balancimin.
Për këtë, pesha e nyjës aktuale duhet të rrumbullakoset në numrin e parë të fuqisë 2 që është më e madhe ose e barabartë me këtë peshë dhe të merret logaritmi binar prej saj. Kështu do të marrim thellësinë e pemës, me kusht që ajo të jetë e balancuar. Pemën e balancojmë pas shtimit të një elementi të ri. Teorinë mbi mënyrën e balancimit të pemëve nuk do ta paraqes, por në kodet burimore është paraqitur funksioni i balancimit.
Kodi për kthimin e pesha 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ërfundimet
- shtimi i një elementi të ri ndodhi brenda O(log n)
- fshirjes së një elementi sipas rendit ndodh brenda O(log n)
- marrjes së një elementi sipas rendit ndodh brenda O(log n)
Shpejtësia O(log n) paguajmë për atë që të gjitha të dhënat ruhen në një formë të renditur.
Nuk di ku mund të jetë e dobishme një strukturë e tillë. Thjesht një ushtrim për të kuptuar si funksionojnë pemët. Faleminderit për vëmendjen.
Linke
Projekti përmban të dhëna provuese për të kontrolluar shpejtësinë e funksionimit. Pema mbushet 1000000 me elementë. Dhe ndodhin heqje, shtim dhe marrje elementësh në rend. 1000000 Ndryshe, do të thotë 3000000 operacioneve. Rezultati doli mjaft i mirë ~ 8 sekonda.
Burimi: habr.com
