Ман бо намуди зерини мушкилот дучор омадам. Зарур аст, ки як контейнери нигоҳдории маълумот, ки функсияҳои зеринро таъмин мекунад:
- элементи нав ворид кунед
- элементро бо рақами силсилавӣ хориҷ кунед
- элементро аз рӯи рақами тартибӣ гиред
- маълумот дар шакли мураттаб нигоҳ дошта мешавад
Маълумот пайваста илова ва хориҷ карда мешавад, сохтор бояд суръати тези корро таъмин кунад. Дар аввал ман кӯшиш кардам, ки чунин чизеро бо истифода аз контейнерҳои стандартӣ амалӣ кунам ист. Ин роҳ бо муваффақият тоҷ нашуд ва фаҳмид, ки ман бояд чизеро худам амалӣ кунам. Ягона чизе, ки ба хотир омад, истифодаи дарахти ҷустуҷӯии бинарӣ буд. Зеро он ба талаботи зуд ворид кардан, нест кардан ва нигоҳ доштани маълумот дар шакли мураттабшуда ҷавобгӯ аст. Танҳо фаҳмидани он, ки чӣ гуна ҳамаи элементҳоро индексатсия кардан ва аз нав ҳисоб кардани индексҳо ҳангоми тағир додани дарахт боқӣ мемонад.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Дар мақола тасвирҳо ва назария бештар аз рамз иборат хоҳад буд. Рамзро дар истиноди зерин дидан мумкин аст.
Вазн
Барои ноил шудан ба ин, дарахт каме тағир дода шуд, маълумоти иловагӣ дар бораи он илова карда шуд вазн гиреҳ. Вазни гиреҳ аст шумораи авлоди ин гиреҳ + 1 (вазни як элемент).
Функсия барои гирифтани вазни гиреҳ:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Вазни варақ мувофиқан ба он баробар аст 0.
Минбаъд, биёед ба тасвири визуалии намунаи чунин дарахт гузарем. Сиёҳ калиди гиреҳ бо ранг нишон дода мешавад (арзиш нишон дода намешавад, зеро ин зарур нест), сурх - вазни гиреҳ, сабз - индекси гиреҳ.
Вақте ки дарахти мо холӣ аст, вазни он 0 аст. Биёед ба он унсури реша илова кунем:
Вазни дарахт 1 мешавад, вазни унсури реша 1 мешавад. Вазни унсури реша вазни дарахт аст.
Биёед якчанд унсурҳои дигар илова кунем:
Ҳар дафъае, ки элементи нав илова карда мешавад, мо гиреҳҳоро ба поён мерасонем ва ҳисобкунаки вазни ҳар як гиреҳи гузаштаро зиёд мекунем. Вақте ки гиреҳи нав сохта мешавад, ба он вазн таъин карда мешавад 1. Агар гиреҳ бо чунин калид мавҷуд бошад, пас мо арзишро аз нав менависем ва ба реша бармегардем ва тағиротро дар вазнҳои ҳамаи гиреҳҳои гузаштаамон бекор мекунем.
Агар гиреҳ хориҷ карда шавад, мо ба поён меравем ва вазни гиреҳҳои гузаштаро кам мекунем.
Нишондиҳандаҳо
Акнун биёед ба тарзи индексатсия кардани гиреҳҳо гузарем. Гиреҳҳо индекси худро ба таври возеҳ нигоҳ намедоранд, он аз рӯи вазни гиреҳҳо ҳисоб карда мешавад. Агар онҳо индекси худро нигоҳ медоштанд, он гоҳ талаб карда мешавад Эй (н) вақти навсозии шохиси ҳамаи гиреҳҳо пас аз ҳар як тағирот дар дарахт.
Биёед ба тасвири визуалӣ гузарем. Дарахти мо холист, биёед гиреҳи 1-ро ба он илова кунем:
Дар гиреҳи аввал индекс дорад 0, ва ҳоло 2 ҳолат имконпазир аст. Дар аввал, индекси элементи реша тағир меёбад, дар дуюм он тағир намеёбад.
Дар реша, зердарахти чап 1 вазн дорад.
Ҳолати дуюм:
Индекси реша тағир наёфт, зеро вазни зердарахти чапи он 0 боқӣ монд.
Индекси гиреҳ ҳамчун вазни зердарахти чапи он + рақами аз волидайн гузашташуда ҳисоб карда мешавад. Ин рақам чист?, Ин ҳисобкунаки индекс аст, дар аввал ба он баробар аст 0, зеро реша волидайн надорад. Он гоҳ ҳама аз он вобаста аст, ки мо дар куҷо ба кӯдаки чап ё рост меравем. Агар ба чап, пас ба ҳисобкунак чизе илова карда намешавад. Агар индекси гирехи чориро ба тарафи рост илова кунем.
Масалан, чӣ гуна индекси элемент бо калиди 8 (кӯчаки рости реша) ҳисоб карда мешавад. Ин "Индекси решавӣ" + "вазни зердарахти чапи гиреҳ бо калиди 8" + "1" == 3 + 2 + 1 == 6
Индекси элемент бо калиди 6 "Индекси решавӣ" + 1 == 3 + 1 == хоҳад буд. 4
Мувофиқи ин, барои гирифтан ва нест кардани элемент аз рӯи индекс вақт лозим аст O (log n), зеро барои ба даст овардани элементи дилхоҳ мо бояд аввал онро пайдо кунем (аз реша ба ин элемент поён равем).
Умуман
Дар асоси вазн, шумо инчунин метавонед чуқурии дарахтро ҳисоб кунед. Барои мувозинат зарур аст.
Барои ин вазни гиреҳи ҷорӣ бояд ба адади якум ба дараҷаи 2, ки аз вазни додашуда зиёд ё баробар аст, мудаввар карда, аз он логарифми дуӣ гирифта шавад. Ин ба мо умқи дарахтро медиҳад, агар он мутавозин бошад. Дарахт пас аз ворид кардани унсури нав мувозинат карда мешавад. Ман дар бораи чӣ гуна мувозинати дарахтон назария намедиҳам. Рамзҳои манбаъ вазифаи мувозинатро таъмин мекунанд.
Рамз барои табдил додани вазн ба амиқ.
/*
* Возвращает первое число в степени 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 (log n)
- нест кардани элемент аз рӯи рақами силсилавӣ дар O (log n)
- ба даст овардани элемент аз рӯи рақами силсилавӣ дар рух медиҳад O (log n)
Суръат O (log n) Мо барои он пардохт мекунем, ки ҳама маълумот дар шакли мураттаб нигоҳ дошта мешавад.
Ман намедонам, ки чунин сохтор дар куҷо муфид бошад. Танҳо як муаммо барои бори дигар фаҳмидани он ки чӣ тавр дарахтон кор мекунанд. Ба диққататон ташаккур.
мурожиат
Лоиҳа дорои маълумоти санҷишӣ барои тафтиши суръати кор мебошад. Дарахт пур мешавад 1000000 унсурҳо. Ва ҳазфкунии пайдарпай, воридкунӣ ва ҷустуҷӯи элементҳо вуҷуд дорад 1000000 як бор. Яъне 3000000 амалиёт. Натиҷа хеле хуб буд ~ 8 сония.
Манбаъ: will.com