Індэксаванае бінарнае дрэва

Трапілася мне задача наступнага віду. Неабходна рэалізаваць кантэйнер захоўвання дадзеных які забяспечвае наступны функцыянал:

• уставіць новы элемент
• выдаліць элемент па парадкавым нумары
• атрымаць элемент па парадкавым нумары
• дадзеныя захоўваюцца ў сартаваць выглядзе

Дадзеныя ўвесь час дадаюцца і выдаляюцца, структура павінна забяспечваць хуткую хуткасць працы. Спачатку спрабаваў рэалізаваць такую ​​рэч выкарыстоўваючы стандартныя кантэйнеры з станд. Гэты шлях не меў поспеху і прыйшло разуменне, што трэба рэалізоўваць нешта самому. Адзінае што прыйшло на розум, гэта выкарыстоўваць бінарнае дрэва пошуку. Паколькі яно адказвае патрабаванню хуткай устаўкі, выдаленню і захоўванню дадзеных у сартаваць выглядзе. Засталося толькі прыдумаць як праіндэксаваць усе элементы і пералічваць індэксы калі дрэва мяняецца.

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 (правый ребенок корня). Это «Индекс корня» + «вес левого поддерева узла с ключом 8» + «1» == 3 + 2 + 1 == 6
Індэксам элемента з ключом 6 будзе "Індэкс кораня" + 1 == 3 + 1 == 4

Адпаведна што б атрымаць, выдаліць элемент па азначніку патрабуецца час O (часопіс 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 (часопіс n)
• выдаленне элемента па парадкавым нумары адбываецца за O (часопіс n)
• атрыманне элемента па парадкавым нумары адбываецца за O (часопіс n)

Хуткасцю O (часопіс n) плацім за тое, што ўсе дадзеныя захоўваюцца ў сартаваным выглядзе.

Дзе можа спатрэбіцца такая структура - не ведаю. Проста задача, што б яшчэ раз разабрацца як працуюць дрэвы. Дзякуй за ўвагу.

Спасылкі

• Зыходны код дрэва

У праекце змяшчаюцца тэставыя дадзеныя для праверкі хуткасці працы. Дрэва запаўняецца 1000000 элементаў. І адбываецца паслядоўнае выдаленне, устаўка і атрыманне элементаў 1000000 раз. Гэта значыць 3000000 аперацый. Вынік аказаўся цалкам нядрэнным ~ 8 секунд.

Крыніца: habr.com