VanEmdeBoas树的详细介绍见算法导论第三版这里只给出实现C代码:#include iostream #include memory #include vector #include deque #include stack #include random #include ctime using namespace std; struct VanEmdeBoasTreeNode //vEB树节点定义 { enum NodeType { SUMMARY, CLUSTER } node_type; //节点类型 unsigned int global_size; //注意这里存储的是实际全域大小关于底数2的对数不是全域大小本身 unsigned long long* min nullptr; //节点最大值不存在为nullptr unsigned long long* max nullptr; //节点最小值,不存在为nullptr VanEmdeBoasTreeNode* summary nullptr; //当前节点的summary节点指针 vectorVanEmdeBoasTreeNode* cluster; //cluster子节点指针 VanEmdeBoasTreeNode(unsigned int g, NodeType node_type) :global_size(g), node_type(node_type) {} ~VanEmdeBoasTreeNode() { delete min; delete max; } }; unsigned long long low(VanEmdeBoasTreeNode* node, unsigned long long x) //调用这三个函数时总是假定node的全域大小大于等于2,即node不是叶节点,low,high,index函数的详细定义见算法导论,这里使用移位运算加快求值速度 { unsigned int g node-cluster[0]-global_size; unsigned long long full 0xffffffffffffffff; full full (64U - g); return x full; } unsigned long long high(VanEmdeBoasTreeNode* node, unsigned long long x) { unsigned int g node-cluster[0]-global_size; return x g; } unsigned long long index(VanEmdeBoasTreeNode* node, unsigned long long low, unsigned long long high) { unsigned int g node-cluster[0]-global_size; high high g; return high | low; } struct StackNode { VanEmdeBoasTreeNode* cur; unsigned long long high; StackNode(VanEmdeBoasTreeNode* c, unsigned long long h) :cur(c), high(h) {} }; class VanEmdeBoasTree { public: enum class StyleOfCreatTree { BFS, DFS }; //建树方式深度优先或广度优先 VanEmdeBoasTree(StyleOfCreatTree how_building_tree, unsigned int g); //g为全域大小为实际全域大小关于底数2的对数 shared_ptrunsigned long long min() { if (isEmpty()) return nullptr; return make_sharedunsigned long long(*root-min); } //返回最小值 shared_ptrunsigned long long max() { if (isEmpty()) return nullptr; return make_sharedunsigned long long(*root-max); } //返回最大值 bool remove(unsigned long long x) { if (beyondGlobalSize(x)) return false; return removeValue(root, x); } //删除值 bool insert(unsigned long long x) { if (beyondGlobalSize(x)) return false; return insertValue(root, x); } //插入值 bool contain(unsigned long long x) { if (beyondGlobalSize(x)) return false; return containValue(root, x); } //判断值是否存在 bool isEmpty() { return root-min nullptr; } //判断vEB树是否为空 shared_ptrunsigned long long pre(unsigned long long x) { if (beyondGlobalSize(x)) return nullptr; return findPrecessor(root, x); } //返回x前驱 shared_ptrunsigned long long suc(unsigned long long x) { if (beyondGlobalSize(x)) return nullptr; return findSuccessor(root, x); } //返回x后继 void printValueInTreeFromSmallToLarge(); //从小到大打印vEB树中所有值 void printValueInTreeFromLargeToSmall(); //从大到小打印vEB树中所有值 ~VanEmdeBoasTree(); //销毁vEB树 private: bool beyondGlobalSize(unsigned long long x); //判断x是否超出实际全域大小 bool removeValue(VanEmdeBoasTreeNode* root, unsigned long long x); bool insertValue(VanEmdeBoasTreeNode* root, unsigned long long x); bool containValue(VanEmdeBoasTreeNode* root, unsigned long long x); shared_ptrunsigned long long findPrecessor(VanEmdeBoasTreeNode* root, unsigned long long x); shared_ptrunsigned long long findSuccessor(VanEmdeBoasTreeNode* root, unsigned long long x); StyleOfCreatTree style_of_build_tree StyleOfCreatTree::DFS; //建树方式 VanEmdeBoasTreeNode* root nullptr; //vEB树根节点 }; void VanEmdeBoasTree::printValueInTreeFromLargeToSmall() { cout 从大到小打印树中值 endl; shared_ptrunsigned long long p max(); if (p nullptr) { cout NULL; cout endl; return; } while (p ! nullptr) { cout *p ; p pre(*p); } cout endl; } void VanEmdeBoasTree::printValueInTreeFromSmallToLarge() { cout 从小到大打印树中值 endl; shared_ptrunsigned long long p min(); if (p nullptr) { cout NULL; cout endl; return; } while (p ! nullptr) { cout *p ; p suc(*p); } cout endl; } bool VanEmdeBoasTree::beyondGlobalSize(unsigned long long x) { unsigned int g root-global_size; unsigned long long t 0xffffffffffffffff; t t (64U - g); if (0 x x t) { return false; } else { return true; } } bool VanEmdeBoasTree::containValue(VanEmdeBoasTreeNode* root, unsigned long long x) { VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) { if (cur-min nullptr) return false; if (cur_value *cur-min) return true; if (*cur-min *cur-max) return false; if (cur-summary nullptr) return true; if (cur_value *cur-min || cur_value *cur-max) return false; if (cur_value *cur-max) return true; VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; //下降到下一层递归搜索 cur_value low(cur, cur_value); cur temp; } } bool VanEmdeBoasTree::insertValue(VanEmdeBoasTreeNode* root, unsigned long long x) //在以root为根的vEB树中插入x,true插入成功,false插入失败 { stackStackNode work_stack; VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) { if (cur-min nullptr) break; if (cur_value *cur-min) return false; if (*cur-min *cur-max) break; if (cur-summary nullptr) return false; if (cur_value *cur-min) //应当在当前节点插入比最小值更小的值,此时用当前值更新最小值并把原先的最小值调整为要插入值 { unsigned long long temp *cur-min; *cur-min cur_value; cur_value temp; } work_stack.push(StackNode(cur, high(cur, cur_value))); //继续向下一层寻找插入位置 VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; cur_value low(cur, cur_value); cur temp; } if (cur-min nullptr) //在找到的插入位置插入 { cur-min new unsigned long long(cur_value); cur-max new unsigned long long(cur_value); } else if (*cur-min *cur-max) { if (cur_value *cur-min) { *cur-min cur_value; if (cur-summary ! nullptr) { unsigned long long high_pos high(cur, *cur-max); unsigned long long value low(cur, *cur-max); cur-cluster[high_pos]-max new unsigned long long(value); cur-cluster[high_pos]-min new unsigned long long(value); insertValue(cur-summary, high_pos); } } else { *cur-max cur_value; if (cur-summary ! nullptr) { unsigned long long high_pos high(cur, cur_value); unsigned long long value low(cur, cur_value); cur-cluster[high_pos]-max new unsigned long long(value); cur-cluster[high_pos]-min new unsigned long long(value); insertValue(cur-summary, high_pos); } } } while (work_stack.empty() false) //自底向上调整summary和max值 { cur work_stack.top().cur; unsigned long long high work_stack.top().high; work_stack.pop(); cur_value index(cur, cur_value, high); if (*cur-cluster[high]-min *cur-cluster[high]-max) insertValue(cur-summary, high); if (cur_value *cur-max) //如果当前层节点max值没有因插入而改变则无需继续向上调整直接退出 return true; *cur-max cur_value; } return true; } bool VanEmdeBoasTree::removeValue(VanEmdeBoasTreeNode* root, unsigned long long x) //在以root为根的vEB树中删除x,成功返回true,失败返回false { stackStackNode work_stack; VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) //从根节点向下搜索找到叶节点或只含有单一值的分支节点且x在其中即退出否则返回false { if (cur-summary nullptr) { if (cur-min nullptr) return false; if (*cur-min *cur-max) { if (cur_value *cur-min) break; return false; } break; } else { if (cur-min nullptr) return false; if (cur_value *cur-min) { if (*cur-min *cur-max) break; unsigned long long t *cur-summary-min; //这里相当关键如果在一个包含两个或两个以上值的分支节点找到x且x恰为分支节点最小值 cur_value *cur-cluster[t]-min; //则应用x在该节点的后继替换最小值,同时更改当前搜索值为替换后的新值,然后下降到x在当前节点的后继所在的当前节点的子vEB树继续搜索 *cur-min index(cur, cur_value, t); work_stack.push(StackNode(cur, t)); cur cur-cluster[t]; continue; } if (*cur-min *cur-max) return false; if (cur_value *cur-min || cur_value *cur-max) return false; work_stack.push(StackNode(cur, high(cur, cur_value))); VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; cur_value low(cur, cur_value); cur temp; } } unsigned long long high 0; bool first_cycle true; while (true) { if (first_cycle) { if (cur-summary nullptr) //在叶节点删除 { if (*cur-min *cur-max) { cur-min nullptr; cur-max nullptr; } else { if (cur_value *cur-min) *cur-min *cur-max; else *cur-max *cur-min; } } else { cur-min nullptr; //在只含有单一值的分支节点删除 cur-max nullptr; } first_cycle false; } else { cur_value index(cur, cur_value, high); if (cur_value *cur-min) //回溯到最小值被其后继替换的最后一个节点 { if (cur_value *cur-max || cur-cluster[high]-min nullptr) removeValue(cur-summary, high); return true; //更新该节点的summary后当前节点最大值和删除前相同保持不变并且当前节点对应vEB树非空故无需向根节点调整直接返回 } if (cur_value ! *cur-max) { //这种情况说明从当前节点cluster数组high元素对应子树删除cur_value后,当前节点的原最大值没有被删除且现在的最大值就是原最大值所以无需更新最大值,当然high元素对应子树被删除值后可能为空所以需要在summary中递归删除 if (cur-cluster[high]-min nullptr) removeValue(cur-summary, high); return true; //上述操作结束后注意到当前节点删除cur_value后不为空故直接返回无需向根节点调整 } if (cur-cluster[high]-max ! nullptr) //回溯到此时的分支节点之前的搜索过程中一定没有用某节点的最小值的后继替换最小值 *cur-max index(cur, *cur-cluster[high]-max, high); //此外一定从搜索结束时找到的叶节点或只含有单一值的分支节点中实际删除给定值后回溯到了当前分支节点,判断条件cur_value *cur-max通过后一定 else //从当前节点的cluster数组的high元素对应的vEB树中删除了该vEB树的最大值cur_value,且high元素之后的元素对应的vEB子树为空,这样必须用 { shared_ptrunsigned long long temp findPrecessor(cur-summary, high); //当前节点的被删除的最大值的前驱更新当前节点最大值 if (temp ! nullptr) *cur-max index(cur, *cur-cluster[*temp]-max, *temp); else *cur-max *cur-min; removeValue(cur-summary, high); } } if (work_stack.empty() true) return true; cur work_stack.top().cur; high work_stack.top().high; work_stack.pop(); } } shared_ptrunsigned long long VanEmdeBoasTree::findSuccessor(VanEmdeBoasTreeNode* root, unsigned long long x) //在以root为根的vEB树中寻找x的后继,失败返回nullptr,否则返回后继值 { stackStackNode work_stack; VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) { if (cur-min nullptr || cur_value *cur-max) { if (work_stack.empty()) return nullptr; cur work_stack.top().cur; shared_ptrunsigned long long temp findSuccessor(cur-summary, work_stack.top().high); cur_value index(cur, *cur-cluster[*temp]-min, *temp); work_stack.pop(); } else { if (cur-summary nullptr) { cur_value *cur-max; } else if (cur_value *cur-min) { cur_value *cur-min; } else if (cur_value *cur-min) { unsigned long long h_min *cur-summary-min; cur_value index(cur, *cur-cluster[h_min]-min, h_min); } else { work_stack.push(StackNode(cur, high(cur, cur_value))); VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; cur_value low(cur, cur_value); cur temp; continue; } } break;//令查找到x的叶节点或x等于其最小值的分支节点为循环开始时的当前节点,如果在当前节点能够找到x的后继则逐级向上返回到根节点并在根结单处最终还原出x的后继 //如果当前节点无法找到x的后继则回溯至父节点在父节点的summary中查找当前节点对应vEB树在父节点cluster中的对应下标的后继如果找到该后继在父节点cluster中对应子树的最小值即 } //为x后继然后逐级向上返回在根节点还原后继否则回溯至祖先节点继续利用祖先节点的summary查找x后继处理过程和上述相同如果最终在根节点处仍未发现x后继则查找失败返回nullptr unsigned long long high; while (!work_stack.empty()) { cur work_stack.top().cur; high work_stack.top().high; work_stack.pop(); cur_value index(cur, cur_value, high); } return make_sharedunsigned long long(cur_value); } shared_ptrunsigned long long VanEmdeBoasTree::findPrecessor(VanEmdeBoasTreeNode* root, unsigned long long x) //在以root为根的vEB树中寻找x的前驱,失败返回nullptr,否则返回前驱值过程和查找后继对称 { stackStackNode work_stack; VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) { if (cur-min nullptr || cur_value *cur-min) { if (work_stack.empty()) return nullptr; cur work_stack.top().cur; shared_ptrunsigned long long temp findPrecessor(cur-summary, work_stack.top().high); if (temp nullptr) { cur_value *cur-min; } else { cur_value index(cur, *cur-cluster[*temp]-max, *temp); } work_stack.pop(); } else { if (cur-summary nullptr) { cur_value *cur-min; } else if (cur_value *cur-max) { cur_value *cur-max; } else { work_stack.push(StackNode(cur, high(cur, cur_value))); VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; cur_value low(cur, cur_value); cur temp; continue; } } break; } unsigned long long high; while (!work_stack.empty()) { cur work_stack.top().cur; high work_stack.top().high; work_stack.pop(); cur_value index(cur, cur_value, high); } return make_sharedunsigned long long(cur_value); } VanEmdeBoasTree::~VanEmdeBoasTree() { stackVanEmdeBoasTreeNode* work_stack; //深度优先销毁vEB树 bool trace_back_flag true; work_stack.push(root); while (work_stack.empty() false) { if (trace_back_flag) { if (work_stack.top()-global_size 1) { work_stack.push(work_stack.top()-summary); } else { delete work_stack.top(); work_stack.pop(); trace_back_flag false; } } else { if (work_stack.top()-cluster.empty() false) { VanEmdeBoasTreeNode* temp work_stack.top(); work_stack.push(work_stack.top()-cluster.back()); temp-cluster.pop_back(); trace_back_flag true; } else { delete work_stack.top(); work_stack.pop(); } } } } VanEmdeBoasTree::VanEmdeBoasTree(StyleOfCreatTree how_building_tree, unsigned int g) { if (g 0 || g 64) { cout ERROR:全域大小超出允许范围 endl; exit(-1); } style_of_build_tree how_building_tree; root new VanEmdeBoasTreeNode(g, VanEmdeBoasTreeNode::NodeType::CLUSTER); //BFS方式构建vEB树 if (style_of_build_tree StyleOfCreatTree::BFS) { dequeVanEmdeBoasTreeNode* work_queue; work_queue.push_back(root); while (work_queue.empty() false) { VanEmdeBoasTreeNode* cur work_queue.front(); work_queue.pop_front(); if (cur-global_size 1) { unsigned int k cur-global_size 1; unsigned long long global 0; if ((cur-global_size 1) 0) { cur-summary new VanEmdeBoasTreeNode(k, VanEmdeBoasTreeNode::NodeType::SUMMARY); global 1U k; } else { cur-summary new VanEmdeBoasTreeNode(k 1, VanEmdeBoasTreeNode::NodeType::SUMMARY); global 1U (k 1); } work_queue.push_back(cur-summary); for (size_t i 1; i global; i) { cur-cluster.push_back(new VanEmdeBoasTreeNode(k, VanEmdeBoasTreeNode::NodeType::CLUSTER)); work_queue.push_back(cur-cluster.back()); } } } } else { struct StackNode { VanEmdeBoasTreeNode* cur; unsigned int down_sqrt; unsigned long long cluster_size; StackNode(VanEmdeBoasTreeNode* c) :cur(c) {} }; stackStackNode work_stack; bool trace_back_flag true; work_stack.push(StackNode(root)); while (work_stack.empty() false) //DFS方式构建vEB树 { if (trace_back_flag) { if (work_stack.top().cur-global_size 1) { unsigned int k work_stack.top().cur-global_size 1; size_t global 0; if ((work_stack.top().cur-global_size 1) 0) { work_stack.top().cur-summary new VanEmdeBoasTreeNode(k, VanEmdeBoasTreeNode::NodeType::SUMMARY); work_stack.top().cluster_size 1U k; } else { work_stack.top().cur-summary new VanEmdeBoasTreeNode(k 1, VanEmdeBoasTreeNode::NodeType::SUMMARY); work_stack.top().cluster_size 1U (k 1); } work_stack.top().down_sqrt k; work_stack.push(StackNode(work_stack.top().cur-summary)); } else { work_stack.pop(); trace_back_flag false; } } else { if (work_stack.top().cur-cluster.size() work_stack.top().cluster_size) { work_stack.top().cur-cluster.push_back(new VanEmdeBoasTreeNode(work_stack.top().down_sqrt, VanEmdeBoasTreeNode::NodeType::CLUSTER)); work_stack.push(work_stack.top().cur-cluster.back()); trace_back_flag true; } else { work_stack.pop(); } } } } } int main() { unsigned int global 4; VanEmdeBoasTree obj(VanEmdeBoasTree::StyleOfCreatTree::DFS, global); vectorunsigned long long input; unsigned long long j 1ULL global; for (unsigned long long i 1; i j; i) { input.push_back(i - 1); } shuffle(input.begin(), input.end(), default_random_engine(time(nullptr))); for (const unsigned long long i : input) { cout 插入 i endl; if (obj.insert(i)) { cout 插入成功 endl; obj.printValueInTreeFromSmallToLarge(); obj.printValueInTreeFromLargeToSmall(); } else { cout 插入失败 endl; } } obj.printValueInTreeFromLargeToSmall(); obj.printValueInTreeFromSmallToLarge(); for (const unsigned long long i : input) { cout 删除 i endl; if (obj.remove(i)) { cout 删除成功 endl; obj.printValueInTreeFromSmallToLarge(); obj.printValueInTreeFromLargeToSmall(); } else { cout 删除失败 endl; } } if (obj.isEmpty()) { cout 树空 endl; } return 0; }
VanEmdeBoas树的详细介绍见算法导论第三版这里只给出实现C代码:#include iostream #include memory #include vector #include deque #include stack #include random #include ctime using namespace std; struct VanEmdeBoasTreeNode //vEB树节点定义 { enum NodeType { SUMMARY, CLUSTER } node_type; //节点类型 unsigned int global_size; //注意这里存储的是实际全域大小关于底数2的对数不是全域大小本身 unsigned long long* min nullptr; //节点最大值不存在为nullptr unsigned long long* max nullptr; //节点最小值,不存在为nullptr VanEmdeBoasTreeNode* summary nullptr; //当前节点的summary节点指针 vectorVanEmdeBoasTreeNode* cluster; //cluster子节点指针 VanEmdeBoasTreeNode(unsigned int g, NodeType node_type) :global_size(g), node_type(node_type) {} ~VanEmdeBoasTreeNode() { delete min; delete max; } }; unsigned long long low(VanEmdeBoasTreeNode* node, unsigned long long x) //调用这三个函数时总是假定node的全域大小大于等于2,即node不是叶节点,low,high,index函数的详细定义见算法导论,这里使用移位运算加快求值速度 { unsigned int g node-cluster[0]-global_size; unsigned long long full 0xffffffffffffffff; full full (64U - g); return x full; } unsigned long long high(VanEmdeBoasTreeNode* node, unsigned long long x) { unsigned int g node-cluster[0]-global_size; return x g; } unsigned long long index(VanEmdeBoasTreeNode* node, unsigned long long low, unsigned long long high) { unsigned int g node-cluster[0]-global_size; high high g; return high | low; } struct StackNode { VanEmdeBoasTreeNode* cur; unsigned long long high; StackNode(VanEmdeBoasTreeNode* c, unsigned long long h) :cur(c), high(h) {} }; class VanEmdeBoasTree { public: enum class StyleOfCreatTree { BFS, DFS }; //建树方式深度优先或广度优先 VanEmdeBoasTree(StyleOfCreatTree how_building_tree, unsigned int g); //g为全域大小为实际全域大小关于底数2的对数 shared_ptrunsigned long long min() { if (isEmpty()) return nullptr; return make_sharedunsigned long long(*root-min); } //返回最小值 shared_ptrunsigned long long max() { if (isEmpty()) return nullptr; return make_sharedunsigned long long(*root-max); } //返回最大值 bool remove(unsigned long long x) { if (beyondGlobalSize(x)) return false; return removeValue(root, x); } //删除值 bool insert(unsigned long long x) { if (beyondGlobalSize(x)) return false; return insertValue(root, x); } //插入值 bool contain(unsigned long long x) { if (beyondGlobalSize(x)) return false; return containValue(root, x); } //判断值是否存在 bool isEmpty() { return root-min nullptr; } //判断vEB树是否为空 shared_ptrunsigned long long pre(unsigned long long x) { if (beyondGlobalSize(x)) return nullptr; return findPrecessor(root, x); } //返回x前驱 shared_ptrunsigned long long suc(unsigned long long x) { if (beyondGlobalSize(x)) return nullptr; return findSuccessor(root, x); } //返回x后继 void printValueInTreeFromSmallToLarge(); //从小到大打印vEB树中所有值 void printValueInTreeFromLargeToSmall(); //从大到小打印vEB树中所有值 ~VanEmdeBoasTree(); //销毁vEB树 private: bool beyondGlobalSize(unsigned long long x); //判断x是否超出实际全域大小 bool removeValue(VanEmdeBoasTreeNode* root, unsigned long long x); bool insertValue(VanEmdeBoasTreeNode* root, unsigned long long x); bool containValue(VanEmdeBoasTreeNode* root, unsigned long long x); shared_ptrunsigned long long findPrecessor(VanEmdeBoasTreeNode* root, unsigned long long x); shared_ptrunsigned long long findSuccessor(VanEmdeBoasTreeNode* root, unsigned long long x); StyleOfCreatTree style_of_build_tree StyleOfCreatTree::DFS; //建树方式 VanEmdeBoasTreeNode* root nullptr; //vEB树根节点 }; void VanEmdeBoasTree::printValueInTreeFromLargeToSmall() { cout 从大到小打印树中值 endl; shared_ptrunsigned long long p max(); if (p nullptr) { cout NULL; cout endl; return; } while (p ! nullptr) { cout *p ; p pre(*p); } cout endl; } void VanEmdeBoasTree::printValueInTreeFromSmallToLarge() { cout 从小到大打印树中值 endl; shared_ptrunsigned long long p min(); if (p nullptr) { cout NULL; cout endl; return; } while (p ! nullptr) { cout *p ; p suc(*p); } cout endl; } bool VanEmdeBoasTree::beyondGlobalSize(unsigned long long x) { unsigned int g root-global_size; unsigned long long t 0xffffffffffffffff; t t (64U - g); if (0 x x t) { return false; } else { return true; } } bool VanEmdeBoasTree::containValue(VanEmdeBoasTreeNode* root, unsigned long long x) { VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) { if (cur-min nullptr) return false; if (cur_value *cur-min) return true; if (*cur-min *cur-max) return false; if (cur-summary nullptr) return true; if (cur_value *cur-min || cur_value *cur-max) return false; if (cur_value *cur-max) return true; VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; //下降到下一层递归搜索 cur_value low(cur, cur_value); cur temp; } } bool VanEmdeBoasTree::insertValue(VanEmdeBoasTreeNode* root, unsigned long long x) //在以root为根的vEB树中插入x,true插入成功,false插入失败 { stackStackNode work_stack; VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) { if (cur-min nullptr) break; if (cur_value *cur-min) return false; if (*cur-min *cur-max) break; if (cur-summary nullptr) return false; if (cur_value *cur-min) //应当在当前节点插入比最小值更小的值,此时用当前值更新最小值并把原先的最小值调整为要插入值 { unsigned long long temp *cur-min; *cur-min cur_value; cur_value temp; } work_stack.push(StackNode(cur, high(cur, cur_value))); //继续向下一层寻找插入位置 VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; cur_value low(cur, cur_value); cur temp; } if (cur-min nullptr) //在找到的插入位置插入 { cur-min new unsigned long long(cur_value); cur-max new unsigned long long(cur_value); } else if (*cur-min *cur-max) { if (cur_value *cur-min) { *cur-min cur_value; if (cur-summary ! nullptr) { unsigned long long high_pos high(cur, *cur-max); unsigned long long value low(cur, *cur-max); cur-cluster[high_pos]-max new unsigned long long(value); cur-cluster[high_pos]-min new unsigned long long(value); insertValue(cur-summary, high_pos); } } else { *cur-max cur_value; if (cur-summary ! nullptr) { unsigned long long high_pos high(cur, cur_value); unsigned long long value low(cur, cur_value); cur-cluster[high_pos]-max new unsigned long long(value); cur-cluster[high_pos]-min new unsigned long long(value); insertValue(cur-summary, high_pos); } } } while (work_stack.empty() false) //自底向上调整summary和max值 { cur work_stack.top().cur; unsigned long long high work_stack.top().high; work_stack.pop(); cur_value index(cur, cur_value, high); if (*cur-cluster[high]-min *cur-cluster[high]-max) insertValue(cur-summary, high); if (cur_value *cur-max) //如果当前层节点max值没有因插入而改变则无需继续向上调整直接退出 return true; *cur-max cur_value; } return true; } bool VanEmdeBoasTree::removeValue(VanEmdeBoasTreeNode* root, unsigned long long x) //在以root为根的vEB树中删除x,成功返回true,失败返回false { stackStackNode work_stack; VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) //从根节点向下搜索找到叶节点或只含有单一值的分支节点且x在其中即退出否则返回false { if (cur-summary nullptr) { if (cur-min nullptr) return false; if (*cur-min *cur-max) { if (cur_value *cur-min) break; return false; } break; } else { if (cur-min nullptr) return false; if (cur_value *cur-min) { if (*cur-min *cur-max) break; unsigned long long t *cur-summary-min; //这里相当关键如果在一个包含两个或两个以上值的分支节点找到x且x恰为分支节点最小值 cur_value *cur-cluster[t]-min; //则应用x在该节点的后继替换最小值,同时更改当前搜索值为替换后的新值,然后下降到x在当前节点的后继所在的当前节点的子vEB树继续搜索 *cur-min index(cur, cur_value, t); work_stack.push(StackNode(cur, t)); cur cur-cluster[t]; continue; } if (*cur-min *cur-max) return false; if (cur_value *cur-min || cur_value *cur-max) return false; work_stack.push(StackNode(cur, high(cur, cur_value))); VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; cur_value low(cur, cur_value); cur temp; } } unsigned long long high 0; bool first_cycle true; while (true) { if (first_cycle) { if (cur-summary nullptr) //在叶节点删除 { if (*cur-min *cur-max) { cur-min nullptr; cur-max nullptr; } else { if (cur_value *cur-min) *cur-min *cur-max; else *cur-max *cur-min; } } else { cur-min nullptr; //在只含有单一值的分支节点删除 cur-max nullptr; } first_cycle false; } else { cur_value index(cur, cur_value, high); if (cur_value *cur-min) //回溯到最小值被其后继替换的最后一个节点 { if (cur_value *cur-max || cur-cluster[high]-min nullptr) removeValue(cur-summary, high); return true; //更新该节点的summary后当前节点最大值和删除前相同保持不变并且当前节点对应vEB树非空故无需向根节点调整直接返回 } if (cur_value ! *cur-max) { //这种情况说明从当前节点cluster数组high元素对应子树删除cur_value后,当前节点的原最大值没有被删除且现在的最大值就是原最大值所以无需更新最大值,当然high元素对应子树被删除值后可能为空所以需要在summary中递归删除 if (cur-cluster[high]-min nullptr) removeValue(cur-summary, high); return true; //上述操作结束后注意到当前节点删除cur_value后不为空故直接返回无需向根节点调整 } if (cur-cluster[high]-max ! nullptr) //回溯到此时的分支节点之前的搜索过程中一定没有用某节点的最小值的后继替换最小值 *cur-max index(cur, *cur-cluster[high]-max, high); //此外一定从搜索结束时找到的叶节点或只含有单一值的分支节点中实际删除给定值后回溯到了当前分支节点,判断条件cur_value *cur-max通过后一定 else //从当前节点的cluster数组的high元素对应的vEB树中删除了该vEB树的最大值cur_value,且high元素之后的元素对应的vEB子树为空,这样必须用 { shared_ptrunsigned long long temp findPrecessor(cur-summary, high); //当前节点的被删除的最大值的前驱更新当前节点最大值 if (temp ! nullptr) *cur-max index(cur, *cur-cluster[*temp]-max, *temp); else *cur-max *cur-min; removeValue(cur-summary, high); } } if (work_stack.empty() true) return true; cur work_stack.top().cur; high work_stack.top().high; work_stack.pop(); } } shared_ptrunsigned long long VanEmdeBoasTree::findSuccessor(VanEmdeBoasTreeNode* root, unsigned long long x) //在以root为根的vEB树中寻找x的后继,失败返回nullptr,否则返回后继值 { stackStackNode work_stack; VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) { if (cur-min nullptr || cur_value *cur-max) { if (work_stack.empty()) return nullptr; cur work_stack.top().cur; shared_ptrunsigned long long temp findSuccessor(cur-summary, work_stack.top().high); cur_value index(cur, *cur-cluster[*temp]-min, *temp); work_stack.pop(); } else { if (cur-summary nullptr) { cur_value *cur-max; } else if (cur_value *cur-min) { cur_value *cur-min; } else if (cur_value *cur-min) { unsigned long long h_min *cur-summary-min; cur_value index(cur, *cur-cluster[h_min]-min, h_min); } else { work_stack.push(StackNode(cur, high(cur, cur_value))); VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; cur_value low(cur, cur_value); cur temp; continue; } } break;//令查找到x的叶节点或x等于其最小值的分支节点为循环开始时的当前节点,如果在当前节点能够找到x的后继则逐级向上返回到根节点并在根结单处最终还原出x的后继 //如果当前节点无法找到x的后继则回溯至父节点在父节点的summary中查找当前节点对应vEB树在父节点cluster中的对应下标的后继如果找到该后继在父节点cluster中对应子树的最小值即 } //为x后继然后逐级向上返回在根节点还原后继否则回溯至祖先节点继续利用祖先节点的summary查找x后继处理过程和上述相同如果最终在根节点处仍未发现x后继则查找失败返回nullptr unsigned long long high; while (!work_stack.empty()) { cur work_stack.top().cur; high work_stack.top().high; work_stack.pop(); cur_value index(cur, cur_value, high); } return make_sharedunsigned long long(cur_value); } shared_ptrunsigned long long VanEmdeBoasTree::findPrecessor(VanEmdeBoasTreeNode* root, unsigned long long x) //在以root为根的vEB树中寻找x的前驱,失败返回nullptr,否则返回前驱值过程和查找后继对称 { stackStackNode work_stack; VanEmdeBoasTreeNode* cur root; unsigned long long cur_value x; while (true) { if (cur-min nullptr || cur_value *cur-min) { if (work_stack.empty()) return nullptr; cur work_stack.top().cur; shared_ptrunsigned long long temp findPrecessor(cur-summary, work_stack.top().high); if (temp nullptr) { cur_value *cur-min; } else { cur_value index(cur, *cur-cluster[*temp]-max, *temp); } work_stack.pop(); } else { if (cur-summary nullptr) { cur_value *cur-min; } else if (cur_value *cur-max) { cur_value *cur-max; } else { work_stack.push(StackNode(cur, high(cur, cur_value))); VanEmdeBoasTreeNode* temp cur-cluster[high(cur, cur_value)]; cur_value low(cur, cur_value); cur temp; continue; } } break; } unsigned long long high; while (!work_stack.empty()) { cur work_stack.top().cur; high work_stack.top().high; work_stack.pop(); cur_value index(cur, cur_value, high); } return make_sharedunsigned long long(cur_value); } VanEmdeBoasTree::~VanEmdeBoasTree() { stackVanEmdeBoasTreeNode* work_stack; //深度优先销毁vEB树 bool trace_back_flag true; work_stack.push(root); while (work_stack.empty() false) { if (trace_back_flag) { if (work_stack.top()-global_size 1) { work_stack.push(work_stack.top()-summary); } else { delete work_stack.top(); work_stack.pop(); trace_back_flag false; } } else { if (work_stack.top()-cluster.empty() false) { VanEmdeBoasTreeNode* temp work_stack.top(); work_stack.push(work_stack.top()-cluster.back()); temp-cluster.pop_back(); trace_back_flag true; } else { delete work_stack.top(); work_stack.pop(); } } } } VanEmdeBoasTree::VanEmdeBoasTree(StyleOfCreatTree how_building_tree, unsigned int g) { if (g 0 || g 64) { cout ERROR:全域大小超出允许范围 endl; exit(-1); } style_of_build_tree how_building_tree; root new VanEmdeBoasTreeNode(g, VanEmdeBoasTreeNode::NodeType::CLUSTER); //BFS方式构建vEB树 if (style_of_build_tree StyleOfCreatTree::BFS) { dequeVanEmdeBoasTreeNode* work_queue; work_queue.push_back(root); while (work_queue.empty() false) { VanEmdeBoasTreeNode* cur work_queue.front(); work_queue.pop_front(); if (cur-global_size 1) { unsigned int k cur-global_size 1; unsigned long long global 0; if ((cur-global_size 1) 0) { cur-summary new VanEmdeBoasTreeNode(k, VanEmdeBoasTreeNode::NodeType::SUMMARY); global 1U k; } else { cur-summary new VanEmdeBoasTreeNode(k 1, VanEmdeBoasTreeNode::NodeType::SUMMARY); global 1U (k 1); } work_queue.push_back(cur-summary); for (size_t i 1; i global; i) { cur-cluster.push_back(new VanEmdeBoasTreeNode(k, VanEmdeBoasTreeNode::NodeType::CLUSTER)); work_queue.push_back(cur-cluster.back()); } } } } else { struct StackNode { VanEmdeBoasTreeNode* cur; unsigned int down_sqrt; unsigned long long cluster_size; StackNode(VanEmdeBoasTreeNode* c) :cur(c) {} }; stackStackNode work_stack; bool trace_back_flag true; work_stack.push(StackNode(root)); while (work_stack.empty() false) //DFS方式构建vEB树 { if (trace_back_flag) { if (work_stack.top().cur-global_size 1) { unsigned int k work_stack.top().cur-global_size 1; size_t global 0; if ((work_stack.top().cur-global_size 1) 0) { work_stack.top().cur-summary new VanEmdeBoasTreeNode(k, VanEmdeBoasTreeNode::NodeType::SUMMARY); work_stack.top().cluster_size 1U k; } else { work_stack.top().cur-summary new VanEmdeBoasTreeNode(k 1, VanEmdeBoasTreeNode::NodeType::SUMMARY); work_stack.top().cluster_size 1U (k 1); } work_stack.top().down_sqrt k; work_stack.push(StackNode(work_stack.top().cur-summary)); } else { work_stack.pop(); trace_back_flag false; } } else { if (work_stack.top().cur-cluster.size() work_stack.top().cluster_size) { work_stack.top().cur-cluster.push_back(new VanEmdeBoasTreeNode(work_stack.top().down_sqrt, VanEmdeBoasTreeNode::NodeType::CLUSTER)); work_stack.push(work_stack.top().cur-cluster.back()); trace_back_flag true; } else { work_stack.pop(); } } } } } int main() { unsigned int global 4; VanEmdeBoasTree obj(VanEmdeBoasTree::StyleOfCreatTree::DFS, global); vectorunsigned long long input; unsigned long long j 1ULL global; for (unsigned long long i 1; i j; i) { input.push_back(i - 1); } shuffle(input.begin(), input.end(), default_random_engine(time(nullptr))); for (const unsigned long long i : input) { cout 插入 i endl; if (obj.insert(i)) { cout 插入成功 endl; obj.printValueInTreeFromSmallToLarge(); obj.printValueInTreeFromLargeToSmall(); } else { cout 插入失败 endl; } } obj.printValueInTreeFromLargeToSmall(); obj.printValueInTreeFromSmallToLarge(); for (const unsigned long long i : input) { cout 删除 i endl; if (obj.remove(i)) { cout 删除成功 endl; obj.printValueInTreeFromSmallToLarge(); obj.printValueInTreeFromLargeToSmall(); } else { cout 删除失败 endl; } } if (obj.isEmpty()) { cout 树空 endl; } return 0; }
