daily pastebin goal
60%
SHARE
TWEET

vEB Tree

a guest Aug 3rd, 2011 1,858 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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top