2-3-дерево. Наївна реалізація

Недавно мені знадобилося написати 2-3-дерево і я почав шукати інформацію в російськомовному інтернеті. На жаль, ні на хабре, ні на інших ресурсах я не зміг знайти досить повну інформацію російською мовою. На всіх ресурсах було одне і те ж: властивості дерева, як вставляються ключі в дерево, пошук у дереві і іноді простий приклад, як віддаляється ключ з дерева; не було реалізації.

Тому, після того, як я зробив те, що мені потрібно, вирішив написати цю статтю. Думаю, комусь буде корисна в освітніх цілях, так як на практиці зазвичай реалізують еквівалент 2-3 — й 2-3-4-дерев   красно-чорне дерево.

Вступна частина
Ті, хто знають, що таке бінарне дерево пошуку і його недоліки, що можуть гортати далі — нічого нового тут не буде.

Більшості програмістів (і не тільки) відомо таке дерево як бінарне дерево пошуку. У цього дерева дуже прості властивості:

  • Обидва піддерева — ліве і праве — є двійковими деревами пошуку.
  • У всіх вузлів лівого піддерева довільного вузла X значення ключів даних менше, ніж значення ключа даних самого вузла X.
  • У той час, як значення ключів даних у всіх вузлів правого піддерева (того ж вузла X) більше або дорівнює, ніж значення ключа даних вузла X.
Дерева пошуку використовують тоді, коли потрібно дуже часто виконувати операцію пошук. У звичайному дереві пошуку є дуже великий недолік: коли на вхід отримуємо відсортовані дані, наше дерево стає звичайним масивом:

image

І тоді операція пошук здійснюватиметься за таку ж складність, як і в масиві, — за O(n), де n — кількість елементів у масиві.

Є кілька способів, як можна звичайне дерево зробити збалансованим (пошук має складність O(log n)). Про це дуже добре написано в двох статтях від хабраюзера nickme: рандомізовані дерева пошуку і АВЛ-дерева.

Загальні властивості 2-3-дерева
Визначення з wiki:

2-3-дерево — структура даних, що є B-деревом Ступеня 1, сторінки якого можуть містити тільки 2-вершини (вершини з одним полем і 2 дітьми) і 3-вершини (вершини з 2 полями і дітьми 3). Листові вершини є винятком — у них немає дітей (але може бути одне або два поля). 2-3-дерева збалансовані, тобто, кожне ліве, праве, і центральне піддерево має одну і ту ж висоту, і, таким чином, містять рівні або майже рівні) обсяги даних.

Властивості:

  • Всі нелистовые вершини містять одне поле і 2 піддерева або 2 поля і 3 піддерева.
  • Всі листові вершини знаходяться на одному рівні (на нижньому рівні) і містять 1 або 2 поля.
  • Всі дані відсортовані (за принципом бінарного дерева пошуку).
  • Нелистовые вершини містять одне або два поля, що вказують на діапазон значень їх поддеревьях. Значення першого поля строго більше найбільшого значення в лівому поддереве і менше або дорівнює найменшому значенню в правому поддереве (або в центральному поддереве, якщо це 3-вершина); аналогічно, значення другого поля (якщо воно є) строго більше найбільшого значення в центральному поддереве і менше або дорівнює, ніж найменше значення в правому поддереве. Ці нелистовые вершини використовуються для направлення функції пошуку потрібного поддереву і, в кінцевому підсумку, до потрібного аркуша. (прим. Це властивість не буде виконуватися, якщо у нас є однакові ключі. Тому можлива ситуація, коли рівні ключі знаходяться в лівому і правому поддеревьях одночасно, тоді ключ в нелистовой вершині буде збігатися з цими ключами. Це ніяк не позначається на правильності роботи і продуктивності алгоритму.).
Приклад 2-3-дерева:

image
Для простоти будемо використовувати різні ключі

Подання дерева в коді
Я буду писати на так званому «Сі з класами», так як я сам програміст на Сі, але мені шалено подобаються такі речі в С++, як конструктори, наявність членів-методів класу і дружні функції.

Вершини нашого дерева будемо представляти у вигляді 4-вершин (це коли вершина може мати 3 ключа і 4 сина). Дане рішення було обрано з декількох причин: по-перше, так легше зробити наївну (пряму) реалізацію, а по-друге, код та так сильно обрамлений if'ами і це рішення дозволило зменшити кількість перевірок і спростити код.

Ось так виглядає подання вершини:

