Рубрики

Дерево Ван Эмде Боаса | Набор 4 | делеция

Настоятельно рекомендуется сначала прочитать предыдущие статьи о Van Emde Boas Tree .

Процедура удаления:
Здесь мы предполагаем, что ключ уже присутствует в дереве.

  • Сначала мы проверяем, присутствует ли только один ключ, затем назначаем максимум и минимум дерева нулевому значению, чтобы удалить ключ.
  • Базовый случай: если размер юниверса дерева равен двум, то после того, как вышеприведенное условие наличия только одного ключа является ложным, в дереве присутствует ровно два ключа (после того, как вышеприведенное условие окажется ложным), поэтому удалите запрос ключ, назначая максимум и минимум дерева другому ключу, присутствующему в дереве.
  • Рекурсивный случай:
    • Если ключ является минимумом дерева, найдите следующий минимум дерева, назначьте его как минимум дерева и удалите ключ запроса.
    • Теперь ключ запроса отсутствует в дереве. Нам придется изменить остальную часть структуры в дереве, чтобы полностью исключить ключ:
    1. Если минимум кластера ключа запроса равен нулю, мы также удалим его из сводки. Также, если ключ является максимумом дерева, мы найдем новый максимум и назначим его как максимум дерева.
    2. В противном случае, если ключ является максимумом дерева, найдите новый максимум и назначьте его как максимум дерева.

Ниже приведена серия изображений, представляющих «запрос на удаление ключа-0» по дереву VEB с 0, 1, 2 ключами:

Шаг 1: поскольку 0 является минимумом дерева, оно будет удовлетворять первому условию остальной части алгоритма.
Сначала он находит следующий максимум, равный 1, и устанавливает его как минимум.

Шаг 2: Теперь он удалит ключ 1 из кластера [0].

Шаг 3: Следующее условие, кластер [0] не имеет ключа, имеет значение true, поэтому он также удалит ключ из сводки.

#include <bits/stdc++.h>

using namespace std;

  

class Van_Emde_Boas {

  

public:

    int universe_size;

    int minimum;

    int maximum;

    Van_Emde_Boas* summary;

    vector<Van_Emde_Boas*> clusters;

  

    // Функция для возврата номеров кластеров

    // в каком ключе присутствует

    int high(int x)

    {

        int div = ceil(sqrt(universe_size));

        return x / div;

    }

  

    // Функция для возврата позиции х в кластере

    int low(int x)

    {

        int mod = ceil(sqrt(universe_size));

        return x % mod;

    }

  

    // Функция для возврата индекса из

    // номер кластера и позиция

    int generate_index(int x, int y)

    {

        int ru = ceil(sqrt(universe_size));

        return x * ru + y;

    }

  

    // Конструктор

    Van_Emde_Boas(int size)

    {

        universe_size = size;

        minimum = -1;

        maximum = -1;

  

        // Базовый вариант

        if (size <= 2) {

            summary = nullptr;

            clusters = vector<Van_Emde_Boas*>(0, nullptr);

        }

        else {

            int no_clusters = ceil(sqrt(size));

  

            // Назначение VEB (sqrt (u)) для сводки

            summary = new Van_Emde_Boas(no_clusters);

  

            // Создание массива указателей дерева VEB размером sqrt (u)

            clusters = vector<Van_Emde_Boas*>(no_clusters, nullptr);

  

            // Назначаем VEB (sqrt (u)) всем его кластерам

            for (int i = 0; i < no_clusters; i++) {

                clusters[i] = new Van_Emde_Boas(ceil(sqrt(size)));

            }

        }

    }

};

  
// Функция для возврата минимального значения
// из дерева, если оно существует

int VEB_minimum(Van_Emde_Boas* helper)

{

    return (helper->minimum == -1 ? -1 : helper->minimum);

}

  
// Функция для возврата максимального значения
// из дерева, если оно существует

int VEB_maximum(Van_Emde_Boas* helper)

{

    return (helper->maximum == -1 ? -1 : helper->maximum);

}

  
// Функция для вставки ключа в дерево

void insert(Van_Emde_Boas* helper, int key)

