Advertisement
Guest User

vEB Tree

a guest
Aug 3rd, 2011
2,425
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cassert>
  4. #include <memory.h>
  5.  
  6. // van Emde Boas Tree by Arthur "Inviz" Khashaev
  7. // special for habrahabr :)
  8.  
  9. // This is a data structure used to store integers in bound [0; U), where U = 2^k
  10.  
  11. // Asymptotic complexity:
  12. // Insert, Lookup, FindNext, Remove, etc -- O(log(log(U)))
  13. // Space -- O(U)
  14.  
  15. #define NONE(K) (1ULL << K)
  16.  
  17. template <unsigned K>
  18. class VebTree {
  19. private:
  20.     unsigned long long T_min, T_max;
  21.     VebTree<(K >> 1)> *T[1ULL << (K >> 1)], *aux;
  22. public:
  23.     VebTree(): T_min(NONE(K)), aux(NULL) {
  24.         memset(T, 0, sizeof(T));
  25.     }
  26.  
  27.     ~VebTree() {
  28.         delete aux;
  29.         for (unsigned long long i = 0; i < (1ULL << (K >> 1)); ++i) {
  30.             delete T[i];
  31.         }
  32.     }
  33.  
  34.     inline bool empty() const {
  35.         return T_min == NONE(K);
  36.     }
  37.  
  38.     inline unsigned long long get_min() const {
  39.         return T_min;
  40.     }
  41.  
  42.     inline unsigned long long get_max() const {
  43.         return T_max;
  44.     }
  45.  
  46.     inline unsigned long long high(unsigned long long key) const {
  47.         return key >> (K >> 1);
  48.     }
  49.  
  50.     inline unsigned long long low(unsigned long long key) const {
  51.         return key & ((1ULL << (K >> 1)) - 1ULL);
  52.     }
  53.  
  54.     inline unsigned long long merge(unsigned long long high, unsigned long long low) const {
  55.         return (high << (K >> 1)) + low;
  56.     }
  57.  
  58.     void insert(unsigned long long key) {
  59.         if (empty()) {
  60.             T_min = T_max = key;
  61.         } else {
  62.             if (key < T_min) {
  63.                 unsigned long long temp_key = key;
  64.                 key = T_min;
  65.                 T_min = temp_key;
  66.             }
  67.             if (key > T_max) {
  68.                 T_max = key;
  69.             }
  70.             if (K != 1) {
  71.                 unsigned long long key_high = high(key);
  72.                 unsigned long long key_low = low(key);
  73.                 if (T[key_high] == NULL) {
  74.                     T[key_high] = new VebTree<(K >> 1)>();
  75.                 }
  76.                 if (T[key_high]->empty()) {
  77.                     if (aux == NULL) {
  78.                         aux = new VebTree<(K >> 1)>();
  79.                     }
  80.                     aux->insert(key_high);
  81.                 }
  82.                 T[key_high]->insert(key_low);
  83.             }
  84.         }
  85.     }
  86.  
  87.     unsigned long long find_next(unsigned long long key) {
  88.         if (key <= T_min) {
  89.             return T_min;
  90.         }
  91.         if (empty() || key > T_max) {
  92.             return NONE(K);
  93.         }
  94.         if (K == 1) {
  95.             return T_max == key ? key : NONE(K);
  96.         }
  97.         unsigned long long key_high = high(key);
  98.         unsigned long long key_low = low(key);
  99.         if (T[key_high] != NULL && key_low <= T[key_high]->get_max()) {
  100.             return merge(key_high, T[key_high]->find_next(key_low));
  101.         } else if (aux != NULL) {
  102.             unsigned long long next_high = aux->find_next(key_high + 1);
  103.             if (next_high != NONE(K >> 1)) {
  104.                 return merge(next_high, T[next_high]->get_min());
  105.             }
  106.         }
  107.         return NONE(K);
  108.     }
  109.  
  110.     bool lookup(unsigned long long key) {
  111.         if (key == T_min || key == T_max) {
  112.             return true;
  113.         } else {
  114.             unsigned long long key_high = high(key);
  115.             unsigned long long key_low = low(key);
  116.             return T[key_high] != NULL && T[key_high]->lookup(key_low);
  117.         }
  118.     }
  119. };
  120.  
  121. int main() {
  122.     VebTree<32> T;
  123.  
  124.     T.insert(5);
  125.     T.insert(10);
  126.     T.insert(3);
  127.  
  128.     assert(T.lookup(5));
  129.     assert(T.lookup(10));
  130.     assert(!T.lookup(15));
  131.  
  132.     assert(T.find_next(3) == 3);
  133.     assert(T.find_next(4) == 5);
  134.     assert(T.find_next(7) == 10);
  135.     assert(T.find_next(100) == NONE(32));
  136.  
  137.     return 0;
  138. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement