Индексирано двоично дърво

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

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

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

Следващото, ще преминем към визуализация на примера за такова дърво. Черно цветом в него ще бъде показан ключът на възела (стойността няма да бъде показвана, тъй като това не е необходимо), червено — тегло на възела, зеленo — индекс на възела.

Когато дървото е празно, теглото му е равно на 0. Нека добавим кореновия елемент:

Теглото на дървото става 1, теглото на кореновия елемент е 1. Теглото на кореновия елемент е теглото на дървото.

Да добавим още няколко елемента:

Всеки път, когато се добавя нов елемент, слизаме надолу през възлите и увеличаваме брояча на теглото на всеки преминал възел. При създаването на нов възел му се присвоява тегло 1. Ако възел с такъв ключ вече съществува, записваме стойността отново и се върнем нагоре до корена, отменяйки промените на теглата на всички възли, които сме преминали.
Ако се изтрива възел, слизаме надолу и декрементираме теглата на преминалите възли.

Индекси

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

Първият възел има индекс 0, а сега имаме два случая. В първия индексът на кореновия елемент ще се промени, а във втория няма да се промени.

Коренът има ляво поддърво с тегло 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