Дерево Прото Ван Эмде Боас | Комплект 2 | Строительство

Опубликовано: 13 Января, 2022

Дерево Ван Эмде Боаса поддерживает операции поиска, минимума, максимума, преемника, предшественника, вставки и удаления за время O (lglgN), что быстрее, чем любая из связанных структур данных, таких как очередь приоритетов, дерево двоичного поиска и т. Д. Дерево Прото Ван Эмде Боаса - это аналогичная структура данных прототипного типа, но она не может достичь сложности O (lglgN). Сначала мы изучим дерево прототипа Ван Эмде Боаса, чтобы получить базовое представление о работе дерева Ван Эмде Боаса. Здесь N - размер вселенной, по которой определено дерево.

Примечание. Ключи структуры данных Proto Van Emde Boas должны быть определены в диапазоне от 0 до n (n - положительное целое число в форме 2 ^{2 ^k} ), и это работает, когда дублирование ключей не допускается.

Сокращения:

Прото-ВЭБ - это аббревиатура от дерева прото-ван Эмде Боаса.
Прото-ВЭБ ( ) - это сокращение от Proto-VEB, содержащее u количество ключей.

Базовое понимание структуры Proto-VEB Tree:
Дерево удавов Proto Van Emde - это рекурсивно определенная структура данных, которая сжимается до размера sqrt по мере продвижения вверх по дереву. Пожалуйста, обратитесь к этой статье, чтобы понять ее основы.

В Proto-VEB мы используем битовый массив, чтобы показать, присутствует ключ или нет, мы ставим 1, если он присутствует, и 0 в противном случае.

Здесь сводка по конкретному кластеру содержит информацию о том, присутствует ли какой-либо ключ в кластере, если присутствует хотя бы один ключ, тогда сводка равна 1 или 0 в другом месте. Кластеры - это сегменты битового массива. Резюме - это тоже битовый массив. См. Изображение ниже:

Построение Proto VEB Tree:

На изображении ниже представлена базовая структура Proto-VEB:

Рекурсивно определенная структура состоит из двух основных частей:

резюме : это указатель на структуру Proto-VEB, которая имеет размер.
кластер: это массив указателей на структуры Proto-VEB с размер.

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

Universe size (u) : Количество ключей в структуре Proto-VEB.
Высокий (x): из первого изображения мы видим, что если мы хотим достичь кластера ключа, мы можем разделить его с помощью .

Например , мы хотим узнать кластер ключа 12, а затем можем разделить его на что равно 3, значит, ключ 12 находится в 3- ^м кластере.
```
 Высокий (x) = пол (x /  )
```
low (x): из первого изображения мы видим, что если нам нужно положение ключа в кластере, мы можем применить операцию модуля x% .

Например , если вы хотите найти позицию 7 в кластере, вы можете применить 7% = 3, что является позицией 7 во 2- ^м кластере.
```
 низкий (x) = x%  )
```

Рекурсивная процедура построения:

Базовый случай: если размер юниверса равен 2, то это базовый размер, поэтому не будет больше сводного массива, это означает, что он равен нулю, и мы будем хранить только битовый массив для 2 ключей.
Мы рекурсивно назначим сводку как размерное дерево прото-ВЭБ и -размерный прото-ВЭБ для всех кластеры.

See u=4 Proto-VEB structure in the image below:

Here is the code representing the Algorithm:

#include <bits/stdc++.h>
using namespace std;
  
class Proto_Van_Emde_Boas {
public:
    // Total number of keys
    int universe_size;
  
    // Summary
    Proto_Van_Emde_Boas* summary;
  
    // Clusters array of Proto-VEB pointers
    vector<Proto_Van_Emde_Boas*> clusters;
  
    int root(int u)
    {
        return int(sqrt(u));
    }
  
    // Function to return cluster numbers
    // in which key is present
    int high(int x)
    {
        return x / root(universe_size);
    }
  
    // Function to return the position
    // of x in cluster
    int low(int x)
    {
        return x % root(universe_size);
    }
  
    // Function to return index form
    // cluster number and position
    int generate_index(int cluster, int position)
    {
        return cluster * root(universe_size) + position;
    }
  
    // Constructor
    Proto_Van_Emde_Boas(int size)
    {
        universe_size = size;
  
        // Base case
        if (size <= 2) {
  
            // Set summary to nullptr as there is no
            // more summary for size 2
            summary = nullptr;
  
            // Vector of two pointers
            // nullptr in starting
            clusters = vector<Proto_Van_Emde_Boas*>(size, nullptr);
        }
        else {
  
            // Assiging Proto-VEB(sqrt(u)) to summary
            summary = new Proto_Van_Emde_Boas(root(size));
  
            // Creating array of Proto-VEB Tree pointers of size sqrt(u)
            // first all nullptrs are going to assign
            clusters = vector<Proto_Van_Emde_Boas*>(root(size), nullptr);
  
            // Assigning Proto-VEB(sqrt(u)) to all its clusters
            for (int i = 0; i < root(size); i++) {
                clusters[i] = new Proto_Van_Emde_Boas(root(size));
            }
        }
    }
};
  
// Driver code
int main()
{
    Proto_Van_Emde_Boas pveb(4);
}

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы Структуры данных

Дерево Прото Ван Эмде Боас | Комплект 2 | Строительство

РЕКОМЕНДУЕМЫЕ СТАТЬИ