Клас для вершини 2-3-дерева
struct node {
private:
int size; // кількість зайнятих ключів
int key[3]; 
node *first; // *first <= key[0];
node *second; // key[0] <= *second < key[1];
node *third; // key[1] <= *third < key[2];
node *fourth; // kye[2] <= *fourth.
node *parent; //Вказівник на батька потрібен для того, тому що адреса кореня може змінюватися при видаленні

bool find(int k) { // Цей метод повертає true, якщо ключ k знаходиться у вершині, інакше false.
for (int i = 0; i < size; i++)
if (key[i] == k) return true;
return false;
}

void swap(int &x, int &y) {
int r = x;
x = y;
y = r;
}

void sort2(int &x, int &y) { 
if (x > y) swap(x, y);
}

void sort3(int &x, int &y, int &z) {
if (x > y) swap(x, y);
if (x > z) swap(x, z);
if (y > z) swap(y, z);
}

void sort() { // Ключі в вершинах повинні бути відсортовані
if (size == 1) return;
if (size == 2) sort2(key[0], key[1]);
if (size == 3) sort3(key[0], key[1], key[2]);
}

void insert_to_node(int k) { // Вставляємо ключ k у вершину (дерево)
key[size] = k;
size++;
sort();
}

void remove_from_node(int k) { // Видаляємо ключ k з вершини (не з дерева)
if (size >= 1 && key[0] == k) {
key[0] = key[1];
key[1] = key[2];
size--;
} else if (size == 2 && key[1] == k) {
key[1] = key[2];
size--;
}
}

void become_node2(int k, node *first_, node *second_) { // Перетворити в 2-вершину.
key[0] = k;
first = first_;
second = second_;
third = nullptr;
fourth = nullptr;
parent = nullptr;
size = 1;
}

bool is_leaf() { // чи Є вузол листом; перевірка використовується при вставки та видалення.
return (first == nullptr) && (second == nullptr) && (third == nullptr);
}

public:
// Створювати завжди будемо вершину тільки з одним ключем
node(int k): size(1), key{k, 0, 0}, first(nullptr), second(nullptr),
third(nullptr), fourth(nullptr), parent(nullptr) {}

node (int k, node *first_, node *second_, node *third_, node *fourth_, node *parent_):
size(1), key{k, 0, 0}, first(first_), second(second_),
third(third_), fourth(fourth_), parent(parent_) {}

friend node *split(node *item); // Метод для розділення вершини при переповненні;
friend node *insert(node *p, int k); // Вставка в дерево;
friend node *search(node *p, int k); // Пошук у дереві;
friend node *search_min(node *p); // Пошук мінімального елемента в поддереве; 
friend node *merge(node *leaf); // Злиття використовується при видаленні;
friend node *redistribute(node *leaf); // Перерозподіл також використовується при видаленні;
friend node *fix(node *leaf); // Використовується після видалення повернути властивостей дереву (використовує merge або redistribute) 
friend node *remove(node *p, int k); // Власне, з назви зрозуміло;
};


Вставити
Для того, щоб вставити в дерево елемента з ключем key, потрібно діяти за алгоритмом:

  1. Якщо дерево порожнє, то створити нову вершину, вставити ключ і повернути в якості кореня цю вершину, інакше
  2. Якщо вершина є листом, то вставляємо ключ в цю вершину і якщо отримали 3 ключа у вершині, то поділяємо її, інакше
  3. Порівнюємо ключ key з першим ключем у вершині, і якщо key менше даного ключа, то йдемо в перше дерево і переходимо до кроку 2, інакше
  4. Дивимося, якщо вершина містить тільки 1 ключ (є 2-вершиною), то йдемо в праве піддерево і переходимо до кроку 2, інакше
  5. Порівнюємо ключ key з другим ключем у вершині, і якщо key менше другого ключа, то йдемо в середнє дерево і переходимо до кроку 2, інакше
  6. Йдемо в праве піддерево і переходимо до пункту 2.
Для прикладу вставимо keys = {1, 2, 3, 4, 5, 6, 7}:

При вставці key=1 ми маємо порожнє дерево, а після отримуємо єдину вершину з єдиним ключа key=1:

image

Далі вставляємо key=2:

image

Тепер вставляємо key=3 і отримуємо вершину, що містить 3 ключа:

image

