Дерево Прото Ван Эмде Боас | Набор 5 | Запросы: минимум, максимум
Пожалуйста, сначала проверьте предыдущие выпуски статьи о дереве Прото Ван Эмде Боаса. Настоятельно рекомендуется.
Порядок нахождения минимума:
- Базовый случай: если размер Proto-VEB равен 2, мы вернем наименьший ключ, присутствующий в кластере, если ключи отсутствуют, тогда мы вернем -1 как символ отсутствия ключей.
- Рекурсия:
- Мы начнем рекурсию поверх сводки, пока не достигнем первого истинного значения (в коде сначала не nullptr в сводном кластере), которое показывает, что в этом кластере присутствует ключ.
- Теперь мы найдем положение ключа в этом кластере, снова используя рекурсивный вызов кластера, чтобы найти первое истинное значение (в коде сначала не nullptr в кластере) в кластере, как мы это делали выше.
- Наконец, мы вернем индекс этого ключа в соответствии с номером кластера, полученным из процедуры по сводке, и положением, полученным из процедуры по кластеру на последнем шаге.
См. Изображение ниже, чтобы получить общее представление об операции:
Обратите внимание на светло-зеленые кружки сверху вниз:
См. Изображение ниже для реальных минимальных операций Proto - VEB:
Следуйте инструкциям в порядке нумерации.
Вы можете легко получить представление о максимуме из процедуры минимума. См. Изображение ниже:
Обратите внимание на светло-зеленые кружки сверху вниз:
Implementation of the above algorithm:
// C++ implementation of the approach #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 position of x in cluster int low( int x) { return x % root(universe_size); } // Function to return the index from // 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)); } } } }; // Function that returns true if the // key is present in the tree bool isMember(Proto_Van_Emde_Boas* helper, int key) { // If key is greater then universe_size then // returns false if (key >= helper->universe_size) return false ; // If we reach at base case // the just return whether // pointer is nullptr then false // else return true if (helper->universe_size == 2) { return helper->clusters[key]; } else { // Recursively go deep into the // level of Proto-VEB tree using its // cluster index and its position return isMember(helper->clusters[helper->high(key)], helper->low(key)); } } // Function to insert a key in the tree void insert(Proto_Van_Emde_Boas*& helper, int key) { // If we reach at base case // then assign Proto-VEB(1) in place // of nullptr if (helper->universe_size == 2) { helper->clusters[key] = new Proto_Van_Emde_Boas(1); } else { // Recursively using index of cluster and its // position in cluster insert(helper->clusters[helper->high(key)], helper->low(key)); // Also do the same recusion in summary VEB insert(helper->summary, helper->high(key)); } } // Function to return the minimum key from the tree int minimum(Proto_Van_Emde_Boas* helper) { // Base case choses the least key // present in the cluster if (helper->universe_size == 2) { if (helper->clusters[0]) { return 0; } else if (helper->clusters[1]) { return 1; } // No keys present then return -1 return -1; } else { // Recursively find in summary for // first 1 present in Proto-VEB int minimum_cluster = minimum(helper->summary); int offset; // If no key is present in // the cluster then return -1 if (minimum_cluster == -1) { return -1; } else { // Recursively find the position of the key // in the minimum_cluster offset = minimum(helper->clusters[minimum_cluster]); // Returns overall index of minimum key return helper->generate_index(minimum_cluster, offset); } } } // Function to return the maximum key from the tree int maximum(Proto_Van_Emde_Boas* helper) { // Return the maximum key present in // the cluster if (helper->universe_size == 2) { if (helper->clusters[1]) { return 1; } else if (helper->clusters[0]) { return 0; } // Return -1 if no keys present in the // cluster return -1; } else { // Recursively find the last 1 present // in the summary int maximum_cluster = maximum(helper->summary); int offset; // If no key is present in // the cluster then return -1 if (maximum_cluster == -1) { return -1; } else { // Recursively find the position of the key // in the maximum_cluster offset = maximum(helper->clusters[maximum_cluster]); return helper->generate_index(maximum_cluster, offset); } } } // Function to delete a key from the tree void pveb_delete(Proto_Van_Emde_Boas*& helper, int key) { // Base case: If the key is present // then make it nullptr if (helper->universe_size == 2) { if (helper->clusters[key]) { delete helper->clusters[key]; helper->clusters[key] = nullptr; } } else { // Recursive delete to reach at the base case pveb_delete(helper->clusters[helper->high(key)], helper->low(key)); bool isanyinCluster = false ; // Iterate over the cluster of keys to check whether // any other key is present within that cluster // If yes then we should not update summary to 0 // else update summary to 0 for ( int i = helper->high(key) * helper->root(helper->universe_size); i < (helper->high(key) + 1) * helper->root(helper->universe_size); i++) { // If member is present then break the loop if (isMember(helper->clusters[helper->high(key)], i)) { isanyinCluster = true ; break ; } } // If no member is present then // update summary to zero if (isanyinCluster == false ) { pveb_delete(helper->summary, helper->high(key)); } } } // Driver code int main() { Proto_Van_Emde_Boas* hello = new Proto_Van_Emde_Boas(4); cout << boolalpha; insert(hello, 2); insert(hello, 3); cout << minimum(hello) << endl; cout << maximum(hello) << endl; } |
И минимальный, и максимальный запрос выполняется с временной сложностью O (log2 (u)).
Отношение повторения:
Т (и) = 2Т ( ) + O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.