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

Срещнах задача от следния вид. Необходимо е да се реализира контейнер за съхранение на данни, който да осигурява следната функционалност:

• вмъкване на нов елемент
• изтриване на елемент по пореден номер
• получаване на елемент по пореден номер
• данните се съхраняват в сортиран вид

Данните постоянно се добавят и изтриват, структурата трябва да осигури бърза скорост на работа. Първоначално се опитах да реализирам нещо такова, използвайки стандартни контейнери от 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. Ако възел с такъв ключ вече съществува, то презаписваме стойността и се връщаме обратно до корена, отменяйки промените на теглата на всички възли, които сме преминали.
Ако се изтрива възел, тогава слизаме надолу и декрементираме теглата на преминатите възли.

Индекси

Сега преминаваме към начина на индексиране на възлите. Възлите очевидно не съхраняват своя индекс, той се изчислява на базата на тежестта на възлите. Ако те съхраняваха своя индекс, щеше да е нужно O(n) време, за да се актуализират индекси на всички възли след всяка промяна в дървото.
Преминете към нагледно представяне. Нашето дърво е празно, добавяме първия възел:

Първият възел има индекс 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 секунди.

Източник: habr.com