Так як ця вершина порушує властивості 2-3-дерева, то ми повинні з цим розібратися. А розберемося з цим ось таким поділом: ключ, який знаходиться в середині (в нашому випадку key=2), перенесемо на батьківську вершину на відповідне місце, або якщо у нас єдина вершина в дереві, то вона відповідно є і коренем дерева — значить, ми створюємо нову вершину і переносимо туди середній ключ key = 2, а решта ключі сортуємо і робимо їх синами нового кореня:

image

Далі за алгоритмом вставляємо key=4:

image

Key=5:

image

Знову порушився властивості 2-3 дерева, робимо поділ:

image

Key=6:

image

Key=7:

image

Тепер нам належить зробити два поділи, оскільки вершина, в яку вставили новий ключ тепер має 3 ключа (спочатку розділимо її):

image

А тепер і корінь має 3 вершини — розділимо його і отримаємо збалансоване дерево, яке при таких вхідних даних із звичайним двійковим деревом пошуку ми б не змогли отримати:

image

Вставка ключа
node *insert(node *p, int k) { // вставка ключа k у дерево з коренем p; завжди повертаємо корінь дерева, т. к. він може змінюватися
if (!p) return new node(k); // якщо дерево порожнє, то створюємо першу 2-3-вершину (корінь)

if (p->is_leaf()) p->insert_to_node(k);
else if (k <= p>key[0]) insert(p->first, k);
else if ((p>size == 1) || ((p>size == 2) && k <= p>key[1])) insert(p->second, k);
else insert(p->third, k);

return split(p);
}


Поділ вершини
node *split(node *item) {
if (item->size < 3) return item;

node *x = new node(item->key[0], item->first, item->second, nullptr, nullptr, item->parent); // Створюємо дві нові вершини,
node *y = new node(item->key[2], item->third, item->fourth, nullptr, nullptr, item->parent); // які мають такого ж батька, як і разделяющийся елемент.
if (x->first) x->first->parent = x; // Правильно встановлюємо "батьків" "синів".
if (x->second) x->second->parent = x; // Після поділу, "батьком" "синів" є "дідусь",
if (y->first) y->first->parent = y; // Тому потрібно правильно встановити покажчики.
if (y->second) y->second->parent = y;

if (item->parent) {
item->parent->insert_to_node(item->key[1]);

if (item->parent->first == item) item->parent->first = nullptr;
else if (item->parent->second == item) item->parent->second = nullptr;
else if (item->parent->third == item) item->parent->third = nullptr;

// Далі відбувається своєрідна сортування ключів при поділі.
if (item->parent->first == nullptr) {
item->parent->fourth = item->parent->third;
item->parent->third = item->parent->second;
item->parent->second = y;
item->parent->first = x;
} else if (item->parent->second == nullptr) {
item->parent->fourth = item->parent->third;
item->parent->third = y;
item->parent->second = x;
} else {
item->parent->fourth = y;
item->parent->third = x;
}

node *tmp = item->parent;
delete item;
return tmp;
} else {
x->parent = item; // Так як в цю гілку потрапляє тільки корінь,
y->parent = item; // то ми "батьком" нових вершин робимо разделяющийся елемент.
item->become_node2(item->key[1], x, y);
return item;
}
}


Пошук
Пошук такий же простий, як і в бінарному дереві пошуку:

  1. Шукаємо шуканий ключ key в поточній вершині, якщо знайшли, то повертаємо вершину, інакше
  2. Якщо key менше першого ключа вершини, то йдемо в ліве піддерево і переходимо до пункту 1, інакше
  3. Якщо в дереві 1 ключ, то йдемо в праве піддерево (середнє, якщо керуватися нашим класом) і переходимо до пункту 1, інакше
  4. Якщо key менше другого ключа вершини, то йдемо в середнє дерево і переходимо до пункту 1, інакше
  5. Йдемо в праве піддерево і переходимо до пункту 1.
