【C++】手撕AVL树（上） https://developer.aliyun.com/article/1565623
🌙AVL树的旋转
在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，采用不同的旋转方法。
AVL树的旋转分为四种：
- 左单旋（LL）
- 右单旋（RR）
- 左右双旋（LR）
- 右左双旋（RL）
旋转规则：
- 让这颗子树左右高度差不超过1
- 旋转过程中继续保持它是搜索树
- 更新调整孩子节点的平衡因子
- 让这颗子树的高度根插入前保持一致
💫左单旋
左单旋的步骤如下：
- 先让 subR 的左子树（subRL）作为 parent 的右子树。
- 然后让 parent 作为 subR 的左子树。
- 接下来让 subR 作为整个子树的根。
- 最后更新平衡因子
我们就以下面的抽象图来看看左单旋如何实现：
代码示例：
// 左单旋（右边高需要左单旋） void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode = parent->_parent; // 先保存parent的parent // 1.建立parent和subRL之间的关系 parent->_right = subRL; if (subRL) // 如果subRL节点不为空，那么要更新它的parent { subRL->_parent = parent; } // 2.建立subR和parent之间的关系 subR->_left = parent; parent->_parent = subR; // 3.建立ppNode和subR之间的关系（分情况讨论parent是整颗树的根，还是局部子树） if (parent == _root) // 当parent是根节点时 { _root = subR; // subR就变成了新的根节点 _root->_parent = nullptr; // 根节点的的parent为空 } else // 当parent是整个树的局部子树时 { if (parent == ppNode->_left) // 如果parent在ppNode的左边 { ppNode->_left = subR; // 那么subR就是parent的左子树 } else // 如果parent在ppNode的右边 { ppNode->_right = subR; // 那么subR就是parent的右子树 } subR->_parent = ppNode; // subR的parent还要指向ppNode } // 更新平衡因子 parent->_bf = 0; subR->_bf = 0; }
💫右单旋
右单旋的步骤如下：
- 先让 subL 的右子树（subLR）作为 parent 的左子树。
- 然后让 parent 作为 subL 的右子树。
- 接下来让 subL 作为整个子树的根。
- 最后更新平衡因子。
我们就以下面的抽象图来看看右单旋如何实现：
代码示例：
// 右单旋（左边高就右单旋） void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode = parent->_parent; // 1.建立parent和subLR之间的关系 parent->_left = subLR; if (subLR) // 如果subLR节点不为空，那么要更新它的parent { subLR->_parent = parent; } // 2.建立subL和parent之间的关系 subL->_right = parent; parent->_parent = subL; // 3.建立ppNode和subL之间的关系（分情况讨论parent是整颗树的根，还是局部子树） if (parent == _root) // 当parent是根节点时 { _root = subL; // subL就变成了新的根节点 _root->_parent = nullptr; // 根节点的的parent为空 } else // 当parent是整个树的局部子树时 { if (parent == ppNode->_left) // 如果parent在ppNode的左边 { ppNode->_left = subL; // 那么subL就是parent的左子树 } else // 如果parent在ppNode的右边 { ppNode->_right = subL; // 那么subL就是parent的右子树 } subL->_parent = ppNode; // subR的parent还要指向ppNode } // 更新平衡因子 parent->_bf = 0; subL->_bf = 0; }
💫左右单旋
左右单旋的步骤如下：
- 先以 subL 为旋转点进行左单旋。
- 然后以 parent 为旋转点进行右单旋。
- 最后再更新平衡因子。
我们就以下面的抽象图来看看左右单旋如何实现：
再次分类讨论：
（1）当 subLR 原始平衡因子是 -1 时，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 1、0、0
（2）当 subLR 原始平衡因子是 1 时，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、-1、0
（3）当 subLR 原始平衡因子是 0 时（说明 subLR 为新增结点），左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、0、0
代码示例：
// 左右双旋（先左单旋，再右单旋） void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; // 1.先以subL为旋转点进行左单旋 RotateL(parent->_left); // 2.再以parent为旋转点进行右单旋 RotateR(parent); // 3.更新平衡因子 if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else { // 如果走到了这里，说明subLR的平衡因子在旋转前就有问题 assert(false); } }
💫右左单旋
右左单旋的步骤如下：
- 先以 subR 为旋转点进行右单旋。
- 然后以 parent 为旋转点进行左单旋。
- 最后再更新平衡因子。
我们就以下面的抽象图来看看右左单旋如何实现：
再次分类讨论：
（1）当 subRL 原始平衡因子是 1 时，左右双旋后 parent、subR、subRL 的平衡因子分别更新为 -1、0、0
（2）当 subRL 原始平衡因子是 -1 时，左右双旋后 parent、subR、subRL 的平衡因子分别更新为 0、1、0
（3）当 subRL 原始平衡因子是 0 时（说明 subRL为新增结点），左右双旋后 parent、subR、subRL 的平衡因子分别更新为0、0、0
代码示例：
// 右左双旋（先右单旋，再左单旋） void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; // 1.先以subR为旋转点进行右单旋 RotateR(parent->_right); // 2.再以parent为旋转点进行左单旋 RotateL(parent); // 3.更新平衡因子 if (bf == 0) { subRL->_bf = 0; parent->_bf = 0; subR->_bf = 0; } else if (bf == 1) { subRL->_bf = 0; parent->_bf = -1; subR->_bf = 0; } else if (bf == -1) { subRL->_bf = 0; parent->_bf = 0; subR->_bf = 1; } else { // 如果走到了这里，说明subRL的平衡因子在旋转前就有问题 assert(false); } }
🌙AVL树的删除
这里的删除过于复杂，我这里就直接上代码了，如果对这里感兴趣的小伙伴们可以查阅资料。
// 删除函数 bool Erase(const K& key) { //用于遍历二叉树 Node* parent = nullptr; Node* cur = _root; //用于标记实际的删除结点及其父结点 Node* delParentPos = nullptr; Node* delPos = nullptr; while (cur) { if (key < cur->_kv.first) //所给key值小于当前结点的key值 { //往该结点的左子树走 parent = cur; cur = cur->_left; } else if (key > cur->_kv.first) //所给key值大于当前结点的key值 { //往该结点的右子树走 parent = cur; cur = cur->_right; } else //找到了待删除结点 { if (cur->_left == nullptr) //待删除结点的左子树为空 { if (cur == _root) //待删除结点是根结点 { _root = _root->_right; //让根结点的右子树作为新的根结点 if (_root) _root->_parent = nullptr; delete cur; //删除原根结点 return true; //根结点无祖先结点，无需进行平衡因子的更新操作 } else { delParentPos = parent; //标记实际删除结点的父结点 delPos = cur; //标记实际删除的结点 } break; //删除结点有祖先结点，需更新平衡因子 } else if (cur->_right == nullptr) //待删除结点的右子树为空 { if (cur == _root) //待删除结点是根结点 { _root = _root->_left; //让根结点的左子树作为新的根结点 if (_root) _root->_parent = nullptr; delete cur; //删除原根结点 return true; //根结点无祖先结点，无需进行平衡因子的更新操作 } else { delParentPos = parent; //标记实际删除结点的父结点 delPos = cur; //标记实际删除的结点 } break; //删除结点有祖先结点，需更新平衡因子 } else //待删除结点的左右子树均不为空 { //替换法删除 //寻找待删除结点右子树当中key值最小的结点作为实际删除结点 Node* minParent = cur; Node* minRight = cur->_right; while (minRight->_left) { minParent = minRight; minRight = minRight->_left; } cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的key cur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的value delParentPos = minParent; //标记实际删除结点的父结点 delPos = minRight; //标记实际删除的结点 break; //删除结点有祖先结点，需更新平衡因子 } } } if (delParentPos == nullptr) //delParentPos没有被修改过，说明没有找到待删除结点 { return false; } //记录待删除结点及其父结点（用于后续实际删除） Node* del = delPos; Node* delP = delParentPos; //更新平衡因子 while (delPos != _root) //最坏一路更新到根结点 { if (delPos == delParentPos->_left) //delParentPos的左子树高度降低 { delParentPos->_bf++; //delParentPos的平衡因子++ } else if (delPos == delParentPos->_right) //delParentPos的右子树高度降低 { delParentPos->_bf--; //delParentPos的平衡因子-- } //判断是否更新结束或需要进行旋转 if (delParentPos->_bf == 0)//需要继续往上更新平衡因子 { //delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子 delPos = delParentPos; delParentPos = delParentPos->_parent; } else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新结束 { break; //delParent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子 } else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转（此时delParentPos树已经不平衡了） { if (delParentPos->_bf == -2) { if (delParentPos->_left->_bf == -1) { Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点 RotateR(delParentPos); //右单旋 delParentPos = tmp; //更新根结点 } else if (delParentPos->_left->_bf == 1) { Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点 RotateLR(delParentPos); //左右双旋 delParentPos = tmp; //更新根结点 } else //delParentPos->_left->_bf == 0 { Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点 RotateR(delParentPos); //右单旋 delParentPos = tmp; //更新根结点 //平衡因子调整 delParentPos->_bf = 1; delParentPos->_right->_bf = -1; break; //更正 } } else //delParentPos->_bf == 2 { if (delParentPos->_right->_bf == -1) { Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点 RotateRL(delParentPos); //右左双旋 delParentPos = tmp; //更新根结点 } else if (delParentPos->_right->_bf == 1) { Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点 RotateL(delParentPos); //左单旋 delParentPos = tmp; //更新根结点 } else //delParentPos->_right->_bf == 0 { Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点 RotateL(delParentPos); //左单旋 delParentPos = tmp; //更新根结点 //平衡因子调整 delParentPos->_bf = -1; delParentPos->_left->_bf = 1; break; //更正 } } //delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子 delPos = delParentPos; delParentPos = delParentPos->_parent; //break; //error } else { assert(false); //在删除前树的平衡因子就有问题 } } //进行实际删除 if (del->_left == nullptr) //实际删除结点的左子树为空 { if (del == delP->_left) //实际删除结点是其父结点的左孩子 { delP->_left = del->_right; if (del->_right) del->_right->_parent = parent; } else //实际删除结点是其父结点的右孩子 { delP->_right = del->_right; if (del->_right) del->_right->_parent = parent; } } else //实际删除结点的右子树为空 { if (del == delP->_left) //实际删除结点是其父结点的左孩子 { delP->_left = del->_left; if (del->_left) del->_left->_parent = parent; } else //实际删除结点是其父结点的右孩子 { delP->_right = del->_left; if (del->_left) del->_left->_parent = parent; } } delete del; //实际删除结点 return true; }
🌙AVL树的遍历
中序是递归遍历（左 根 右），由于涉及到传参，所以需要写一个子函数。
代码实现：
// 中序遍历 void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); // 走左 cout << root->_kv.first << "[" << root->_bf << "]" << endl; // 遍历根 _InOrder(root->_right); // 走右 } void InOrder() { _InOrder(_root); }
🌙AVL树的查找
查找步骤：
- 若 key 值小于当前结点的值，则应该在该结点的左子树当中进行查找。
- 若 key 值大于当前结点的值，则应该在该结点的右子树当中进行查找。
- 若 key 值等于当前结点的值，则查找成功，返回对应结点。
代码实现：
// 查找元素 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return NULL; }
🌙AVL树的高度
由于涉及到传参，所以需要写一个子函数。
代码实现：
// 计算树的高度 int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } int Height() { return _Height(_root); }
🌙AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分为下面两步：
（1）验证其为二叉搜索树
- 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
// 计算树的高度 int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } int Height() { return _Height(_root); }
（2）验证其为平衡树
- 每个节点子树高度差的绝对值不超过 1（注意节点中如果没有平衡因子）
- 节点的平衡因子是否计算正确
🌙AVL树的高度
//求高度 int Height(Node* root) { if (root == nullptr) return 0; int lh = Height(root->_left); int rh = Height(root->_right); return lh > rh ? lh + 1 : rh + 1; } //判断平衡 bool IsBalance(Node* root) { if (root == nullptr) { return true; } int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } return abs(rightHeight - leftHeight) < 2 && IsBalance(root->_left) && IsBalance(root->_right); }
🌙AVL树优缺点
优点：
- 平衡二叉树的优点不言而喻，相对于二叉排序树（BST）而言，平衡二叉树避免了二叉排序树可能出现的最极端情况（斜树）问题，其平均查找的时间复杂度为 O ( l o g N ) O(logN)O(logN)
缺点：
- 平衡二叉树为了保持平衡，动态进行插入和删除操作的代价也会增加。因此出现了后来的红黑树
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查询时高效的时间复杂度，即O ( l o g N ) O(logN)O(logN)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但一个结构经常修改，就不太适合。
🌙整体代码
#include <iostream> #include <assert.h> #include<vector> #include <time.h> using namespace std; // 创建AVL树的结点 template<class K,class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left; // 左子树 AVLTreeNode<K, V>* _right; // 右子树 AVLTreeNode<K, V>* _parent;// 父亲结点 pair<K, V> _kv; // 存储的键值对 int _bf; // 平衡因子（右子树高度 - 左子树高度） // 构造函数 AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} }; template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: // 插入元素 bool Insert(const pair<K, V>& kv) { if (_root == nullptr) // 如果没有结点 { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) // 采用循环查找要插入的结点 { if (cur->_kv.first < kv.first) // 插入的元素大于cur就走右子树 { parent = cur; cur = cur->_right; } else if (cur->_kv.first < kv.first) // 插入的元素小于cur就走左子树 { parent = cur; cur = cur->_left; } else return false; } cur = new Node(kv);// 创建一个结点 // 链接 if (parent->_kv.first < kv.first) parent->_right = cur; else parent->_left = cur; cur->_parent = parent; // 循环判断插入结点的平衡因子和AVL树是否正确 while (parent) { // 判断插入的节点在父亲的右边还是左边 if (cur == parent->_left) // 在左边就父亲平衡因子减一 parent->_bf--; else // 在右边就父亲平衡因子加一 parent->_bf++; if (parent->_bf == 0) // 如果父亲的平衡因子为 0 该树就是健康的不用改变 break; else if (parent->_bf == 1 || parent->_bf == -1) // 这时需要向上调整每个节点的平衡因子 { cur = cur->_parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) // 需要旋转处理 { // 旋转处理 if (parent->_bf == 2 && cur->_bf == 1) // 左单旋 { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋 { RotateR(parent); } else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋 { RotateLR(parent); } else // 右左双旋 { RotateRL(parent); } break; } else { // 插入之前AVL树就有问题 assert(false); } } } // 左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* ppnode = parent->_parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } parent->_bf = 0; subR->_bf = 0; } // 右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* ppnode = parent->_parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } subL->_bf = 0; parent->_bf = 0; } // 左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == -1) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); } } // 右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); subRL->_bf = 0; if (bf == 1) { subR->_bf = 0; parent->_bf = -1; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; } else { parent->_bf = 0; subR->_bf = 0; } } // 中序遍历 void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); // 走左 cout << root->_kv.first << "[" << root->_bf << "]" << endl; // 遍历根 _InOrder(root->_right); // 走右 } void InOrder() { _InOrder(_root); } // 计算树的高度 int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } int Height() { return _Height(_root); } // 判断是否平衡 bool _IsBalance(Node* root, int& height) { if (root == nullptr) { height = 0; return true; } int leftHeight = 0, rightHeight = 0; if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)) { return false; } if (abs(rightHeight - leftHeight) >= 2) { cout << root->_kv.first << "不平衡" << endl; return false; } if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; return true; } bool IsBalance() { int height = 0; return _IsBalance(_root, height); } // 计算树的结点个数 size_t _Size(Node* root) { if (root == NULL) return 0; return _Size(root->_left) + _Size(root->_right) + 1; } size_t Size() { return _Size(_root); } // 查找元素 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return NULL; } // 删除函数 bool Erase(const K& key) { //用于遍历二叉树 Node* parent = nullptr; Node* cur = _root; //用于标记实际的删除结点及其父结点 Node* delParentPos = nullptr; Node* delPos = nullptr; while (cur) { if (key < cur->_kv.first) //所给key值小于当前结点的key值 { //往该结点的左子树走 parent = cur; cur = cur->_left; } else if (key > cur->_kv.first) //所给key值大于当前结点的key值 { //往该结点的右子树走 parent = cur; cur = cur->_right; } else //找到了待删除结点 { if (cur->_left == nullptr) //待删除结点的左子树为空 { if (cur == _root) //待删除结点是根结点 { _root = _root->_right; //让根结点的右子树作为新的根结点 if (_root) _root->_parent = nullptr; delete cur; //删除原根结点 return true; //根结点无祖先结点，无需进行平衡因子的更新操作 } else { delParentPos = parent; //标记实际删除结点的父结点 delPos = cur; //标记实际删除的结点 } break; //删除结点有祖先结点，需更新平衡因子 } else if (cur->_right == nullptr) //待删除结点的右子树为空 { if (cur == _root) //待删除结点是根结点 { _root = _root->_left; //让根结点的左子树作为新的根结点 if (_root) _root->_parent = nullptr; delete cur; //删除原根结点 return true; //根结点无祖先结点，无需进行平衡因子的更新操作 } else { delParentPos = parent; //标记实际删除结点的父结点 delPos = cur; //标记实际删除的结点 } break; //删除结点有祖先结点，需更新平衡因子 } else //待删除结点的左右子树均不为空 { //替换法删除 //寻找待删除结点右子树当中key值最小的结点作为实际删除结点 Node* minParent = cur; Node* minRight = cur->_right; while (minRight->_left) { minParent = minRight; minRight = minRight->_left; } cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的key cur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的value delParentPos = minParent; //标记实际删除结点的父结点 delPos = minRight; //标记实际删除的结点 break; //删除结点有祖先结点，需更新平衡因子 } } } if (delParentPos == nullptr) //delParentPos没有被修改过，说明没有找到待删除结点 { return false; } //记录待删除结点及其父结点（用于后续实际删除） Node* del = delPos; Node* delP = delParentPos; //更新平衡因子 while (delPos != _root) //最坏一路更新到根结点 { if (delPos == delParentPos->_left) //delParentPos的左子树高度降低 { delParentPos->_bf++; //delParentPos的平衡因子++ } else if (delPos == delParentPos->_right) //delParentPos的右子树高度降低 { delParentPos->_bf--; //delParentPos的平衡因子-- } //判断是否更新结束或需要进行旋转 if (delParentPos->_bf == 0)//需要继续往上更新平衡因子 { //delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子 delPos = delParentPos; delParentPos = delParentPos->_parent; } else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新结束 { break; //delParent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子 } else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转（此时delParentPos树已经不平衡了） { if (delParentPos->_bf == -2) { if (delParentPos->_left->_bf == -1) { Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点 RotateR(delParentPos); //右单旋 delParentPos = tmp; //更新根结点 } else if (delParentPos->_left->_bf == 1) { Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点 RotateLR(delParentPos); //左右双旋 delParentPos = tmp; //更新根结点 } else //delParentPos->_left->_bf == 0 { Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点 RotateR(delParentPos); //右单旋 delParentPos = tmp; //更新根结点 //平衡因子调整 delParentPos->_bf = 1; delParentPos->_right->_bf = -1; break; //更正 } } else //delParentPos->_bf == 2 { if (delParentPos->_right->_bf == -1) { Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点 RotateRL(delParentPos); //右左双旋 delParentPos = tmp; //更新根结点 } else if (delParentPos->_right->_bf == 1) { Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点 RotateL(delParentPos); //左单旋 delParentPos = tmp; //更新根结点 } else //delParentPos->_right->_bf == 0 { Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点 RotateL(delParentPos); //左单旋 delParentPos = tmp; //更新根结点 //平衡因子调整 delParentPos->_bf = -1; delParentPos->_left->_bf = 1; break; //更正 } } //delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子 delPos = delParentPos; delParentPos = delParentPos->_parent; //break; //error } else { assert(false); //在删除前树的平衡因子就有问题 } } //进行实际删除 if (del->_left == nullptr) //实际删除结点的左子树为空 { if (del == delP->_left) //实际删除结点是其父结点的左孩子 { delP->_left = del->_right; if (del->_right) del->_right->_parent = parent; } else //实际删除结点是其父结点的右孩子 { delP->_right = del->_right; if (del->_right) del->_right->_parent = parent; } } else //实际删除结点的右子树为空 { if (del == delP->_left) //实际删除结点是其父结点的左孩子 { delP->_left = del->_left; if (del->_left) del->_left->_parent = parent; } else //实际删除结点是其父结点的右孩子 { delP->_right = del->_left; if (del->_left) del->_left->_parent = parent; } } delete del; //实际删除结点 return true; } private: Node* _root = nullptr; }; void TestAVLTree1() { //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; AVLTree<int, int> t; for (auto e : a) { if (e == 14) { int x = 0; } t.Insert(make_pair(e, e)); cout << e << "->" << t.IsBalance() << endl; } t.InOrder(); cout << t.IsBalance() << endl; } void TestAVLTree2() { const int N = 1000000; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); //cout << v.back() << endl; } size_t begin2 = clock(); AVLTree<int, int> t; for (auto e : v) { t.Insert(make_pair(e, e)); //cout << "Insert:" << e << "->" << t.IsBalance() << endl; } size_t end2 = clock(); cout << "Insert:" << end2 - begin2 << endl; cout << t.IsBalance() << endl; cout << "Height:" << t.Height() << endl; cout << "Size:" << t.Size() << endl; size_t begin1 = clock(); // 确定在的值 for (auto e : v) { t.Find(e); } // 随机值 for (size_t i = 0; i < N; i++) { t.Find((rand() + i)); } size_t end1 = clock(); cout << "Find:" << end1 - begin1 << endl; }
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
