Iltqajt mat-tip ta' problema li ġej. Huwa meħtieġ li jiġi implimentat kontenitur tal-ħażna tad-dejta li jipprovdi l-funzjonalità li ġejja:
- daħħal element ġdid
- neħħi l-element bin-numru tas-serje
- tikseb element b'numru ordinal
- data hija maħżuna f'forma magħżula
Id-data qed tiżdied u titneħħa kontinwament, l-istruttura għandha tiżgura veloċità ta 'operazzjoni mgħaġġla. Għall-ewwel ippruvajt nimplimenta ħaġa bħal din billi tuża kontenituri standard minn STD. Din it-triq ma kinitx inkurunata b'suċċess u wasal il-fehim li kelli bżonn nimplimenta xi ħaġa jien. L-unika ħaġa li ġiet f'moħħna kienet li tuża siġra tat-tfittxija binarja. Minħabba li tissodisfa r-rekwiżit ta 'inserzjoni veloċi, tħassir u ħażna ta' data f'forma magħżula. Li jibqa 'huwa li nsemmu kif tindika l-elementi kollha u tikkalkula mill-ġdid l-indiċi meta tinbidel is-siġra.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};L-artiklu se jkun fih aktar stampi u teorija milli kodiċi. Il-kodiċi jista 'jaraha fil-link hawn taħt.
Piż
Biex jinkiseb dan, is-siġra għaddiet minn modifika żgħira, ġiet miżjuda informazzjoni addizzjonali dwarha piż nodu. Il-piż tan-nodu huwa numru ta’ dixxendenti ta’ dan in-node + 1 (piż ta’ element wieħed).
Funzjoni biex tikseb il-piż tan-node:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Il-piż tal-folja huwa korrispondentement ugwali għal 0.
Sussegwentement, ejja ngħaddu għal rappreżentazzjoni viżiva ta 'eżempju ta' siġra bħal din. Iswed iċ-ċavetta tan-node se tintwera bil-kulur (il-valur mhux se jintwera, peress li dan mhux meħtieġ), aħmar — il-piż tal-għoqda, aħdar — indiċi tan-nodi.
Meta s-siġra tagħna tkun vojta, il-piż tagħha huwa 0. Ejja nżidu element għerq magħha:
Il-piż tas-siġra jsir 1, il-piż tal-element tal-għeruq isir 1. Il-piż tal-element tal-għerq huwa l-piż tas-siġra.
Ejja nżidu ftit elementi oħra:
Kull darba li jiġi miżjud element ġdid, ninżlu n-nodi u nżidu l-counter tal-piż ta 'kull nodu mgħoddi. Meta jinħoloq nodu ġdid, jiġi assenjat piż lilu 1. Jekk node b'tali ċavetta diġà jeżisti, allura aħna se niktbu fuq il-valur u mmorru lura għall-għerq, u nikkanċellaw il-bidliet fil-piżijiet tan-nodi kollha li għaddejna.
Jekk node qed jitneħħa, allura ninżlu u nnaqqsu l-piżijiet tan-nodi mgħoddija.
Indiċijiet
Issa ejja nimxu fuq kif indiċi nodes. In-nodi ma jaħżnux b'mod espliċitu l-indiċi tagħhom, huwa kkalkulat abbażi tal-piż tan-nodi. Jekk huma jaħżnu l-indiċi tagħhom, allura jkun meħtieġ O (n) ħin biex taġġorna l-indiċi tan-nodi kollha wara kull bidla fis-siġra.
Ejja ngħaddu għal rappreżentazzjoni viżiva. Is-siġra tagħna hija vojta, ejja nżidu l-ewwel nodu magħha:
L-ewwel node għandu indiċi 0, u issa 2 każijiet huma possibbli. Fl-ewwel, l-indiċi tal-element għerq se jinbidel, fit-tieni mhux se jinbidel.
Fl-għerq, is-subsiġra tax-xellug tiżen 1.
It-tieni każ:
L-indiċi tal-għerq ma nbidilx minħabba li l-piż tas-subsiġra tax-xellug tiegħu baqa '0.
L-indiċi ta 'node huwa kkalkulat bħala l-piż tas-subtree tax-xellug tiegħu + in-numru mgħoddi mill-ġenitur. X'inhu dan in-numru?, Dan huwa l-counter tal-indiċi, inizjalment huwa ugwali għal 0, għax l-għerq m'għandux ġenitur. Imbagħad kollox jiddependi minn fejn ninżlu għat-tifel tax-xellug jew tal-lemin. Jekk fuq ix-xellug, allura xejn ma jiżdied mal-counter. Jekk inżidu l-indiċi tan-node kurrenti mal-lemin.
Pereżempju, kif jiġi kkalkulat l-indiċi ta 'element biċ-ċavetta 8 (it-tifel tal-lemin tal-għerq). Dan huwa "Root Index" + "piż tas-subtree tax-xellug tan-node b'ċavetta 8" + "1" == 3 + 2 + 1 == 6
L-indiċi tal-element biċ-ċavetta 6 se jkun "Root Index" + 1 == 3 + 1 == 4
Għaldaqstant, jieħu ż-żmien biex tikseb u tħassar element b'indiċi O (log n), għax sabiex niksbu l-element mixtieq l-ewwel irridu nsibuh (jinżlu mill-għerq għal dan l-element).
Il-fond
Ibbażat fuq il-piż, tista 'wkoll tikkalkula l-fond tas-siġra. Meħtieġa għall-ibbilanċjar.
Biex tagħmel dan, il-piż tan-nodu kurrenti għandu jkun imqarreb għall-ewwel numru għall-qawwa ta '2 li hija akbar minn jew ugwali għall-piż mogħti u ħu l-logaritmu binarju minnu. Dan jagħtina l-fond tas-siġra, jekk wieħed jassumi li hija bilanċjata. Is-siġra hija bilanċjata wara li ddaħħal element ġdid. Mhux se nagħti teorija dwar kif nibbilanċjaw is-siġar. Il-kodiċijiet tas-sors jipprovdu funzjoni ta' bilanċ.
Kodiċi għall-konverżjoni tal-piż għall-fond.
/*
* Возвращает первое число в степени 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));
}Riżultati ta '
- inserzjoni ta’ element ġdid iseħħ fi O (log n)
- it-tħassir ta' element bin-numru tas-serje jseħħ fi O (log n)
- il-ksib ta’ element b’numru tas-serje jseħħ fi O (log n)
Veloċità O (log n) Aħna nħallsu għall-fatt li d-dejta kollha hija maħżuna f'forma magħżula.
Ma nafx fejn struttura bħal din tista 'tkun utli. Just puzzle biex għal darb'oħra tifhem kif jaħdmu s-siġar. Grazzi tal-attenzjoni tiegħek.
referenzi
Il-proġett fih data tat-test biex tiċċekkja l-veloċità tat-tħaddim. Is-siġra qed timla 1000000 elementi. U hemm tħassir sekwenzjali, inserzjoni u rkupru ta 'elementi 1000000 darba. Jiġifieri 3000000 operazzjonijiet. Ir-riżultat irriżulta li kien pjuttost tajjeb ~ 8 sekondi.
Sors: www.habr.com