Индексирано бинарно дрво

Наидов на следниот вид на проблем. Неопходно е да се имплементира контејнер за складирање податоци што ја обезбедува следната функционалност:

• вметнете нов елемент
• отстранете го елементот по сериски број
• добие елемент по реден број
• податоците се чуваат во сортирана форма

Податоците постојано се додаваат и отстрануваат, структурата мора да обезбеди брза брзина на работа. Отпрвин се обидов да имплементирам такво нешто користејќи стандардни контејнери од std. Овој пат не беше крунисан со успех и дојде разбирање дека треба сам да спроведам нешто. Единственото нешто што ми падна на ум беше да се користи бинарно дрво за пребарување. Бидејќи го исполнува условот за брзо вметнување, бришење и складирање на податоци во сортирана форма. Останува само да дознаеме како да ги индексираме сите елементи и повторно да ги пресметаме индексите кога дрвото се менува.

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. Ако веќе постои јазол со таков клуч, тогаш ќе ја презапишеме вредноста и ќе се вратиме назад до коренот, откажувајќи ги промените во тежините на сите јазли што ги поминавме.
Ако некој јазол се отстранува, тогаш се спуштаме и ги намалуваме тежините на поминатите јазли.

Индекси

Сега да продолжиме со тоа како да индексираме јазли. Јазлите не го складираат експлицитно нивниот индекс, тој се пресметува врз основа на тежината на јазлите. Ако тие го складирале својот индекс, тогаш тоа би било потребно Тој) време за ажурирање на индексите на сите јазли по секоја промена на дрвото.
Ајде да преминеме на визуелно претставување. Нашето дрво е празно, ајде да го додадеме првиот јазол на него:

Првиот јазол има индекс 0, а сега се можни 2 случаи. Во првиот, индексот на коренскиот елемент ќе се промени, во вториот нема да се промени.

Во коренот, левото поддрво тежи 1.

Втор случај:

Индексот на коренот не се промени бидејќи тежината на неговото лево поддрво остана 0.

Индексот на јазолот се пресметува како тежина на неговото лево подстебло + бројот што е пренесен од родителот. Која е оваа бројка?, Ова е бројач на индекси, првично е еднаков на 0, бидејќи коренот нема родител. Тогаш се зависи од тоа каде ќе се спуштиме до левото или десното дете. Ако лево, тогаш ништо не се додава на бројачот. Ако на десниот го додадеме индексот на тековниот јазол.

На пример, како се пресметува индексот на елемент со клуч 8 (десното дете на коренот). Ова е „Root Index“ + „тежина на левото поддрво на јазолот со клучот 8“ + „1“ == 3 + 2 + 1 == 6
Индексот на елементот со клуч 6 ќе биде „Root Index“ + 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 секунди.

Извор: www.habr.com