Пошук ключа
node *search(node *p, int k) { // Пошук ключа k в 2-3 дерево з коренем p.
if (!p) return nullptr;

if (p->find(k)) return p;
else if (k < p>key[0]) return search ("p>first, k);
else if ((p>size == 2) && (k < p>key[1]) || (p->size == 1)) return search ("p>second, k);
else if (p->size == 2) return search ("p>third, k);
}


Видалити
Видалення в 2-3-дереві, як і в будь-якому іншому дереві, відбувається тільки з аркуша (з самої нижньої вершини). Тому, коли ми знайшли ключ, який потрібно видалити, спочатку треба перевірити, чи знаходиться цей ключ до листової або нелистовой вершині. Якщо ключ знаходиться в нелистовой вершині, то потрібно знайти еквівалентний ключ для видаляється ключа з листової вершини і поміняти їх місцями. Для знаходження еквівалентного ключа є два варіанти: або знайти максимальний елемент в лівому поддереве, або знайти мінімальний елемент у правому поддереве. Давайте оберемо другий варіант, так як він мені більше подобається. Наприклад:

image

Щоб видалити із дерева ключ key=4, для початку потрібно знайти еквівалентний ему елемент і поміняти місцями: це або key=3, або key=5. Так як я вибрав другий спосіб, то міняю ключі key=4 і key=5 місцями і видаляю key=4 з аркуша («тире» буде позначати місце ключа, який ми видалили):

image

Пошуку мінімального ключа
node *search_min(node *p) { // Пошук вузла з мінімальним елементів в 2-3-дерево з коренем p.
if (!p) return p;
if (!(p->first)) return p;
else return search_min(p->first);
}


Видалення ключа
node *remove(node *p, int k) { // Видалення ключа k в 2-3-дерево з коренем p.
node *item = search(p, k); // Шукаємо вузол, де знаходиться ключ k

if (!item) return p;

node *min = nullptr;
if (item->key[0] == k) min = search_min(item->second); // Шукаємо еквівалентний ключ
else min = search_min(item->third);

if (min) { // Змінюємо місцями ключі
int &z = (k == item->key[0] ? item->key[0] : item->key[1]);
item->swap(z, min->key[0]);
item = min; // Переміщаємо курсор на лист, т. к. min - завжди лист
}

item->remove_from_node(k); // видаляємо необхідний ключ з листа
return fix(item); // Викликаємо функцію для відновлення властивостей дерева.
}


Після того, як видалили ключ, у нас можуть вийти концептуально 4 різні ситуації: 3 з них порушують властивості дерева, а одна — ні. Тому для вершини, з якої видалили ключ, потрібно викликати функцію виправлення fix(), яка поверне властивості 2-3 дерева. Випадки, які описуються функції, що розглядаються нижче.

Виправлення дерева після видалення ключа
node *fix(node *leaf) {
if (leaf->size == 0 && leaf->parent == nullptr) { // Випадок 0, коли видаляємо єдиний ключ в дереві
delete leaf;
return nullptr;
}
if (leaf->size != 0) { // Випадок 1, коли вершина, в якій видалили ключ, мала два ключа
if (leaf->parent) return fix(leaf->parent);
else return leaf;
}

node *parent = leaf->parent;
if (parent->first->size == 2 || parent->second->size == 2 || parent->size == 2) leaf = redistribute(leaf); // Випадок 2, коли достатньо перерозподілити ключі в дереві
else if (parent->size == 2 && parent->third->size == 2) leaf = redistribute(leaf); // Аналогічно
else leaf = merge(leaf); // Випадок 3, коли потрібно провести склеювання і пройтися вверх по дереву як мінімум на ще одну вершину

return fix(leaf);
}


Тепер перейдемо до можливих варіантів, які можуть з'явитися після видалення ключа. Для простоти будемо розглядати випадки, де глибина дерева дорівнює 2. Загальний випадок — це дерево з глибиною дорівнює трьом. Тоді буде зрозуміло, як впоратися з видаленням ключа в дереві з будь-якою глибиною. Що ми і зробимо в підсумковому прикладі для більшості ситуацій. А поки приступимо до приватним випадків.

Випадок 0:

Найпростіший випадок, також як і наступний, на які вистачить і одного речення, щоб зрозуміти: якщо дерево складається з однієї вершини (корінь), яка має 1 ключ, то просто видаляємо цю вершину. The end.

Випадок 1:

Якщо потрібно видалити ключ з листа, де знаходяться два ключа, то ми просто видаляємо ключ і на цьому функція видалення закінчена.
Видалимо key=4:

image-> image-> image

Випадок 2 (розподіл або redistribute):

Ми видаляємо ключ з вершини і вершина стає порожньою. Якщо хоча б у одного з братів є 2 ключа, то робимо просту правильне розподіл і робота закінчена. Під правильним розподілом я маю на увазі, що при циклічному зсуві ключів між батьком і синами також потрібно буде переміщати і онуків батьків. Перерозподіляти ключі можна з любого брата, але зручніше за все з близького, який має 2 ключа, при цьому ми циклічно зсуваємо всі ключі, наприклад з прикладу нижче видалимо key=1:

image-> image-> image

Або ось другий приклад: у нас батько має 2 ключі, відповідно 3 сина, і ми видалимо key=4. Перерозподіл у нашому прикладі можна зробити як з лівого брата, так і з правого; я вибрав з лівого:

image-> image-> image-> image->

-> image

Як бачимо, властивості дерева збережені.

Перерозподіл
node *redistribute(node *leaf) {
node *parent = leaf->parent;
node *first = parent->first;
node *second = parent->second;
node *third = parent->third;

if ((parent->size == 2) && (first->size < 2) && (second->size < 2) && (third->size < 2)) {
if (first == leaf) {
parent->first = parent->second;
parent->second = parent->third;
parent->third = nullptr;
parent->first->insert_to_node(parent->key[0]);
parent->first->third = parent->first->second;
parent->first->second = parent->first->first;

if (leaf->first != nullptr) parent->first->first = leaf->first;
else if (leaf->second != nullptr) parent->first->first = leaf->second;

if (parent->first->first != nullptr) parent->first->first->parent = parent->first;

parent->remove_from_node(parent->key[0]);
delete first;
} else if (second == leaf) {
first->insert_to_node(parent->key[0]);
parent->remove_from_node(parent->key[0]);
if (leaf->first != nullptr) first->third = leaf->first;
else if (leaf->second != nullptr) first->third = leaf->second;

if (first->third != nullptr) first->third->parent = first;

parent->second = parent->third;
parent->third = nullptr;

delete second;
} else if (third == leaf) {
second->insert_to_node(parent->key[1]);
parent->third = nullptr;
parent->remove_from_node(parent->key[1]);
if (leaf->first != nullptr) second->third = leaf->first;
else if (leaf->second != nullptr) second->third = leaf->second;

if (second->third != nullptr) second->third->parent = second;

delete third;
}
} else if ((parent->size == 2) && ((first->size == 2) || (second->size == 2) || (third->size == 2))) {
if (third == leaf) {
if (leaf->first != nullptr) {
leaf->second = leaf->first;
leaf->first = nullptr;
}

leaf->insert_to_node(parent->key[1]);
if (second->size == 2) {
parent->key[1] = second->key[1];
second->remove_from_node(second->key[1]);
leaf->first = second->third;
second->third = nullptr;
if (leaf->first != nullptr) leaf->first->parent = leaf;
} else if (first->size == 2) {
parent->key[1] = second->key[0];
leaf->first = second->second;
second->second = second->first;
if (leaf->first != nullptr) leaf->first->parent = leaf;

second->key[0] = parent->key[0];
parent->key[0] = first->key[1];
first->remove_from_node(first->key[1]);
second->first = first->third;
if (second->first != nullptr) second->first->parent = second;
first->third = nullptr;
}
} else if (second == leaf){
if (third->size == 2) {
if (leaf->first == nullptr) {
leaf->first = leaf->second;
leaf->second = nullptr;
}
second->insert_to_node(parent->key[1]);
parent->key[1] = third->key[0];
third->remove_from_node(third->key[0]);
second->second = third->first;
if (second->second != nullptr) second->second->parent = second;
third->first = third->second;
third->second = third->third;
third->third = nullptr;
} else if (first->size == 2) {
if (leaf->second == nullptr) {
leaf->second = leaf->first;
leaf->first = nullptr;
}
second->insert_to_node(parent->key[0]);
parent->key[0] = first->key[1];
first->remove_from_node(first->key[1]);
second->first = first->third;
if (second->first != nullptr) second->first->parent = second;
first->third = nullptr;
}
} else if (first == leaf) {
if (leaf->first == nullptr) {
leaf->first = leaf->second;
leaf->second = nullptr;
}
first->insert_to_node(parent->key[0]);
if (second->size == 2) {
parent->key[0] = second->key[0];
second->remove_from_node(second->key[0]);
first->second = second->first;
if (first->second != nullptr) first->second->parent = first;
second->first = second->second;
second->second = second->third;
second->third = nullptr;
} else if (third->size == 2) {
parent->key[0] = second->key[0];
second->key[0] = parent->key[1];
parent->key[1] = third->key[0];
third->remove_from_node(third->key[0]);
first->second = second->first;
if (first->second != nullptr) first->second->parent = first;
second->first = second->second;
second->second = third->first;
if (second->second != nullptr) second->second->parent = second;
third->first = third->second;
third->second = third->third;
third->third = nullptr;
}
}
} else if (parent->size == 1) {
leaf->insert_to_node(parent->key[0]);

if (first == leaf && second->size == 2) {
parent->key[0] = second->key[0];
second->remove_from_node(second->key[0]);

if (leaf->first == nullptr) leaf->first = leaf->second;

leaf->second = second->first;
second->first = second->second;
second->second = second->third;
second->third = nullptr;
if (leaf->second != nullptr) leaf->second->parent = leaf;
} else if (second == leaf && first->size == 2) {
parent->key[0] = first->key[1];
first->remove_from_node(first->key[1]);

if (leaf->second == nullptr) leaf->second = leaf->first;

leaf->first = first->third;
first->third = nullptr;
if (leaf->first != nullptr) leaf->first->parent = leaf;
}
}
return parent;
}


Випадок 3 (склеювання або merge):

Мабуть, самий складний випадок, так як після склеювання завжди обов'язково йти по дереву вгору і знову застосовувати операції або merge, або redistribute. Після redistribute алгоритм відновлення властивостей 2-3-дерева після видалення ключа можна припинити, так як вершини в цій операції не видаляються.

Для початку подивимося, як видалити ключ key=3 з вершини, батько якої має тільки двох синів (~ 1 ключ):

image-> image-> image-> image-> image

Що ж ми зробили? Ми видалили ключ key=3. Потім нам потрібно перенести ключ з батька на сина, де ключ є: в даному випадку у лівого сина. Потім потрібно видалити вершину, з якої видалили ключ. І останній крок — це перевірити, якщо батько був коренем дерева, то видалити цей корінь і призначити новий коренем ту вершину, куди ми перенесли ключ, інакше доведеться викликати функцію виправлення fix() вже для батьків. Виглядає легко.

Тепер розглянемо два варіанти, коли батько має 2 ключі. У першому варіанті видалимо key=3 (з середнього сина):

image-> image-> image-> image

Що ми зробили на цей раз? Ми знову перенесли ключ батьків (вже один з двох) до сина і видалили сина, який не має ключів. Так як батько мав 2 ключа, то перевіряти, чи був батько коренем, не потрібно. В описаному вище випадку алгоритм виправлення такий: потрібно перенести менший ключ батька в піддерево з меншими ключами або більший ключ в піддерево з великими ключами, і видалити вершину без ключів. Ще приклад, видалимо key=1:

image-> image-> image-> image

Склеювання
node *merge(node *leaf) {
node *parent = leaf->parent;

if (parent->first == leaf) {
parent->second->insert_to_node(parent->key[0]);
parent->second->third = parent->second->second;
parent->second->second = parent->second->first;

if (leaf->first != nullptr) parent->second->first = leaf->first;
else if (leaf->second != nullptr) parent->second->first = leaf->second;

if (parent->second->first != nullptr) parent->second->first->parent = parent->second;

parent->remove_from_node(parent->key[0]);
delete parent->first;
parent->first = nullptr;
} else if (parent->second == leaf) {
parent->first->insert_to_node(parent->key[0]);

if (leaf->first != nullptr) parent->first->third = leaf->first;
else if (leaf->second != nullptr) parent->first->third = leaf->second;

if (parent->first->third != nullptr) parent->first->third->parent = parent->first;

parent->remove_from_node(parent->key[0]);
delete parent->second;
parent->second = nullptr;
}

if (parent->parent == nullptr) {
node *tmp = nullptr;
if (parent->first != nullptr) tmp = parent->first;
else tmp = parent->second;
tmp->parent = nullptr;
delete parent;
return tmp;
}
return parent;
}


! Важливо! При склеюванні або перерозподіл нелистовой вершини потрібно буде також склеювати і/або перерозподіляти синів братів.

Підсумковий приклад видалення ключів:

Підібрав приклад такий, щоб можна було побачити основні випадки (крім випадку 0). Для початку вставимо ключі keys={10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 5, 15, 25, 8} в порожнє дерево і отримаємо:

image

Тепер видалимо по порядку ключі keys={5, 8, 10, 30, 15}.

Після видалення ключа key=5 отримуємо:

image

Видаляємо key=8:

image

Тепер key=10:

image

Key=30:

image

І, нарешті, key=15. Так як тут відбувається при виправленні дерева операція merge, то подивимося на всі кроки.

Крок 1. Вид дерева відразу після першого дзвінка fix():

image

Крок 2. Другий виклик fix():

image

Крок 3. Третій виклик fix():

image

Крок 4. Останній виклик fix():

image

Ось так ми видалили ключ key=15 і дерево залишилося з тими властивостями, з якими і повинно бути.

На цьому все, спасибі за увагу.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.