I tutaki ahau ki te momo raruraru e whai ake nei. He mea tika ki te whakatinana i tetahi ipu rokiroki raraunga e whakarato ana i nga mahi e whai ake nei:
- kōkuhu huānga hōu
- tango huānga mā te tau rangatū
- tiki huānga mā te tau ordinal
- ka penapena nga raraunga ki te ahua kua tohua
Ko nga raraunga kei te taapiri me te tango i nga wa katoa, me whakarite te hanganga i te tere o te mahi. I te tuatahi i whakamatau ahau ki te whakatinana i taua mea ma te whakamahi i nga ipu paerewa mai haora. Ko tenei huarahi kaore i karaunatia ki te angitu, ka tae mai te maaramatanga me whakatinana ahau i tetahi mea. Ko te mea anake i puta ki te hinengaro ko te whakamahi i te rakau rapu rua. Na te mea ka tutuki i te whakaritenga o te whakauru tere, te whakakore me te rokiroki o nga raraunga i roto i te ahua kua tohua. Ko nga mea e toe ana ko te whakaaro me pehea te tohu i nga huānga katoa me te tatau ano i nga tohu ina huri te rakau.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Ko te tuhinga ka nui ake nga pikitia me nga ariā i te waehere. Ka taea te tiro i te waehere i te hono i raro nei.
Taumaha
Hei whakatutuki i tenei, he iti te whakarereketanga o te rakau, ka taapirihia etahi atu korero mo taumaha kōpuku. Ko te taumaha node te maha o nga uri o tenei node + 1 (te taumaha o te huānga kotahi).
Taumahi mo te whiwhi taumaha node:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}He rite te taumaha o te rau ki te 0.
Muri iho, ka anga atu ki te whakaaturanga ataata o tetahi tauira o taua rakau. Pango ka whakaatuhia te kī node ki te tae (kaore e whakaatuhia te uara, na te mea kaore e tika ana), i roto i te whero - te taimaha o te hiku, kākāriki — taupū kōpuku.
Ka noho kau ta tatou rakau, he 0 tona taumaha. Me tapiri he huanga pakiaka ki roto:
Ko te taumaha o te rakau ka 1, ko te taumaha o te huanga pakiaka ka 1. Ko te taumaha o te huanga pakiaka ko te taumaha o te rakau.
Me taapiri etahi atu waahanga:
Ia wa ka taapirihia he huānga hou, ka heke tatou ki raro i nga pona ka whakanui ake i te porotiti taumaha o ia pona kua paahitia. Ina hangahia he node hou, ka tohua he taumaha ki a ia 1. Mēnā kei te noho kē he kōpuku me taua kī, ka tuhiruatia te uara ka hoki ki runga ki te putake, ka whakakore i nga huringa o nga taumahatanga o nga pona katoa kua paahitia.
Mena kei te tangohia tetahi node, ka heke iho ki raro ka whakaheke i nga taumaha o nga pona kua paahitia.
Ngā Tauira
Inaianei ka anga whakamua me pehea te tohu i nga node. Karekau nga node e tino penapena i o raatau taurangi, ka tatauhia i runga i te taumaha o nga node. Mena ka penapenahia e raatau ta raatau tohu, katahi ka hiahiatia E (n) te wa ki te whakahou i nga tohu o nga pona katoa i muri i ia huringa o te rakau.
Me neke tatou ki te whakaaturanga ataata. Kua kau ta tatou rakau, me tapiri te node tuatahi ki runga:
He taupū te kōpuku tuatahi 0, a inaianei e 2 nga keehi ka taea. I te tuatahi, ka huri te tohu o te huanga pakiaka, i te tuarua kaore e rereke.
I te putake, 1 te taumaha o te rakau iti maui.
Take tuarua:
Ko te taupū o te pakiaka karekau i rereke na te mea i noho 0 te taumaha o tana riuroto maui.
Ko te taupū o te kōpuku ka tātaihia ko te taumaha o tōna rākau iti mauī + te tau i tukuna mai i te matua. He aha tenei tau?, Ko te porotiti taurangi tenei, i te timatanga he rite ki 0, no te mea karekau he matua o te putake. Na ka whakawhirinaki katoa ki te waahi ka heke ki te tamaiti maui, ki te taha matau ranei. Mena kei te taha maui, kaore he mea ka taapiri atu ki te porotiti. Mēnā ka tāpirihia te taupū o te kōpuku o nāianei ki te taha matau.
Hei tauira, me pehea te tatau i te taupū o te huānga whai kī 8 (te tamaiti matau o te putake). Ko te "Taupapa Root" + "te taumaha o te rakau iti maui o te node me te taviri 8" + "1" == 3 + 2 + 1 == 6
Ko te taupū o te huānga me te kī 6 ko te "Root Index" + 1 == 3 + 1 == 4
No reira, ka roa te wa ki te tiki me te muku i tetahi huānga ma te taurangi O (takiuru n), na te mea kia whiwhi ai i te huānga e hiahiatia ana me rapu tuatahi (haere ki raro i te putake ki tenei huānga).
Te hohonu
I runga i te taumaha, ka taea hoki te tatau i te hohonu o te rakau. E tika ana mo te taurite.
Hei mahi i tenei, me whakaawhiwhia te taumaha o te node o naianei ki te tau tuatahi ki te mana o te 2 he nui ake, he rite ranei ki te taumaha kua hoatu, ka tango i te tauruarua mai i taua mea. Ma tenei e homai te hohonutanga o te rakau, me te whakaaro he taurite. Ka taurite te rakau i muri i te whakauru i tetahi huānga hou. E kore ahau e hoatu he ariā mo te whakataurite i nga rakau. Ka whakaratohia e nga waehere puna he mahi taurite.
Waehere mo te huri i te taumaha ki te hohonu.
/*
* Возвращает первое число в степени 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));
}Ngā putanga
- ka whakaurua he huānga hou ki roto O (takiuru n)
- ka mukua tetahi huānga ma te tau rangatū ka puta ki roto O (takiuru n)
- te whiwhi huānga mā te tau rangatū ka puta ki roto O (takiuru n)
Te tere O (takiuru n) Ka utua e matou mo te mea kei te rongoa nga raraunga katoa i roto i te ahua kua tohua.
Kaore au i te mohio kei hea te whai hua o taua hanganga. He panga noa kia mohio ano ki te mahi o nga rakau. Mauruuru koe mo to aro.
tohutoro
Kei roto i te kaupapa nga raraunga whakamatautau hei tirotiro i te tere o te mahi. Kei te whakakiia te rakau 1000000 huānga. A he whakakorenga raupapa, he whakauru me te tango i nga huānga 1000000 kotahi. Koira 3000000 mahi. Ko te hua ka puta he tino pai ~ 8 hēkona.
Source: will.com