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

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

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

Данните непрекъснато се добавят и премахват, структурата трябва да осигурява бърза скорост на работа. Отначало се опитах да внедря такова нещо, използвайки стандартни контейнери от станд. Този път не беше увенчан с успех и дойде разбирането, че трябва да внедря нещо сам. Единственото нещо, което ми дойде на ум, беше да използвам двоично дърво за търсене. Тъй като отговаря на изискването за бързо вмъкване, изтриване и съхранение на данни в сортирана форма. Всичко, което остава, е да разберете как да индексирате всички елементи и да преизчислите индексите, когато дървото се промени.

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 (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 секунди.

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