Ua loaʻa iaʻu kēia ʻano pilikia. Pono e hoʻokō i kahi pahu mālama data e hāʻawi ana i kēia mau hana:
- hoʻokomo i ka mea hou
- wehe i ka mea ma ka helu serial
- loaʻa i ka mea ma ka helu ordinal
- mālama ʻia ka ʻikepili ma ke ʻano koho
Hoʻohui mau ʻia ka ʻikepili a hoʻoneʻe ʻia, pono e hōʻoia ka hana i ka wikiwiki o ka hana. I ka wā mua ua ho'āʻo wau e hoʻokō i ia mea me ka hoʻohana ʻana i nā ipu maʻamau mai ok. ʻAʻole i lei ʻia kēia ala me ka holomua a ua hiki mai ka ʻike e pono iaʻu e hoʻokō i kekahi mea iaʻu iho. ʻO ka mea wale nō i komo i ka noʻonoʻo ʻo ka hoʻohana ʻana i kahi lāʻau huli binary. No ka mea e hoʻokō i ke koi o ka hoʻokomo wikiwiki ʻana, ka holoi ʻana a me ka mālama ʻana i nā ʻikepili ma ke ʻano i hoʻokaʻawale ʻia. ʻO nā mea a pau i koe e noʻonoʻo pehea e kuhikuhi ai i nā mea a pau a helu hou i nā helu i ka wā e loli ai ka lāʻau.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};E loaʻa i ka ʻatikala nā kiʻi a me ke kumumanaʻo ma mua o ke code. Hiki ke ʻike ʻia ke code ma ka loulou ma lalo nei.
ʻO ke kaumaha
No ka hoʻokō ʻana i kēia, ua hoʻololi iki ka lāʻau, ua hoʻohui ʻia ka ʻike hou aku e pili ana kaumaha node. ʻO ke kaumaha o ka node helu o na mamo o keia node + 1 (kaumaha o ka mea hookahi).
Hana no ka loaʻa ʻana o ke kaumaha node:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Ua like ke kaumaha o ka pepa me 0.
A laila, e neʻe kākou i kahi hiʻohiʻona ʻike o kahi laʻana o ia lāʻau. ʻeleʻele e hōʻike ʻia ke kī node i ke kala (ʻaʻole e hōʻike ʻia ka waiwai, no ka mea ʻaʻole pono kēia), i ʻulaʻula - kaumaha puʻupuʻu, ʻōmaʻomaʻo — helu kuhikuhi node.
Ke haʻahaʻa kā mākou kumulāʻau, ʻo 0 kona kaumaha. E hoʻohui kākou i kahi kumu kumu iā ia:
Lilo ke kaumaha o ke kumu i 1, lilo ke kaumaha o ke kumu i 1. ʻO ke kaumaha o ke kumu kumu ke kaumaha o ka lāʻau.
E hoʻohui i kekahi mau mea hou aʻe:
I kēlā me kēia manawa e hoʻohui ʻia kahi mea hou, e iho mākou i lalo i nā node a hoʻonui i ka helu paona o kēlā me kēia node i hala. Ke hana ʻia kahi node hou, hāʻawi ʻia kahi paona iā ia 1. Inā loaʻa kahi node me ia kī, a laila e kākau hou mākou i ka waiwai a hoʻi i luna i ke kumu, e kāpae ana i nā loli i nā paona o nā nodes a pau i hala.
Inā wehe ʻia kahi node, a laila iho mākou i lalo a hoʻemi i nā paona o nā node i hala.
Papa Kuhikuhi
I kēia manawa e neʻe kākou i ka pehea e kuhikuhi ai i nā nodes. ʻAʻole mālama pono nā nodes i kā lākou papa kuhikuhi, ua helu ʻia ma muli o ke kaumaha o nā nodes. Inā mālama lākou i kā lākou index, a laila pono ia ʻO (n) manawa e hoʻololi i nā kuhikuhi o nā nodes a pau ma hope o kēlā me kēia hoʻololi i ka lāʻau.
E neʻe kākou i kahi hōʻike kiʻi. ʻAʻohe kā mākou kumu lāʻau, e hoʻohui i ka node 1 iā ia:
Loaʻa i ka node mua kahi kuhikuhi 0, a hiki i kēia manawa 2 mau hihia. I ka mua, e loli ka index o ke kumu kumu, i ka lua ʻaʻole ia e loli.
Ma ke kumu, he 1 ke kaumaha o ka subtree hema.
ʻO ka hihia ʻelua:
ʻAʻole i loli ka papa kuhikuhi o ke kumu no ka mea he 0 ke kaumaha o kona kumulāʻau hema.
Ua helu ʻia ka papa kuhikuhi o kahi node e like me ke kaumaha o kāna kumulāʻau hema + ka helu i hala mai ka makua. He aha kēia helu?, ʻO kēia ka helu helu helu, i ka mua ua like ia me 0, no ka mea ʻaʻohe makua o ke kumu. A laila pili ia i kahi e iho ai mākou i ke keiki hema a i ʻole ke keiki ʻākau. Inā ma ka hema, ʻaʻohe mea i hoʻohui ʻia i ka counter. Inā mākou e hoʻohui i ka index o ka node o kēia manawa i ka ʻākau.
No ka laʻana, pehea e helu ʻia ai ka papa kuhikuhi o kahi mea me ke kī 8 (ke keiki ʻākau o ke kumu). ʻO kēia ka "Root Index" + "kaumaha o ka subtree hema o ka node me ke kī 8" + "1" == 3 + 2 + 1 == 6
ʻO ka papa kuhikuhi o ka mea me ke kī 6 ʻo ia ka "Root Index" + 1 == 3 + 1 == 4
No laila, pono ka manawa e kiʻi a holoi i kahi mea e ka index ʻO (ʻeʻe n), no ka loaʻa ʻana o ka mea i makemake ʻia e loaʻa mua iā mākou (e iho i lalo mai ke kumu a hiki i kēia mea).
Hōʻike
Ma muli o ke kaumaha, hiki iā ʻoe ke helu i ka hohonu o ka lāʻau. Pono no ke kaulike.
No ka hana ʻana i kēia, pono e hoʻopuni ʻia ke kaumaha o ka node o kēia manawa i ka helu mua i ka mana o 2 i ʻoi aku ka nui a i ʻole like me ka paona i hāʻawi ʻia a lawe i ka logarithm binary mai ia mea. Hāʻawi kēia iā mākou i ka hohonu o ka lāʻau, me ka manaʻo he kaulike. Kaulike ka lāʻau ma hope o ka hoʻokomo ʻana i kahi mea hou. ʻAʻole wau e hāʻawi i ka manaʻo e pili ana i ke kaulike ʻana i nā lāʻau. Hāʻawi nā code kumu i kahi hana kaulike.
Code no ka hoʻololi ʻana i ke kaumaha i ka 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));
}Nā hopena
- hoʻokomo ʻia kahi mea hou i loko ʻO (ʻeʻe n)
- e holoi ana i kekahi mea ma ka helu serial ʻO (ʻeʻe n)
- ka loaʻa ʻana o kahi mea ma ka helu serial ʻO (ʻeʻe n)
Ka māmā holo ʻO (ʻeʻe n) Uku mākou no ka mālama ʻia ʻana o nā ʻikepili a pau ma ke ʻano i koho ʻia.
ʻAʻole maopopo iaʻu kahi e pono ai kēlā ʻano hana. He puʻupuʻu wale nō e hoʻomaopopo hou i ka hana ʻana o nā lāʻau. Mahalo no kou noonoo.
kūmole
Aia ka papahana i ka ʻikepili hoʻāʻo e nānā i ka wikiwiki o ka hana. Ke piha nei ka laau 1000000 mau mea. A aia kahi holoi ʻana, hoʻokomo a hoʻihoʻi i nā mea 1000000 pākahi. ʻo ia 3000000 nā hana. Ua maikaʻi loa ka hopena ~ 8 kekona.
Source: www.habr.com