Наишао сам на следећу врсту проблема. Неопходно је имплементирати контејнер за складиштење података који пружа следећу функционалност:
- уметните нови елемент
- уклонити елемент по серијском броју
- добити елемент по редном броју
- подаци се чувају у сортираном облику
Подаци се стално додају и уклањају, структура мора да обезбеди брзу брзину рада. У почетку сам покушао да имплементирам такву ствар користећи стандардне контејнере из стд. Овај пут није био крунисан успехом и дошло је схватање да треба нешто да спроведем сам. Једино што ми је пало на памет је коришћење бинарног стабла претраге. Зато што испуњава захтев брзог уметања, брисања и складиштења података у сортираном облику. Остаје само да смислите како да индексирате све елементе и поново израчунате индексе када се дрво промени.
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
Сходно томе, потребно је време да се добије и избрише елемент по индексу О (лог н), јер да бисмо добили жељени елемент морамо га прво пронаћи (сићи од корена до овог елемента).
Дубина
На основу тежине можете израчунати и дубину дрвета. Неопходан за балансирање.
Да би се то урадило, тежина тренутног чвора се мора заокружити на први број на степен 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));
}Резултати
- убацивање новог елемента долази у О (лог н)
- брисање елемента по серијском броју се јавља у О (лог н)
- добијање елемента по серијском броју јавља се у О (лог н)
Брзина О (лог н) Плаћамо чињеницу да се сви подаци чувају у сортираном облику.
Не знам где би таква структура могла бити корисна. Само загонетка да још једном разумемо како дрвеће функционише. Хвала на пажњи.
референце
Пројекат садржи тест податке за проверу брзине рада. Дрво се пуни 1000000 елемената. И постоји секвенцијално брисање, уметање и преузимање елемената 1000000 једном. То је 3000000 операције. Резултат се показао прилично добрим ~ 8 секунди.
Извор: ввв.хабр.цом