{

    // Если в дереве нет ключа

    // затем устанавливаем минимум и максимум

    // к ключу (прочитайте предыдущую статью

    // для лучшего понимания)

    if (helper->minimum == -1) {

        helper->minimum = key;

        helper->maximum = key;

    }

    else {

        if (key < helper->minimum) {

  

            // Если ключ меньше текущего минимума

            // затем меняем его на текущий минимум

            // потому что этот минимум на самом деле

            // минимум одного внутреннего кластера

            // так, как мы углубляемся в Ван Эмде Боас

            // мы должны принять этот минимум к его реальной позиции

            // Эта концепция похожа на «Ленивое распространение»

            swap(helper->minimum, key);

        }

  

        // Тогда не базовый случай ...

        if (helper->universe_size > 2) {

  

            // Если в кластере нет ключа, вставьте ключ в

            // и кластер и сводка

            if (VEB_minimum(helper->clusters[helper->high(key)]) == -1) {

                insert(helper->summary, helper->high(key));

  

                // Устанавливает минимум и максимум кластера для ключа

                // поскольку других ключей нет, мы остановимся на этом уровне

                // мы не углубляемся в структуру вроде

                // Ленивое распространение

                helper->clusters[helper->high(key)]->minimum = helper->low(key);

                helper->clusters[helper->high(key)]->maximum = helper->low(key);

            }

            else {

                // Если в дереве есть другие элементы, то рекурсивно

                // углубляемся в структуру, чтобы установить соответствующие атрибуты

                insert(helper->clusters[helper->high(key)], helper->low(key));

            }

        }

  

        // Устанавливает ключ как максимум, который больше текущего максимума

        if (key > helper->maximum) {

            helper->maximum = key;

        }

    }

}

  
// Функция, которая возвращает true, если
// ключ присутствует в дереве

bool isMember(Van_Emde_Boas* helper, int key)

{

  

    // если размер_интервала меньше ключа

    // тогда мы не можем искать ключ, поэтому возвращает

    // ложный

    if (helper->universe_size < key) {

        return false;

    }

  

    // Если в любой момент нашего обхода

    // дерева, если ключ минимальный

    // или максимум поддерева, тогда

    // ключ присутствует, поэтому возвращает true

    if (helper->minimum == key || helper->maximum == key) {

        return true;

    }

    else {

  

        // Если после выполнения вышеуказанного условия,

        // если размер дерева равен 2, то

        // текущий ключ должен быть

        // максимум или минимум дерева, если оно

        // нет, то возвращает false, потому что ключ

        // не может присутствовать в поддереве

        if (helper->universe_size == 2) {

            return false;

        }

        else {

  

            // Рекурсивный вызов по кластеру

            // в котором может присутствовать ключ

            // а также передать новую позицию ключа

            // т.е. низкий (ключ)

            return isMember(helper->clusters[helper->high(key)],

                            helper->low(key));

        }

    }

}

  
// Функция поиска преемника данного ключа

int VEB_successor(Van_Emde_Boas* helper, int key)

{

  

    // Базовый случай: если ключ равен 0 и его преемник

    // присутствует, затем возвращает 1, иначе возвращает ноль

    if (helper->universe_size == 2) {

  

        if (key == 0 && helper->maximum == 1) {

            return 1;

        }

        else {

            return -1;

        }

    }

  

    // Если ключ меньше минимума, вернуть минимум

    // потому что это будет преемник ключа

    else if (helper->minimum != -1 && key < helper->minimum) {

  

        return helper->minimum;

    }

    else {

  

        // Найти преемника внутри кластера ключа

        // Сначала найти максимум в кластере

        int max_incluster = VEB_maximum(helper->clusters[helper->high(key)]);

  

        int offset{ 0 }, succ_cluster{ 0 };

  

        // Если в кластере есть какой-либо ключ (максимум! = - 1), то найти

        // преемник внутри кластера

        if (max_incluster != -1 && helper->low(key) < max_incluster) {

  

            offset = VEB_successor(helper->clusters[helper->high(key)],

                                   helper->low(key));

  

            return helper->generate_index(helper->high(key), offset);

        }

  

        // В противном случае ищем следующий кластер, где есть хотя бы один ключ

        else {

  

            succ_cluster = VEB_successor(helper->summary, helper->high(key));

  

            // Если нет кластера с каким-либо ключом

            // в итоге потом возвращаем ноль

            if (succ_cluster == -1) {

                return -1;

            }

  

            // Находим минимум в последующем кластере, который будет

            // быть преемником ключа

            else {

  

                offset = VEB_minimum(helper->clusters[succ_cluster]);

  

                return helper->generate_index(succ_cluster, offset);

            }

        }

    }

}

  
// Функция для поиска предшественника данного ключа

int VEB_predecessor(Van_Emde_Boas* helper, int key)

