Попалося мені завдання такого виду. Необхідно реалізувати контейнер зберігання даних, що забезпечує наступний функціонал:
- вставити новий елемент
- видалити елемент за порядковим номером
- отримати елемент за порядковим номером
- дані зберігаються у сортованому вигляді
Дані постійно додаються та видаляються, структура повинна забезпечувати швидку швидкість роботи. Спочатку намагався реалізувати таку річ використовуючи стандартні контейнери з 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 (права дитина кореня). Це "Індекс кореня" + "вага лівого піддерева вузла з ключем 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