Na ou tau atu i le ituaiga o faafitauli nei. E mana'omia le fa'atinoina o se atigipusa e teu ai fa'amaumauga e maua ai galuega nei:
- fa'aofi elemene fou
- aveese elemene ile numera fa'asologa
- maua le elemene ile numera fa'asologa
- fa'amaumauga o lo'o teuina ile fa'avasegaina
O faʻamatalaga e faʻaopoopoina ma aveese i taimi uma, o le fausaga e tatau ona faʻamautinoa le saoasaoa o le gaioiga. I le taimi muamua sa ou taumafai e faʻatino se mea faapena e faʻaaoga ai pusa masani mai itula. O lenei ala e leʻi faapaleina i le manuia ma na oʻo mai le malamalama e tatau ona ou faʻatinoina se mea e aʻu lava. Na o le pau lava le mea na oʻo mai i lou mafaufau o le faʻaaogaina o se laʻau suʻesuʻe binary. Aua e fetaui ma le manaʻoga o le faʻapipiʻi vave, tapeina ma le teuina o faʻamaumauga i le faʻavasegaina. Pau lava le mea o loʻo totoe o le mafaufau pe faʻafefea ona faʻavasega elemene uma ma toe faʻatusatusa faʻailoga pe a suia le laʻau.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};O le tusiga o le a tele atu ata ma manatu nai lo code. E mafai ona va'aia le code ile so'oga i lalo.
Pauna
Ina ia ausia lenei mea, o le laau na faia se suiga laʻititi, faʻaopoopo faʻamatalaga faaopoopo e uiga i mamafa node. O le mamafa o le node numera o suli o lenei node + 1 (mamafa o se elemene e tasi).
Galuega mo le mauaina o le mamafa o le node:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Ole mamafa ole laupepa e tutusa lelei ile 0.
Sosoo ai, se'i o tatou agai atu i se ata vaaia o se faataitaiga o se laau faapena. Lanu uliuli o le ki node o le a faʻaalia i le lanu (o le a le faʻaalia le tau, talu ai e le manaʻomia), mumu - mamafa nonoa, lanu meamata - fa'ailoga node.
A gaogao la tatou laau, o lona mamafa o le 0. Sei o tatou faaopoopo i ai se aa elemene:
O le mamafa o le laau e avea ma 1, o le mamafa o le aʻa e avea ma 1. O le mamafa o le aʻa o le mamafa o le laau.
Sei o tatou faaopoopo nisi elemene:
O taimi uma e fa'aopoopoina ai se elemene fou, matou te alu ifo i lalo ma fa'ateleina le fata mamafa o pona ta'itasi ua pasia. A faia se node fou, e tu'uina atu i ai se mamafa 1. Afai o loʻo i ai se node e iai sea ki, o le a tatou toe faʻamauina le tau ma toe foʻi i luga i le aʻa, faʻaleaogaina suiga i le mamafa o nodes uma na tatou pasia.
Afai e aveese se node, ona tatou o ifo lea i lalo ma faaitiitia le mamafa o nodes ua pasia.
Faasino igoa
Se'i o tatou aga'i atu i le auala e fa'asino ai nodes. Nodes e le teuina manino a latou faasinoupu, e fuafua i luga o le mamafa o nodes. Afai latou te teuina a latou faasino igoa, ona manaʻomia lea Le (n) taimi e fa'afou ai fa'ailoga o nodes uma pe a uma suiga ta'itasi i le la'au.
Sei o tatou agai atu i se ata vaaia. Ua gaogao la tatou laau, sei tatou faaopoopo i ai le node muamua:
O le node muamua e iai se faasino igoa 0, ma o lea ua 2 mataupu e mafai. I le muamua, o le faasino igoa o le elemene aʻa o le a suia, i le lona lua o le a le suia.
I le a'a, o le la'au agavale e 1 le mamafa.
Mataupu lona lua:
E le'i suia le fa'ailoga o le a'a ona o le mamafa o lona la'au agavale na tumau 0.
O le faasinoupu o se node e fa'atatau i le mamafa o lona la'au agavale + le numera na pasi mai le matua. O le a lenei numera?, O le fa'ailoga fa'ailoga, muamua e tutusa ma 0, ona o le a’a e leai sona matua. Ona faalagolago uma lea i le mea tatou te alu ifo i lalo i le tamaititi agavale poʻo le taumatau. Afai i le agavale, ona leai lea o se mea e faʻaopoopo i le fata. Afai tatou te faʻaopoopoina le faʻailoga o le node o loʻo i ai nei i le saʻo.
Mo se fa'ata'ita'iga, pe fa'apefea ona fa'atatauina le fa'ailoga o se elemene ma le ki 8 (le tama taumatau o le a'a). Ole "Root Index" + "mamafa ole la'au agavale ole node ma le ki 8" + "1" == 3 + 2 + 1 == 6
O le faasinoupu o le elemene ma le ki 6 o le a avea ma "Root Index" + 1 == 3 + 1 == 4
E tusa ai, e manaʻomia le taimi e maua ma tape ai se elemene e ala ile faʻasino O(loga n), aua ina ia maua le elemene manaʻomia e tatau ona tatou mauaina muamua (alu i lalo mai le aʻa i lenei elemene).
Paʻu
Faʻavae i luga o le mamafa, e mafai foi ona e fuafuaina le loloto o le laau. Manaomia mo le faapaleniina.
Ina ia faia lenei mea, o le mamafa o le node o loʻo i ai nei e tatau ona lapotopoto i le numera muamua i le mana o le 2 lea e sili atu pe tutusa ma le mamafa tuʻuina atu ma ave le logarithm binary mai ai. O lenei mea o le a maua ai le loloto o le laau, ma le manatu e paleni. E paleni le laau pe a uma ona tuʻuina se elemene fou. O le a ou le tuuina atu se manatu e uiga i le auala e faapaleni ai laau. O tulafono fa'apogai e maua ai se galuega paleni.
Code mo le faaliliuina o le mamafa i le loloto.
/*
* Возвращает первое число в степени 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));
}O taunuʻuga
- fa'aofiina o se elemene fou e tupu i totonu O(loga n)
- o le tapeina o se elemene ile numera fa'asologa e tupu ile O(loga n)
- mauaina o se elemene e ala ile numera fa'asologa e tupu ile O(loga n)
Saosaoa O(loga n) Matou te totogia le mea moni o faʻamaumauga uma o loʻo teuina i le faʻavasegaina.
Ou te le iloa po o fea e aoga ai se fausaga faapena. Na'o se paso e toe malamalama ai i le auala e galue ai laau. Faafetai mo lou gauai mai.
mau
O le poloketi o loʻo i ai faʻamatalaga suʻega e siaki ai le saoasaoa o le gaioiga. Ua tumu le laau 1000000 elemene. Ma o loʻo i ai se faʻasologa faʻasolosolo, faʻaofiina ma toe maua mai elemene 1000000 fa'atasi. O lena lava 3000000 fa'agaioiga. O le iʻuga na faʻaalia e matua lelei lava ~ 8 sekone.
puna: www.habr.com