Ik kaam oer it folgjende type probleem. It is needsaaklik om in kontener foar gegevensopslach te ymplementearjen dy't de folgjende funksjonaliteit leveret:
- ynfoegje nij elemint
- fuortsmite elemint troch serial number
- krije elemint troch ordinaal getal
- gegevens wurde opslein yn sortearre foarm
Gegevens wurde konstant tafoege en fuortsmiten, de struktuer moat soargje foar rappe operaasjesnelheid. Earst haw ik besocht sa'n ding te realisearjen mei standert konteners fan std. Dit paad waard net bekroand mei súkses en it begryp kaam dat ik sels wat útfiere moast. It iennichste dat yn 't sin kaam wie om in binêre sykbeam te brûken. Om't it foldocht oan de eask fan flugge ynfoegje, wiskjen en opslach fan gegevens yn sortearre foarm. Alles wat oerbliuwt is om út te finen hoe't jo alle eleminten yndeksearje en de yndeksen opnij berekkenje as de beam feroaret.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};It artikel sil mear foto's en teory befetsje dan koade. De koade kin besjoen wurde op de link hjirûnder.
Gewicht
Om dit te berikken, de beam ûndergie in lichte modifikaasje, ekstra ynformaasje waard tafoege oer gewicht node. It knooppuntgewicht is oantal neikommelingen fan dizze knooppunt + 1 (gewicht fan ien elemint).
Funksje foar it krijen fan nodegewicht:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}It gewicht fan it blêd is oerienkommende gelyk oan 0.
Lit ús dan fierder gean nei in fisuele foarstelling fan in foarbyld fan sa'n beam. Swart de knooppuntkaai sil yn kleur toand wurde (de wearde sil net werjûn wurde, om't dit net nedich is), read - knoopgewicht, grien - node yndeks.
As ús beam leech is, is syn gewicht 0. Litte wy der in woartelelemint oan tafoegje:
It gewicht fan 'e beam wurdt 1, it gewicht fan it woartelelemint wurdt 1. It gewicht fan it woartelelemint is it gewicht fan 'e beam.
Litte wy in pear mear eleminten tafoegje:
Eltse kear in nij elemint wurdt tafoege, wy geane del de knopen en fergrutsje de gewicht teller fan eltse node trochjûn. As in nij knooppunt wurdt oanmakke, wurdt der in gewicht oan tawiisd 1. As in knooppunt mei sa'n kaai al bestiet, dan sille wy de wearde oerskriuwe en weromgean nei de root, en annulearje de wizigingen yn 'e gewichten fan alle knooppunten dy't wy hawwe trochjûn.
As in knooppunt wurdt fuortsmiten, dan geane wy nei ûnderen en ferminderje de gewichten fan 'e trochjûne knooppunten.
Yndeksen
Litte wy no trochgean nei hoe't jo knopen yndeksearje. Knooppunten bewarje har yndeks net eksplisyt, it wurdt berekkene op basis fan it gewicht fan 'e knopen. As se har yndeks opslaan, dan soe it nedich wêze O (n) tiid om de yndeksen fan alle knopen te aktualisearjen nei elke feroaring yn 'e beam.
Litte wy nei in fisuele foarstelling gean. Us beam is leech, litte wy der de 1e knooppunt oan tafoegje:
De earste node hat in yndeks 0, en no binne 2 gefallen mooglik. Yn 'e earste sil de yndeks fan it root-elemint feroarje, yn' e twadde sil it net feroarje.
By de woartel weegt de linker subtree 1.
Twadde gefal:
De yndeks fan 'e woartel is net feroare, om't it gewicht fan syn linker subtree 0 bleau.
De yndeks fan in knooppunt wurdt berekkene as it gewicht fan syn linker subtree + it nûmer trochjûn fan 'e âlder. Wat is dit getal?, Dit is de yndeks teller, earstoan is it gelyk oan 0, omdat de woartel hat gjin âlder. Dan hinget it allegear ôf wêr't wy nei it linker of de rjochter del geane. As nei lofts, dan wurdt neat tafoege oan de teller. As wy de yndeks fan 'e aktuele knoop oan' e rjochter taheakje.
Bygelyks, hoe't de yndeks fan in elemint mei kaai 8 (it rjochter bern fan 'e woartel) wurdt berekkene. Dit is "Root Index" + "gewicht fan linker subtree fan node mei kaai 8" + "1" == 3 + 2 + 1 == 6
De yndeks fan it elemint mei kaai 6 sil wêze "Root Index" + 1 == 3 + 1 == 4
Dêrtroch nimt it tiid om in elemint per yndeks te krijen en te wiskjen O (log n), want om it winske elemint te krijen moatte wy it earst fine (fan 'e woartel nei dit elemint gean).
Djipte
Op grûn fan it gewicht kinne jo ek de djipte fan 'e beam berekkenje. Needsaaklik foar balâns.
Om dit te dwaan, moat it gewicht fan 'e aktuele knooppunt ôfrûn wurde op it earste getal ta de krêft fan 2 dat grutter is as of gelyk oan it opjûne gewicht en dêr de binêre logaritme fan nimme. Dit sil ús de djipte fan 'e beam jaan, oannommen dat it lykwichtich is. De beam is lykwichtich nei it ynfoegjen fan in nij elemint. Ik sil gjin teory jaan oer hoe't jo beammen balansearje kinne. De boarne koades jouwe in balânsjende funksje.
Koade foar it konvertearjen fan gewicht nei djipte.
/*
* Возвращает первое число в степени 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));
}Resultaten
- ynfoegje fan in nij elemint komt yn O (log n)
- wiskjen fan in elemint troch serial number komt foar yn O (log n)
- it krijen fan in elemint troch serial number komt foar yn O (log n)
Faasje O (log n) Wy betelje foar it feit dat alle gegevens wurde opslein yn sortearre foarm.
Ik wit net wêr't sa'n struktuer nuttich wêze kin. Krekt in puzel om nochris te begripen hoe't beammen wurkje. Tank foar jo oandacht.
referinsjes
It projekt befettet testgegevens om de snelheid fan operaasje te kontrolearjen. De beam giet fol 1000000 eleminten. En d'r is in sekwinsjele wiskjen, ynfoegje en opheljen fan eleminten 1000000 ienris. Dat is 3000000 operaasjes. It resultaat blykte frij goed te wêzen ~ 8 sekonden.
Boarne: www.habr.com