Ke ile ka kopana le bothata ba mofuta o latelang. Hoa hlokahala ho kenya ts'ebetso ea polokelo ea data e fanang ka ts'ebetso e latelang:
- kenya elemente e ncha
- tlosa element ka nomoro ea serial
- fumana element ka nomoro ea ordinal
- data e bolokoa ka mokhoa o hlophisitsoeng
Lintlha li lula li eketsoa le ho tlosoa, sebopeho se tlameha ho netefatsa lebelo la ts'ebetso e potlakileng. Qalong ke ile ka leka ho kenya ts'ebetsong ntho e joalo ke sebelisa lijana tse tloaelehileng ho tloha lihora. Tsela ena ha ea ka ea hlophisoa ka katleho mme kutloisiso e ile ea tla ea hore ke hloka ho kenya ts'ebetsong ho hong ka bonna. Ntho feela e ileng ea tla kelellong ke ho sebelisa sefate sa ho batla sa binary. Hobane e kopana le tlhokahalo ea ho kenya ka potlako, ho hlakola le ho boloka data ka mokhoa o hlophisitsoeng. Sohle se setseng ke ho fumana mokhoa oa ho supa likarolo tsohle le ho bala li-indices ha sefate se fetoha.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Sengoliloeng se tla ba le litšoantšo le maikutlo a mangata ho feta khoutu. Khoutu e ka bonoa sehokelong se ka tlase.
Boima ba 'mele
Ho finyella sena, sefate se ile sa e-ba le phetoho e nyenyane, boitsebiso bo eketsehileng bo ile ba eketsoa ka boima node. Boima ba node ke palo ea litloholo tsa node ena + 1 (boima ba ntho e le nngwe).
Mosebetsi oa ho fumana boima ba node:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Boima ba lakane bo lekana le 0.
Ka mor'a moo, a re feteleng pele ho setšoantšo se bonahalang sa mohlala oa sefate se joalo. Ntsho senotlolo sa node se tla bontšoa ka 'mala (boleng bo ke ke ba bontšoa, kaha sena ha se hlokahale), bofubelu - boima ba 'mele, botala - index ea li-node.
Ha sefate sa rona se se na letho, boima ba sona ke 0. Ha re kenye karolo ea motso ho sona:
Boima ba sefate bo fetoha 1, boima ba motsoako oa motsoako bo fetoha 1. Boima ba motsoako oa motsoako ke boima ba sefate.
Ha re kenye lintlha tse ling tse 'maloa:
Nako le nako ha ntho e ncha e eketsoa, re theola li-node ebe re eketsa k'hamera ea boima ba node e 'ngoe le e' ngoe e fetisitsoeng. Ha node e ncha e thehoa, boima bo abeloa ho eona 1. Haeba node e nang le senotlolo se joalo e se e ntse e le teng, joale re tla hlakola boleng ebe re khutlela motsong, re hlakola liphetoho tsa boima ba li-node tsohle tseo re li fetisitseng.
Haeba node e tlosoa, joale re theoha ebe re fokotsa boima ba li-node tse fetisitsoeng.
Li-index
Joale a re tsoeleng pele ho mokhoa oa ho index nodes. Li-node ha li boloke index ea tsona ka ho hlaka, e baloa ho latela boima ba li-node. Haeba ba ne ba bolokile index ea bona, ho ne ho tla hlokahala O (n) nako ea ho ntlafatsa li-index tsa li-node tsohle ka mor'a phetoho e 'ngoe le e' ngoe sefateng.
Ha re feteleng ho setšoantšo sa pono. Sefate sa rona ha se na letho, a re kenyeng node ea 1 ho sona:
Node ea pele e na le index 0, 'me joale linyeoe tse 2 lia khoneha. Ntlha ea pele, index ea motsoako oa metso e tla fetoha, ea bobeli e ke ke ea fetoha.
Motsong, sefate se ka ho le letšehali se boima ba 1.
Taba ea bobeli:
Lenane la motso ha lea ka la fetoha hobane boima ba sefate sa eona se letšehali se ile sa lula 0.
Index ea node e baloa e le boima ba sefate sa eona se letšehali + palo e fetisitsoeng ho motsoali. Nomoro ee ke eng?, Ena ke index counter, qalong e lekana le 0, hobane motso ha o na motsoali. Joale ho itšetlehile ka hore na re theohela kae ho ngoana ea letšehali kapa ea nepahetseng. Haeba ka ho le letšehali, joale ha ho letho le kenyelletsoang k'haontareng. Haeba re eketsa index ea node ea hona joale ho e nepahetseng.
Mohlala, index ea element e nang le senotlolo 8 (ngoana ea nepahetseng oa motso) e baloa joang. Ena ke "Root Index" + "boima ba subtree e ka letsohong le letšehali le senotlolo sa 8" + "1" == 3 + 2 + 1 == 6
Lenane la ntho e nang le senotlolo sa 6 e tla ba "Root Index" + 1 == 3 + 1 == 4
Ka hona, ho nka nako ho fumana le ho hlakola element ka index O (log n), hobane e le hore re fumane ntho e lakatsehang re tlameha ho e fumana pele (theoha ho tloha motsong ho ea ho ntho ena).
Botebo
Ho itšetlehile ka boima ba 'mele, u ka boela ua bala botebo ba sefate. Ho hlokahala bakeng sa ho leka-lekanya.
Ho etsa sena, boima ba node ea hona joale e tlameha ho pota-potiloe ho nomoro ea pele ho matla a 2 a maholo ho feta kapa a lekanang le boima bo fanoeng ebe o nka logarithm ea binary ho eona. Sena se tla re fa botebo ba sefate, ho nka hore bo leka-lekane. Sefate se leka-lekana ka mor'a ho kenya ntho e ncha. Nke ke ka fana ka khopolo ea ho leka-lekanya lifate. Likhoutu tsa mohloli li fana ka ts'ebetso ea ho leka-lekanya.
Khoutu ea ho fetola boima ho ea botebong.
/*
* Возвращает первое число в степени 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));
}Liphello
- ho kenya elemente e ncha ho etsahala ho O (log n)
- ho hlakola element ka nomoro ea seriale ho etsahala ka O (log n)
- ho fumana element ka nomoro ea serial ho etsahala ka O (log n)
Lebelo O (log n) Re lefella taba ea hore data eohle e bolokiloe ka mokhoa o hlophisitsoeng.
Ha ke tsebe moo sebopeho se joalo se ka bang molemo. Ke papali feela ea ho utloisisa hore na lifate li sebetsa joang. Kea leboha ha u mametse.
litšupiso
Morero o na le lintlha tsa tlhahlobo ho lekola lebelo la ts'ebetso. Sefate sea tlala 1000000 likarolo. 'Me ho na le ho hlakoloa ka tatellano, ho kenngoa le ho khutlisa likarolo 1000000 hang. Ke hore 3000000 ts'ebetso. Sephetho se ile sa fetoha hantle ~ metsotsoana e 8.
Source: www.habr.com