Pull to refresh

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

Reading time 15 min
Views 60K
Недавно мне понадобилось написать 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 и дерево осталось с теми свойствами, с которыми и должно быть.

На этом всё, спасибо за внимание.
Tags:
Hubs:
+34
Comments 14
Comments Comments 14

Articles