{

  

    // Базовый случай: если ключ 1 и его предшественник

    // присутствует, затем возвращает 0, иначе возвращает ноль

    if (helper->universe_size == 2) {

  

        if (key == 1 && helper->minimum == 0) {

            return 0;

        }

        else

            return -1;

    }

  

    // Если ключ больше максимума дерева, то

    // вернуть ключ, так как он будет предшественником ключа

    else if (helper->maximum != -1 && key > helper->maximum) {

  

        return helper->maximum;

    }

    else {

  

        // Найти предшественника в кластере ключа

        // Сначала находим минимум в ключе, чтобы проверить, есть ли ключ

        // присутствует в кластере

        int min_incluster = VEB_minimum(helper->clusters[helper->high(key)]);

  

        int offset{ 0 }, pred_cluster{ 0 };

  

        // Если в кластере присутствует какой-либо ключ, найдите предшественника в

        // кластер

        if (min_incluster != -1 && helper->low(key) > min_incluster) {

  

            offset = VEB_predecessor(helper->clusters[helper->high(key)],

                                     helper->low(key));

  

            return helper->generate_index(helper->high(key), offset);

        }

  

        // В противном случае ищите предшественника в сводке, которая

        // возвращает индекс кластера предшественника с любым ключом

        else {

  

            pred_cluster = VEB_predecessor(helper->summary, helper->high(key));

  

            // Если нет предшествующего кластера, тогда ...

            if (pred_cluster == -1) {

  

                // Особый случай из-за ленивого распространения

                if (helper->minimum != -1 && key > helper->minimum) {

                    return helper->minimum;

                }

  

                else

                    return -1;

            }

  

            // Иначе найти максимум в кластере предшественника

            else {

  

                offset = VEB_maximum(helper->clusters[pred_cluster]);

  

                return helper->generate_index(pred_cluster, offset);

            }

        }

    }

}

  
// Функция для удаления ключа из дерева
// при условии, что ключ присутствует

void VEB_delete(Van_Emde_Boas* helper, int key)

{

  

    // Если присутствует только один ключ, это означает

    // что это ключ, который мы хотим удалить

    // То же состояние, что и ключ == max && key == min

    if (helper->maximum == helper->minimum) {

  

        helper->minimum = -1;

        helper->maximum = -1;

    }

  

    // Базовый случай: если вышеприведенное условие неверно

    // т.е. дерево имеет более двух ключей

    // и если его размер равен двум, то дерево имеет ровно два ключа.

    // Мы просто удаляем его, назначая другому

    // текущее значение ключа

    else if (helper->universe_size == 2) {

  

        if (key == 0) {

            helper->minimum = 1;

        }

        else {

            helper->minimum = 0;

        }

        helper->maximum = helper->minimum;

    }

    else {

  

        // Как мы делаем что-то похожее на ленивое распространение

        // мы в основном найдем следующий больший ключ

        // и назначаем как минимум

        if (key == helper->minimum) {

  

            int first_cluster = VEB_minimum(helper->summary);

  

            key

                = helper->generate_index(first_cluster,

                                         VEB_minimum(helper->clusters[first_cluster]));

  

            helper->minimum = key;

        }

  

        // Теперь мы удаляем ключ

        VEB_delete(helper->clusters[helper->high(key)],

                   helper->low(key));

  

        // После удаления ключа остальные улучшения

  

        // Если минимум в кластере ключа -1

        // тогда мы должны удалить его из резюме

        // полностью исключить ключ

        if (VEB_minimum(helper->clusters[helper->high(key)]) == -1) {

  

            VEB_delete(helper->summary, helper->high(key));

  

            // После вышеуказанного условия, если ключ

            // это максимум дерева тогда ...

            if (key == helper->maximum) {

                int max_insummary = VEB_maximum(helper->summary);

  

                // Если максимальное значение сводки равно нулю

                // тогда присутствует только один ключ, так

                // назначаем мин. до макс.

                if (max_insummary == -1) {

  

                    helper->maximum = helper->minimum;

                }

                else {

  

                    // Назначаем глобальный максимум дерева после удаления

                    // наш ключ запроса

                    helper->maximum

                        = helper->generate_index(max_insummary,

                                                 VEB_maximum(helper->clusters[max_insummary]));

                }

            }

        }

  

        // Просто найдите новый максимальный ключ и

        // устанавливаем максимум дерева

        // до нового максимума

        else if (key == helper->maximum) {

  

            helper->maximum

                = helper->generate_index(helper->high(key),

                                         VEB_maximum(helper->clusters[helper->high(key)]));

        }

    }

}

  
// Код драйвера

int main()

{

    Van_Emde_Boas* end = new Van_Emde_Boas(8);

  

    // Вставка ключей

    insert(end, 1);

    insert(end, 0);

    insert(end, 2);

    insert(end, 4);

  

    // перед удалением

    cout << isMember(end, 2) << endl;

    cout << VEB_predecessor(end, 4) << " "

         << VEB_successor(end, 1) << endl;

  

    // Удалить только при наличии ключа

    if (isMember(end, 2))

        VEB_delete(end, 2);

  

    // После удаления

    cout << isMember(end, 2) << endl;

    cout << VEB_predecessor(end, 4) << " "

         << VEB_successor(end, 1) << endl;

}

Выход:

1
2 2
0
1 4

Рекомендуемые посты:

Дерево Ван Эмде Боаса | Набор 4 | делеция

0.00 (0%) 0 votes