Ek het op die volgende tipe probleem afgekom. Dit is nodig om 'n databergingshouer te implementeer wat die volgende funksionaliteit verskaf:
- voeg nuwe element in
- verwyder element volgens reeksnommer
- kry element volgens ranggetal
- data word in gesorteerde vorm gestoor
Data word voortdurend bygevoeg en verwyder, die struktuur moet vinnige werkingspoed verseker. Ek het eers probeer om so iets te implementeer met behulp van standaard houers van st. Hierdie pad is nie met sukses bekroon nie en die begrip het gekom dat ek self iets moes implementeer. Die enigste ding wat by my opgekom het, was om 'n binêre soekboom te gebruik. Omdat dit voldoen aan die vereiste van vinnige invoeging, verwydering en berging van data in gesorteerde vorm. Al wat oorbly, is om uit te vind hoe om al die elemente te indekseer en die indekse te herbereken wanneer die boom verander.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Die artikel sal meer prente en teorie as kode bevat. Die kode kan by die skakel hieronder gesien word.
Gewig
Om dit te bereik, het die boom 'n effense verandering ondergaan, bykomende inligting is bygevoeg oor gewig nodus. Die nodus gewig is aantal afstammelinge van hierdie nodus + 1 (gewig van 'n enkele element).
Funksie om nodus gewig te kry:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Die gewig van die vel is dienooreenkomstig gelyk aan 0.
Kom ons gaan dan verder na 'n visuele voorstelling van 'n voorbeeld van so 'n boom. Swart die nodussleutel sal in kleur gewys word (die waarde sal nie gewys word nie, aangesien dit nie nodig is nie), in rooi - knoop gewig, groen - node-indeks.
Wanneer ons boom leeg is, is sy gewig 0. Kom ons voeg 'n wortelelement daarby:
Die gewig van die boom word 1, die gewig van die wortelelement word 1. Die gewig van die wortelelement is die gewig van die boom.
Kom ons voeg nog 'n paar elemente by:
Elke keer as 'n nuwe element bygevoeg word, gaan ons die nodusse af en verhoog die gewigteller van elke nodus wat verby is. Wanneer 'n nuwe nodus geskep word, word 'n gewig daaraan toegeken 1. As 'n nodus met so 'n sleutel reeds bestaan, sal ons die waarde oorskryf en teruggaan na die wortel, wat die veranderinge in die gewigte van alle nodusse wat ons geslaag het, kanselleer.
As 'n nodus verwyder word, gaan ons af en verlaag die gewigte van die geslaagde nodusse.
Indekse
Kom ons gaan nou verder na hoe om nodusse te indekseer. Nodusse stoor nie hul indeks uitdruklik nie, dit word bereken op grond van die gewig van die nodusse. As hulle hul indeks gestoor het, sou dit vereis word O (n) tyd om die indekse van alle nodusse by te werk na elke verandering in die boom.
Kom ons gaan aan na 'n visuele voorstelling. Ons boom is leeg, kom ons voeg die 1ste knoop daarby:
Die eerste nodus het 'n indeks 0, en nou is 2 gevalle moontlik. In die eerste sal die indeks van die wortelelement verander, in die tweede sal dit nie verander nie.
By die wortel weeg die linker subboom 1.
Tweede geval:
Die indeks van die wortel het nie verander nie omdat die gewig van sy linker subboom 0 gebly het.
Die indeks van 'n nodus word bereken as die gewig van sy linker subboom + die getal wat deur die ouer gestuur is. Wat is hierdie getal?, Dit is die indeksteller, aanvanklik is dit gelyk aan 0, omdat die wortel het geen ouer nie. Dan hang dit alles af van waar ons afgaan na die linker kind of die regter een. As dit aan die linkerkant is, word niks by die toonbank gevoeg nie. As ons die indeks van die huidige nodus by die regte een voeg.
Byvoorbeeld, hoe die indeks van 'n element met sleutel 8 (die regte kind van die wortel) bereken word. Dit is "Wortelindeks" + "gewig van linker subboom van nodus met sleutel 8" + "1" == 3 + 2 + 1 == 6
Die indeks van die element met sleutel 6 sal "Root Index" + 1 == 3 + 1 == wees 4
Gevolglik neem dit tyd om 'n element volgens indeks te kry en uit te vee O (log n), want om die gewenste element te kry, moet ons dit eers vind (gaan van die wortel af na hierdie element).
diepte
Op grond van die gewig kan jy ook die diepte van die boom bereken. Nodig vir balansering.
Om dit te doen, moet die gewig van die huidige nodus afgerond word tot die eerste getal tot die mag van 2 wat groter as of gelyk aan die gegewe gewig is en die binêre logaritme daaruit neem. Dit sal ons die diepte van die boom gee, in die veronderstelling dat dit gebalanseerd is. Die boom is gebalanseer nadat 'n nuwe element ingevoeg is. Ek sal nie 'n teorie gee oor hoe om bome te balanseer nie. Die bronkodes verskaf 'n balanserende funksie.
Kode vir die omskakeling van gewig na diepte.
/*
* Возвращает первое число в степени 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));
}Resultate van
- invoeging van 'n nuwe element vind plaas in O (log n)
- die verwydering van 'n element volgens reeksnommer vind plaas in O (log n)
- die verkryging van 'n element volgens reeksnommer vind plaas in O (log n)
Spoed O (log n) Ons betaal vir die feit dat alle data in gesorteerde vorm gestoor word.
Ek weet nie waar so 'n struktuur nuttig kan wees nie. Net 'n legkaart om weer te verstaan hoe bome werk. Dankie vir jou aandag.
verwysings
Die projek bevat toetsdata om die spoed van werking na te gaan. Die boom raak vol 1000000 elemente. En daar is 'n opeenvolgende verwydering, invoeging en herwinning van elemente 1000000 een keer. Dit is 3000000 bedrywighede. Die resultaat was redelik goed ~ 8 sekondes.
Bron: will.com