Kam hasur në llojin e mëposhtëm të problemit. Është e nevojshme të zbatohet një kontejner i ruajtjes së të dhënave që ofron funksionalitetin e mëposhtëm:
- fut një element të ri
- hiqni elementin sipas numrit të serisë
- merrni elementin sipas numrit rendor
- të dhënat ruhen në formë të renditur
Të dhënat shtohen dhe hiqen vazhdimisht, struktura duhet të sigurojë shpejtësi të shpejtë funksionimi. Në fillim u përpoqa ta zbatoja një gjë të tillë duke përdorur kontejnerë standardë nga standarde. Kjo rrugë nuk u kurorëzua me sukses dhe erdhi mirëkuptimi që më duhej të zbatoja vetë diçka. E vetmja gjë që më erdhi në mendje ishte përdorimi i një peme kërkimi binar. Sepse plotëson kërkesat e futjes, fshirjes dhe ruajtjes së shpejtë të të dhënave në formë të renditur. E tëra që mbetet është të kuptojmë se si të indeksojmë të gjithë elementët dhe të rillogaritim indekset kur pema ndryshon.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Artikulli do të përmbajë më shumë fotografi dhe teori sesa kod. Kodin mund ta shikoni në linkun e mëposhtëm.
peshë
Për të arritur këtë, pema iu nënshtrua një modifikimi të lehtë, u shtuan informacione shtesë rreth saj peshë nyje. Pesha e nyjës është numri i pasardhësve të kësaj nyje + 1 (pesha e një elementi të vetëm).
Funksioni për marrjen e peshës së nyjës:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Pesha e fletës është përkatësisht e barabartë me 0.
Tjetra, le të kalojmë në një paraqitje vizuale të një shembulli të një peme të tillë. E zezë çelësi i nyjes do të shfaqet me ngjyra (vlera nuk do të shfaqet, pasi kjo nuk është e nevojshme), i kuq - pesha e nyjës, e gjelbër - indeksi i nyjeve.
Kur pema jonë është bosh, pesha e saj është 0. Le të shtojmë një element rrënjë në të:
Pesha e pemës bëhet 1, pesha e elementit rrënjë bëhet 1. Pesha e elementit rrënjë është pesha e pemës.
Le të shtojmë disa elementë të tjerë:
Sa herë që shtohet një element i ri, ne zbresim nyjet dhe rrisim numëruesin e peshës së secilës nyje të kaluar. Kur krijohet një nyje e re, i caktohet një peshë 1. Nëse një nyje me një çelës të tillë ekziston tashmë, atëherë ne do ta mbishkruajmë vlerën dhe do të kthehemi në rrënjë, duke anuluar ndryshimet në peshat e të gjitha nyjeve që kemi kaluar.
Nëse një nyje po hiqet, atëherë ne zbresim dhe zvogëlojmë peshat e nyjeve të kaluara.
Tregues
Tani le të kalojmë në mënyrën se si të indeksojmë nyjet. Nyjet nuk e ruajnë në mënyrë eksplicite indeksin e tyre, ai llogaritet në bazë të peshës së nyjeve. Nëse e ruanin indeksin e tyre, atëherë do të kërkohej O (n) koha për të përditësuar indekset e të gjitha nyjeve pas çdo ndryshimi në pemë.
Le të kalojmë në një paraqitje vizuale. Pema jonë është bosh, le të shtojmë nyjen e parë në të:
Nyja e parë ka një indeks 0, dhe tani janë të mundshme 2 raste. Në të parën, indeksi i elementit rrënjë do të ndryshojë, në të dytën nuk do të ndryshojë.
Në rrënjë, nënpema e majtë peshon 1.
Rasti i dytë:
Indeksi i rrënjës nuk ndryshoi sepse pesha e nënpemës së saj të majtë mbeti 0.
Indeksi i një nyje llogaritet si pesha e nënpemës së majtë të saj + numri i kaluar nga prindi. Sa është ky numër?, Ky është numëruesi i indeksit, fillimisht është i barabartë me 0, sepse rrënja nuk ka prind. Pastaj gjithçka varet nga ku zbresim tek fëmija i majtë apo tek ai i djathtë. Nëse në të majtë, atëherë asgjë nuk shtohet në banak. Nëse i shtojmë indeksin e nyjës aktuale tek e djathta.
Për shembull, si llogaritet indeksi i një elementi me çelës 8 (fëmija i duhur i rrënjës). Ky është "Indeksi i rrënjës" + "pesha e nënpemës së majtë të nyjës me çelësin 8" + "1" == 3 + 2 + 1 == 6
Indeksi i elementit me çelësin 6 do të jetë "Indeksi i rrënjës" + 1 == 3 + 1 == 4
Prandaj, duhet kohë për të marrë dhe fshirë një element sipas indeksit O (regjistro n), sepse për të marrë elementin e dëshiruar fillimisht duhet ta gjejmë atë (të zbresim nga rrënja në këtë element).
thellësi
Në bazë të peshës, mund të llogarisni edhe thellësinë e pemës. E nevojshme për balancimin.
Për ta bërë këtë, pesha e nyjës aktuale duhet të rrumbullakoset në numrin e parë në fuqinë 2 që është më e madhe ose e barabartë me peshën e dhënë dhe të merret logaritmi binar prej tij. Kjo do të na japë thellësinë e pemës, duke supozuar se ajo është e balancuar. Pema është e balancuar pas futjes së një elementi të ri. Unë nuk do të jap një teori se si të balancohen pemët. Kodet burimore ofrojnë një funksion balancues.
Kodi për konvertimin e peshës 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));
}Rezultatet e
- futja e një elementi të ri ndodh në O (regjistro n)
- fshirja e një elementi sipas numrit serik ndodh në O (regjistro n)
- marrja e një elementi sipas numrit serik ndodh në O (regjistro n)
Shpejtësia O (regjistro n) Ne paguajmë për faktin që të gjitha të dhënat ruhen në formë të renditur.
Nuk e di se ku mund të jetë e dobishme një strukturë e tillë. Vetëm një enigmë për të kuptuar edhe një herë se si funksionojnë pemët. Faleminderit per vemendjen.
Referencat
Projekti përmban të dhëna testimi për të kontrolluar shpejtësinë e funksionimit. Pema po mbushet 1000000 elementet. Dhe ka një fshirje, futje dhe rikuperim vijues të elementeve 1000000 një herë. Kjo eshte 3000000 operacionet. Rezultati doli të ishte mjaft i mirë ~ 8 sekonda.
Burimi: www.habr.com