企业官网建设流程全解析

HB(k)树是对AVL树的推广，故称广义AVL树，具体定义是HB(k)树要么是空树要么是满足如下条件的二叉搜索树：

其左右子树均为HB(k)树，且右子树高度和左子树高度差的绝对值小于等于k.

本文HB(k)树的删除算法参考了苏州大学唐自立老师的参考文献《一种新的删除HB(k)树的结点的算法》。笔者根据文中的当前阶段删除的示意图编写自底向上的删除算法，插入算法完全为自己独立思考所得，具体代码如下:

#include <stack> #include <vector> #include <iostream> #include <string> #include <cmath> #include <algorithm> #include <random> #include <ctime> #include <deque> using namespace std; template <typename T> struct HB_kTreeNode //AVL树节点类 { long long bf; //节点平衡因子 T data; //节点数据域 HB_kTreeNode* left; HB_kTreeNode* right; HB_kTreeNode(long long b, const T &d) :bf(b), data(d), left(nullptr), right(nullptr) {} }; void printNULL(size_t num) { for (size_t o = 1; o <= num; ++o) cout << " "; cout << "NULL" << endl; } template <typename T> void printHB_kTree(HB_kTreeNode<T>* root, const vector<size_t>& offset_array, size_t offset, size_t level) { if (root == nullptr) cout << "NULL空树" << endl; for (size_t i = 1; i <= offset; ++i) cout << " "; cout << to_string(root->data); cout << ":bf="; if (root->bf > 0) cout << "+"; cout << root->bf; cout << endl; if (root->left == nullptr) { if (root->right != nullptr) { printNULL(offset + offset_array[level] + 4); printHB_kTree(root->right, offset_array, offset + offset_array[level] + 4, level + 1); } } else { printHB_kTree(root->left, offset_array, offset + offset_array[level] + 4, level + 1); if (root->right == nullptr) { printNULL(offset + offset_array[level] + 4); } else printHB_kTree(root->right, offset_array, offset + offset_array[level] + 4, level + 1); } } template <typename T> void print(HB_kTreeNode<T>* root) { deque<HB_kTreeNode<T>*> work_queue; work_queue.push_back(root); vector<size_t> offset_array; while (work_queue.empty() == false) { size_t n = work_queue.size(); size_t max_length = 0; for (size_t i = 1; i <= n; i++) { HB_kTreeNode<T>* temp = work_queue.front(); work_queue.pop_front(); if (temp->left != nullptr) work_queue.push_back(temp->left); if (temp->right != nullptr) work_queue.push_back(temp->right); size_t offset = 0; offset += to_string(temp->data).size(); offset += to_string(temp->bf).size(); if (temp->bf > 0) ++offset; if (offset > max_length) max_length = offset; } offset_array.push_back(max_length); } printHB_kTree(root, offset_array, 0, 0); } template <typename T> class HB_kTree { public: bool insert(const T &key); bool remove(const T& key); void RotateLR(HB_kTreeNode<T>* ptr); void RotateRL(HB_kTreeNode<T>* ptr); void RotateR(HB_kTreeNode<T>* ptr); void RotateL(HB_kTreeNode<T>* ptr); bool isEmpty()const { return root == nullptr; } HB_kTreeNode<T>* getRoot() const{ return root; } long long getK() const{ return k; } void printTree() { if (root == nullptr) cout << "NULL" << endl; else print(root); } HB_kTree(long long k) :k(k), root(nullptr) {} private: const long long k; HB_kTreeNode<T>* root; }; template <typename T> void HB_kTree<T>::RotateLR(HB_kTreeNode<T>* ptr) //对以ptr为根的子树执行先左后右双旋转,ptr成为旋转后新树根节点指针 { HB_kTreeNode<T>* p = ptr->left; HB_kTreeNode<T>* q = p->right; p->right = q->left; q->left = p; ptr->left = q->right; q->right = ptr; } template <typename T> void HB_kTree<T>::RotateRL(HB_kTreeNode<T>* ptr) //对以ptr为根的子树执行先右后左双旋转,ptr成为旋转后新树根节点指针 { HB_kTreeNode<T>* p = ptr->right; HB_kTreeNode<T>* q = p->left; p->left = q->right; q->right = p; ptr->right = q->left; q->left = ptr; } template <typename T> void HB_kTree<T>::RotateR(HB_kTreeNode<T>* ptr) //对以ptr为根的子树执行右单旋转,ptr成为旋转后新树根节点指针 { HB_kTreeNode<T>* p = ptr->left; ptr->left = p->right; p->right = ptr; } template <typename T> void HB_kTree<T>::RotateL(HB_kTreeNode<T>* ptr) ////对以ptr为根的子树执行左单旋转,ptr成为旋转后新树根节点指针 { HB_kTreeNode<T>* p = ptr->right; ptr->right = p->left; p->left = ptr; } template <typename T> int Searchd(HB_kTreeNode<T>* ptr, int d) { if (d == 2) return 0; else { if (d == 1) { if (ptr->right == nullptr) return 0; else return 2; } else { if (ptr->left != nullptr) return 1; else { if (ptr->right != nullptr) return 2; else return 0; } } } } template <typename T> bool isHBTree(const HB_kTree<T>& object) //判断以root为根节点的二叉树是否为AVL树 { struct memory { HB_kTreeNode<T>* p; int direction; T lmin; int lh = 0; //节点左子树高度 memory(HB_kTreeNode<T>* p, int d) :p(p), direction(d) {} }; T rmin; T rmax; T lmax; int rh; int d = 0; HB_kTreeNode<T>* ptr = object.getRoot(); HB_kTreeNode<T>* const dest = ptr; stack<memory> arrange; bool TF = false; while (true) { if (Searchd(ptr, d) == 0) { if (ptr == dest) { if (d == 0) return true; } if (d == 0) { if (arrange.top().direction == 1) { arrange.top().lh = 1; arrange.top().lmin = ptr->data; lmax = ptr->data; } else { rh = 1; rmin = ptr->data; rmax = ptr->data; } } else { if (d == 1) { if (lmax >= ptr->data) { cout << "当前树非二叉搜索树,也非HB(" << object.getK() << ")树" << endl; return false; } if (arrange.top().lh > object.getK()) { cout << "存在左右子树高度差绝对值大于" << object.getK() << "的子树,原树非HB(" << object.getK() << ")树" << endl; return false; } if (ptr == dest) return true; T lmin = arrange.top().lmin; int lh = arrange.top().lh; arrange.pop(); if (arrange.top().direction == 1) { arrange.top().lmin = lmin; arrange.top().lh = lh + 1; lmax = ptr->data; } else { rmin = lmin; rmax = ptr->data; rh = lh + 1; } } else { if (rmin <= ptr->data) { cout << "当前树非二叉搜索树,也非HB(" << object.getK() << ")树" << endl; return false; } if (abs(rh - arrange.top().lh) > object.getK()) { cout << "存在左右子树高度差绝对值大于" << object.getK() << "的子树,原树非HB(" << object.getK() << ")树" << endl; return false; } if (ptr == dest) return true; if (ptr->left == nullptr) { arrange.pop(); if (arrange.top().direction == 1) { arrange.top().lmin = ptr->data; lmax = rmax; arrange.top().lh = rh + 1; } else { rmin = ptr->data; ++rh; } } else { T lmin = arrange.top().lmin; int lh = arrange.top().lh; arrange.pop(); if (arrange.top().direction == 1) { arrange.top().lmin = lmin; arrange.top().lh = max(lh, rh) + 1; lmax = rmax; } else { rmin = lmin; rh = max(lh, rh) + 1; } } } } ptr = arrange.top().p; d = arrange.top().direction; } else { HB_kTreeNode<T>* interval = nullptr; if (d == 0) { arrange.push(memory(ptr, Searchd(ptr, d))); if (arrange.top().direction == 1) ptr = ptr->left; else ptr = ptr->right; } else { if (ptr->data <= lmax) { cout << "当前树非二叉搜索树,也非HB(" << object.getK() << ")树" << endl; return false; } arrange.top().direction = 2; ptr = ptr->right; } d = 0; } } } template <typename T> bool executeDelete(HB_kTreeNode<T>*& parent, HB_kTreeNode<T>*& q, HB_kTreeNode<T>* p, HB_kTreeNode<T>* left_or_right, stack<HB_kTreeNode<T>*>& stackforflashback) { if (stackforflashback.empty()) //被删节点有父节点 { parent = left_or_right; delete p; //删除被删节点后原AVL树恢复平衡,parent为根节点结束 return true; } parent = stackforflashback.top(); stackforflashback.pop(); if (parent->left == p) parent->left = left_or_right; //将被删节点左子树或右子树链接至被删节点父节点相应链指针，并删除被删节点 else parent->right = left_or_right; q = left_or_right; //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树或右子树根节点指针 delete p; return false; } template <typename T> void executeDelete(HB_kTreeNode<T>*& q, HB_kTreeNode<T>* p, HB_kTreeNode<T>*& left_or_right) { left_or_right = q->right; //left_o_right为parent->left时用该节点数据域替换被删节点数据域,将其右子树链接至其父节点左链指针,随后删除该节点 p->data = q->data; //left_o_right为p->right时用被删节点右子女数据域替换被删节点指针域,将右子女右子树链接至被删节点右链指针,并删除右子女 delete q; q = left_or_right; //left_o_right为parent->left时parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针 } template <typename T> void linkWithUpper(HB_kTreeNode<T>* parent, HB_kTreeNode<T>* original, HB_kTreeNode<T>* _new) { if (original == parent->left) { parent->left = _new; } else { parent->right = _new; } } template <typename T> bool HB_kTree<T>::remove(const T& key) { HB_kTreeNode<T>* p = root; stack<HB_kTreeNode<T>*> stackforflashback; while (p != nullptr) //搜索被删除节点,同时将回溯路径记录在栈中 { if (p->data == key) break; else { stackforflashback.push(p); if (key < p->data) { p = p->left; } else { p = p->right; } } } if (p != nullptr) //被删除节点存在,被p指向 { HB_kTreeNode<T>* parent = nullptr; HB_kTreeNode<T>* q = nullptr; if (p->left != nullptr && p->right != nullptr) //被删节点左右子树均存在 { q = p->right; parent = p; if (q->left != nullptr) //被删节点右子树根节点有左子树 { while (q->left != nullptr) //在被删节点右子树根节点左子树中搜索中序遍历的第一个节点,同时用栈记录回溯路径 { stackforflashback.push(parent); parent = q; q = q->left; } executeDelete(q, p, parent->left); } else executeDelete(q, p, p->right); } else { if (p->left != nullptr) //被删节点左子树不空,右子树空 { if (executeDelete(parent, q, p, p->left, stackforflashback)) { root = parent; return true; } } else if (p->right != nullptr) //处理过程和以上情形完全对称 { if (executeDelete(parent, q, p, p->right, stackforflashback)) { root = parent; return true; } } else //被删节点为叶节点 { if (executeDelete(parent, q, p, static_cast<HB_kTreeNode<T>*>(nullptr), stackforflashback)) { root = parent; return true; } } } bool TF = false; if (parent->right == nullptr && parent->left == nullptr) { parent->bf = 0; if (stackforflashback.empty()) return true; q = parent; parent = stackforflashback.top(); stackforflashback.pop(); } enum class result {link_over, link_back, over, back}; result before; //为true结束平衡化,为false向上回溯 do { if (TF == true) { if (before == result::back || before == result::link_back) { if (before == result::link_back) linkWithUpper(stackforflashback.top(), parent, q); else q = parent; parent = stackforflashback.top(); } else { if (before == result::link_over) linkWithUpper(stackforflashback.top(), parent, q); return true; } stackforflashback.pop(); } else TF = true; if (parent->left == q) { if (parent->bf == 0) { parent->bf = 1; before = result::over; } else if (parent->bf > 0) { if (parent->bf != k) { ++parent->bf; before = result::over; } else { q = parent->right; if (q->bf == -k) { p = q->left; RotateRL(parent); } else RotateL(parent); if (q->bf == 0) { q->bf = -1; before = result::link_over; } else if (q->bf > 0) { parent->bf = k - q->bf; --q->bf; before = result::link_back; } else if (q->bf != -k) { --q->bf; before = result::link_over; } else { if (p->bf == 0) { parent->bf = k - 1; q->bf = 1 - k; } else if (p->bf > 0) { parent->bf = k - 1 - p->bf; q->bf = 1 - k; p->bf = min(p->bf, k - 1); } else { parent->bf = k - 1; q->bf = 1 - k - p->bf; p->bf = max(p->bf, 1 - k); } before = result::link_back; q = p; } } } else { ++parent->bf; before = result::back; } } else { if (parent->bf == 0) { parent->bf = -1; before = result::over; } else if (parent->bf < 0) { if (parent->bf != -k) { --parent->bf; before = result::over; } else { q = parent->left; if (q->bf == k) { p = q->right; RotateLR(parent); } else RotateR(parent); if (q->bf == 0) { q->bf = 1; before = result::link_over; } else if (q->bf < 0) { parent->bf = -k - q->bf; ++q->bf; before = result::link_back; } else if (q->bf != k) { ++q->bf; before = result::link_over; } else { if (p->bf == 0) { parent->bf = 1 - k; q->bf = k - 1; } else if (p->bf > 0) { parent->bf = 1 - k; q->bf = k - 1 - p->bf; p->bf = min(p->bf, k - 1); } else { parent->bf = 1 - k - p->bf; q->bf = k - 1; p->bf = max(p->bf, 1 - k); } before = result::link_back; q = p; } } } else { --parent->bf; before = result::back; } } } while (stackforflashback.empty() == false); if (before == result::back || before == result::link_back) { if (before == result::link_back) root = q; } else { if (before == result::link_over) root = q; } return true; } else { cout << "HB(k)树中不存在要删除的数据元素,删除失败" << endl; return false; } } template <typename T> bool HB_kTree<T>::insert(const T& key) { if (root == nullptr) { root = new HB_kTreeNode<T>(0, key); return true; } stack<HB_kTreeNode<T>*> stackforflashback; HB_kTreeNode<T>* p = root; while (p != nullptr) //搜索插入位置 { stackforflashback.push(p); if (key < p->data) p = p->left; else if (key > p->data) p = p->right; else { cout << "要插入的关键字在AVL树中已存在,插入失败" << endl; return false; } } p = new HB_kTreeNode<T>(0, key); if (key < stackforflashback.top()->data) { stackforflashback.top()->left = p; //新节点插入并调整父节点平衡因子 } else { stackforflashback.top()->right = p; } HB_kTreeNode<T>* parent = nullptr; while (stackforflashback.empty() == false) { parent = stackforflashback.top(); stackforflashback.pop(); if (p == parent->left) { --parent->bf; if (parent->bf >= 0) return true; else if (parent->bf >= -k) { p = parent; } else { if (p->bf > 0) { HB_kTreeNode<T>* m = p->right; RotateLR(parent); if (m->bf > 0) { parent->bf = 1 - k; long long temp_p_bf = p->bf; p->bf = p->bf - m->bf - 1; m->bf = min(m->bf, temp_p_bf - 1); } else if (m->bf < 0) { parent->bf = -k + 1 - m->bf; m->bf = max(m->bf, 1 - k); --p->bf; } p = m; } else { RotateR(parent); parent->bf = -k - p->bf; ++p->bf; } } } else { ++parent->bf; if (parent->bf <= 0) return true; else if (parent->bf <= k) { p = parent; } else { if (p->bf < 0) { HB_kTreeNode<T>* m = p->left; RotateRL(parent); if (m->bf > 0) { parent->bf = k - 1 - m->bf; m->bf = min(m->bf, k - 1); ++p->bf; } else { parent->bf = k - 1; long long temp_p_bf = p->bf; p->bf = p->bf + 1 - m->bf; m->bf = max(temp_p_bf + 1, m->bf); } p = m; } else { RotateL(parent); parent->bf = k - p->bf; --p->bf; } } } if (p != parent) { if (stackforflashback.empty() == false) { linkWithUpper(stackforflashback.top(), parent, p); return true; //返回恢复平衡的AVL树根节点 } root = p; return true; } } return true; } int main() { const int k = 2; const int N = 2000; vector<int> insertvalue; for (int i = 1; i <= N; ++i) { insertvalue.push_back(i); } shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine()); HB_kTree<int> test_tree(k); for (vector<int>::const_iterator p = insertvalue.cbegin(); p != insertvalue.cend(); ++p) { cout << "插入节点" << *p << endl; test_tree.insert(*p); //test_tree.printTree(); cout << endl; if (isHBTree(test_tree) == true) { cout << "当前树是HB("<< k << ")树"; cout << endl; } else { cerr << "错误当前树不是HB("<< k << ")树!" << endl; exit(0); } } cout << endl; //test_tree.printTree(); cout << endl; for (vector<int>::const_iterator p = insertvalue.cbegin(); p != insertvalue.cend(); ++p) { cout << "删除节点" << *p << endl; test_tree.remove(*p); //test_tree.printTree(); if (test_tree.isEmpty() == false) { cout << endl; if (isHBTree(test_tree) == true) { cout << "当前树是HB(" << k << ")树"; cout << endl; } else { cerr << "错误当前树不是HB(" << k << ")树!" << endl; exit(0); } } else cout << "NULL"; cout << endl; } return 0; }