1. AVL树概念
AVL树就是自平衡二叉查找树，为了解决二叉树退化为单链表，使得增删查改时间度为O(N)，这里采用控制平衡策略达到效率是O(logN)。
2. AVL树满足性质
每个节点的左右子树高度之差绝对不能超过1
- 左边插入（父节点高度差-1）
- 右边插入（父节点高度差+1）
- 不插入（自身节点高度差为0
3. AVL节点结构
template <class KEY, class VAULE> struct AVLtree_node { AVLtree_node<KEY, VAULE>* _left; //左节点指向 AVLtree_node<KEY, VAULE>* _right; //右节点指向 AVLtree_node<KEY, VAULE>* _parent; //父节点指向 pair<KEY, VAULE> _couple; //存储key/value int _balanceFactor; //平衡因子(左右子树高度差) AVLtree_node(const pair<KEY, VAULE>& couple) :_left(nullptr) :_right(nullptr) :_parent(nullptr) :_couple(couple) :_balanceFactor(0) {} };
4. 插入操作
插入阶段
根节点为空
new节点，改变根指向，返回true
根节点不为空
找到插入位置
右查找：当前节点key值 < 插入节点key值
左查找：当前节点key值 > 插入节点key值
当前节点key值 = 插入节点key值 ：直接返回false
在对应待插入位置插入
new节点，当前插入位置指向该节点
右插入：当前节点key值 < 插入节点key值
左插入: 当前节点key值 > 插入节点key值
当前被插入节点父指针指向指向被连接节点
自动平衡（TODO）
bool insert(const pair<KEY, VAULE>& couple) { //二叉搜索树阶段 if (_root == nullptr) //根为空:直接new并指向返回 { _root = new node(couple); return true; } /*找插入位置*/ node* parent = nullptr; //起初根节点的父节点为nullptr node* cur = _root; //被插入节点指向 while (cur) { if (cur->_couple.first < couple.first) //右查找：当前节点key值 < 插入节点key值 { parent = cur; cur = cur->_right; } else if (cur->_couple.first > couple.first) //左查找: 当前节点key值 > 插入节点key值 { parent = cur; cur = cur->_left; } else //当前节点key值 = 插入节点key值：直接退出 { return false; } } /*在对应位置插入*/ cur = new node(couple); if (parent->_couple.first > couple.first) //左插入: 当前节点key值 > 插入节点key值 { parent->_left = newnode; } else //右插入：当前节点key值 < 插入节点key值 { parent->_right = newnode; } cur->_parent = parent; //反向链接 /*自动平衡 TODO*/ //AVL树阶段 }
- 平衡阶段铺垫
注意：并没有画上父节点指向，为了便于观察所以没有画，默认每个节点是有父节点指向的
- 右边插入构图
- 左边插入构图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rGLjZnpU-1684114665514)(https://typora130.oss-cn-nanjing.aliyuncs.com/QQ截图20230513154519.png)]
上面左右插入构图示范中，观察发现该节点左右子树高度差超过了1就会形成子树单链表，这样就会影响到效率，那么这里的解决办法就是对其旋转处理（待解），另外观察到上面错误高度差情况，会发现一旦插入其被插入节点的部分祖先的平衡因子（高度差）可能改变，所以，插入新增节点会影响部分或全部祖先的平衡因子，平衡因子怎么来更新呢？如果新增节点在其父节点左边，父节点平衡因子-1，如果新增节点在其父节点右边，父节点平衡因子+1，每个节点的平衡因子初始状态都是0。是什么时候平衡因子更新？当插入节点的父节点的平衡因子变化（不为0），那么就需要对其被插入节点的部分或者全部祖先的平衡因子更新。
观察：右边插入三种情况示范：
被插入节点父节点平衡高度不为0，就向上更新祖先的平衡因子，向上更新的依据是该节点左右子树高度变化了；如果插入节点父节点平衡高度为0，就无需向上更新平衡因子
后面两种情况观察：当祖先节点的平衡因子为2或者-2时，就不应该再往上层更新平衡因子了（key值为7的节点的平衡因子就没必要更新了），因为此时只要有一个祖先的平衡因子为2说明就已经有问题了，就需要对这部分子树来调整达到一种平衡状态（旋转处理）。
自动平衡
更新平衡因子
改变被插入节点父节点平衡因子
被插入节点在其父节点右子树中：父节点平衡因子+1
被插入节点在其父节点左子树中：父节点平衡因子-1
判断是否继续向上更新平衡因子
父节点平衡因子为1或者-1，继续更新
父节点平衡因子为0，无需更新
父节点平衡因子为2或者-2，子树不平衡，旋转处理使得平衡（TODO）
bool insert(const pair<KEY, VAULE>& couple) { if (_root == nullptr) //根为空:直接new并指向返回 { _root = new node(couple); return true; } /*找插入位置*/ node* parent = nullptr; //起初根节点的父节点为nullptr node* cur = _root; //被插入节点指向 while (cur) { if (cur->_couple.first < couple.first) //右查找：当前节点key值 < 插入节点key值 { parent = cur; cur = cur->_right; } else if (cur->_couple.first > couple.first) //左查找: 当前节点key值 > 插入节点key值 { parent = cur; cur = cur->_left; } else //当前节点key值 = 插入节点key值：直接退出 { return false; } } /*在对应位置插入*/ cur = new node(couple); if (parent->_couple.first > couple.first) //左插入: 当前节点key值 > 插入节点key值 { parent->_left = newnode; } else //右插入：当前节点key值 < 插入节点key值 { parent->_right = newnode; } cur->_parent = parent; //反向链接 /*自动平衡 TODO*/ //更新平衡因子 while (parent) { if (cur == parent->_right) //被插入节点在其父节点右子树中 { parent->_balanceFactor++; } else //被插入节点在其父节点左子树中 { parent->_balanceFactor--; } if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) //继续更新平衡因子 { parent = parent->_parent; cur = cur->_parent; } else if (parent->_balanceFactor == 0) //无需更新 { break; } else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) //子树不平衡(旋转处理) { /*TODO*/ break; //旋转之后达到平衡无需更新平衡因子(操作完后便知) } else { assert(false); } } }
- 平衡阶段旋转处理
旋转目的：让子树平衡并且降低子树高度
- 左单旋
- 左单旋一定是右高左低
三个举例：
三个举例来抽象得到宏观图：
H为这颗子树高度，当H为0，反应就是上述第一个例子；当H为1，反应就是上述第二个例子；当H为2，反应就是上述第三个例子。当H为x时，其调整方法不变。当H为2时，此时有三种情况的高度为2的树：
但是这里c这棵子树必须是x类型的高度为2的树，a,b这两课子树可以是任意一种都可以。为什么c子树必须是x类型的树呢？如果是y型可能插入不会引发旋转，也可能只会局部旋转：
如何旋转？
- 让cur的左子树(curLeft)放在parent的右子树位置并且curLeft的父节点指向指向parent
- 让parent放在cur的左子树位置并且parent的父节点指向指向cur
- cur变为子树或者整颗树的根
- 更新parent和cur的平衡因子
//parent->_balanceFactor == 2 && cur->_balanceFactor = 1 void leftSingleRotate(node* parent) //左单旋 { //记录指针 node* parent_RightChild = parent->_right; //parent_RightChild = cur node* parent_RightChild_LeftChild = parentRightChild->_left; //parent_RightChild_LeftChild = curLeft node* parent_parent = parent->_parent; //局部根或整棵树根的父节点 parent->_right = parent_RightChild_LeftChild; //让cur的左子树(curLeft)放在parent的右子树位置 if (parent_RightChild_LeftChild != nullptr) //H为0时,parent_RightChild_LeftChild=nullptr { parent_RightChild_LeftChild->_parent = parent; //curLeft的父节点指向指向parent } parent_RightChild->_left = parent; //让parent放在cur的左子树位置 parent->_parent = parent_RightChild; //parent的父节点指向指向cur //cur(parent_RightChild)变为子树或者整颗树的根 if (parent_parent == nullptr) //parent是整颗树的根 { _root = parent_RightChild; _root->_parent = nullptr; } else //parent是局部子树的根 { if (parent_parent->_left == parent) //parent节点在父节点的左子树位置 { parent_parent->_left = parent_RightChild; } else //parent节点在父节点的右子树位置 { parent_parent->_right = parent_RightChild; } parent_RightChild->_parent = parent_parent; } //更新平衡因子 parent->_balanceFactor = parent_RightChild->_balanceFactor = 0; }
- 右单旋
- 右单旋一定是左高右低
三个举例来抽象得到宏观图
H为这颗子树高度，当H为0，反应就是上述第一个例子；当H为1，反应就是上述第二个例子；当H为2，反应就是上述第三个例子。当H为x时，其调整方法不变。当H为2时，这里的c子树必须是x类型的树，此时有三种情况的高度为2的树：
如何旋转？
- 让cur的右子树(curRight)放在parent的左子树位置并且让curRight父节点的指向指向parent
- 让parent放在cur的右子树位置并且让parent的父节点指向指向cur
- cur变为子树或者整颗树的根
- 更新parent和cur的平衡因子
//parent->_balanceFactor == -2 && cur->_balanceFactor == -1 void rightSingleRotate(node* parent) //右单旋 { //记录指针 node* parent_LeftChild = parent->_left; //parent_LeftChild = cur node* parent_LeftChild_RightChild = parent_LeftChild->_right; //parent_LeftChild_RightChild = curRight node* parent_parent = parent->_parent; //局部根或整棵树根的父节点 parent->_left = parent_LeftChild_RightChild; //让cur的右子树(curRight)放在parent的左子树位置 if (parent_LeftChild_RightChild != nullptr) { parent_LeftChild_RightChild->_parent = parent; //让curRight父节点的指向指向parent } parent_LeftChild->_right = parent; //让parent放在cur的右子树位置 parent->_parent = parent_LeftChild; //让parent的父节点指向指向cur //cur(parent_LeftChild)变为子树或者整颗树的根 if (parent_parent == nullptr) //parent是整颗树的根 { _root = parent_LeftChild; //cur(parent_LeftChild)就是根 _root->_parent = nullptr; } else //parent是局部子树的根 { if (parent_parent->_left == parent) //parent节点在父节点的左子树位置 { parent_parent->_left = parent_LeftChild; } else //parent节点在父节点的右子树位置 { parent_parent->_right = parent_LeftChild; } parent_LeftChild->_parent = parent_parent; //cur(parent_LeftChild)指向局部根的父节点 } //更新平衡因子 parent->_balanceFactor = parent_LeftChild->_balanceFactor = 0; }
- 先左后右旋
抽象图：
H为子树高度，H为0时，此时60这个节点也不存在，新增节点必须是key为60这个节点位置；H为1，2，3…等等图形这里不再画出，都可以通过抽象达成相同调整方法，这里被插入节点一定是b，c子树位置或者b，c的子树孩子位置。
如何旋转？
先左旋cur为根的子树
让cur的右指向指向curRightLeft并且curRightLeft的父节点的指向指向cur
让curRight的左指向指向cur并且cur的父节点的指向指向curRight
curRight作为子树根并且改变curRight的父节点的指向指向parent
更新cur和curRight的平衡因子为0
后右旋parent为根的子树
让parent的左指向指向curRightRight并且curRightRight的父节点的指向指向parent
让curRight的右子树指向parent并且parent的父节点的指向指向curRight
curRight作为树的根并且改变curRight的父节点指向指向空
更新parent和curRight的平衡因子为0
更新cur、curRight、parent平衡因子（插入b，c子树不同位置会导致最终平衡因子的变化）
c子树插入(curRight->_balanceFactor=1)：最终cur的平衡因子为-1，parent平衡因子为0，curRight平衡因子为0
b子树插入(curRight->_balanceFactor=-1)：最终cur的平衡因子为0，parent平衡因子为1，curRight平衡因子为0
curRight本身是被插入节点(curRight->_balanceFactor=0，H=0)，最终cur、parent、curRight平衡因子都为0
//parent->_balanceFactor == -2 && cur->_balanceFactor == 1 void leftRightRotate(node* parent) { node* parent_LeftChild = parent->_left; //parent_LeftChild = cur node* parent_LeftChild_RightChild = parent_LeftChild->_right; //parent_LeftChild_RightChild = curRight int balanceFactor = parent_LeftChild_RightChild->_balanceFactor; //记录curRight的平衡因子值：确定在b子树还是c子树插入 leftSingleRotate(parent->_left); //左单旋cur为根树 rightSingleRotate(parent); //右单旋parent为根的树 //更新cur、curRight、parent平衡因子（插入b，c子树不同位置会导致最终平衡因子的变化） if (balanceFactor == 1) //c子树插入 { parent->_balanceFactor = 0; parent_LeftChild_RightChild = 0; //curRight->_balanceFactor = 0 parent_LeftChild = -1; //cur->_balanceFactor = -1 } else if (balanceFactor == -1) //b子树插入 { parent->_balanceFactor = 1; parent_LeftChild_RightChild = 0; //curRight->_balanceFactor = 0 parent_LeftChild = 0; //cur->_balanceFactor = 0 } else if (balanceFactor == 0) //curRight自身是被插入节点 { parent->_balanceFactor = 0; parent_LeftChild_RightChild = 0; //curRight->_balanceFactor = 0 parent_LeftChild = 0; //cur->_balanceFactor = 0 } else { assert(false); } }
- 先右后左旋
抽象图：
H为子树高度，H为0时，此时60这个节点也不存在，新增节点必须是key为60这个节点位置；H为1，2，3…等等图形这里不再画出，都可以通过抽象达成相同调整方法，这里被插入节点一定是b，c子树位置或者b，c的子树孩子位置。
如何旋转？
先右旋cur为根的子树
让cur的左指向指向curLeftRight并且curLeftRight的父节点的指向指向cur
让curLeft的右指向指向cur并且cur的父节点的指向指向curLeft
curLeft作为子树的根并且curLeft的父节点的指向指向parent
更新cur和curLeft的平衡因子为0
后左旋parent为根的树
让parent的右指向指向curLeftLeft并且curLeftLeft的父节点的指向指向parent
让curLeft的左指向指向parent并且paren的父节点的指向指向curLeft
curLeft作为树的根并且改变curLeft的父节点的指向指向nullptr
更新parent和curLeft的平衡因子为0
更新cur、curLeft、parent平衡因子（插入b，c子树不同位置会导致最终平衡因子的变化）
b子树插入(curLeft->_balance=1)，最终cur的平衡因子为0，parent平衡因子为-1，curLeft平衡因子为0
c子树插入(curLeft->_balance=-1)，最终cur的平衡因子为1，parent平衡因子为0，curLeft平衡因子为0
curLeft本身是被插入节点(curLeft->_balanceFactor=0，H=0)，最终cur、parent、curRight平衡因子都为0
//parent->_balanceFactor == 2 && cur->_balanceFactor == -1 void rightLeftRotate(node* parent) //先右后左旋 { node* parent_RightChild = parent->_right; //parent_RightChild = cur node* parent_RightChild_LeftChild = parent_RightChild->_left; //parent_RightChild_LeftChild = curLeft int balanceFactor = parent_RightChild_LeftChild->_balanceFactor; 记录curLeft的平衡因子值：确定在b子树还是c子树插入 rightSingleRotate(parent_RightChild); //右单旋cur为根的树 leftSingleRotate(parent); //左单旋parent为根的树 //更新cur、curRight、parent平衡因子（插入b，c子树不同位置会导致最终平衡因子的变化） if (balanceFactor == 1) //b子树插入 { parent_RightChild->_balanceFactor = 0; //cur->_balanceFactor = 0 parent->_balanceFactor = -1; parent_RightChild_LeftChild->_balanceFactor = 0; //curLeft->_balanceFactor = 0; } else if (balanceFactor == -1) //c子树插入 { parent_RightChild->_balanceFactor = 1; //cur->_balanceFactor = 1 parent->_balanceFactor = 0; parent_RightChild_LeftChild->_balanceFactor = 0; //curLeft->_balanceFactor = 0; } else if (balanceFactor == 0) //curLeft本身是被插入节点 { parent_RightChild->_balanceFactor = 0; //cur->_balanceFactor = 0 parent->_balanceFactor = 0; parent_RightChild_LeftChild->_balanceFactor = 0; //curLeft->_balanceFactor = 0; } else { assert(false); } }
5. 检测
- 中序遍历是否升序
void inOrder() //中序遍历 { _inOrder(_root); cout << endl; } void _inOrder(node* root) //中序遍历 { if (root == nullptr) { return; } _inOrder(root->_left); cout << root->_couple.first << " "; _inOrder(root->_right); }
- 是否平衡
bool isBalance() //判断树是否为平衡树 { return _isBalance(_root); } int heightDiffer(node* root) { if (root == nullptr) return 0; int leftHeight = heightDiffer(root->_left); int rightHeight = heightDiffer(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } bool _isBalance(node* root) //判断树是否为平衡树(检查每个节点的左右子树高度差) { if (root == nullptr) return true; int leftHeight = heightDiffer(root->_left); int rightHeight = heightDiffer(root->_right); if (rightHeight - leftHeight != root->_balanceFactor) //不只是对高度检查还应该对平衡因子检查 { cout << "key:" << root->_couple.first << " node balanceFactor exception!" << endl; return false; } return abs(leftHeight - rightHeight) < 2 && _isBalance(root->_left) && _isBalance(root->_right); }
6. 完整代码
插入阶段
根节点为空
new节点，改变根指向，返回true
根节点不为空
找到插入位置
右查找：当前节点key值 < 插入节点key值
左查找：当前节点key值 > 插入节点key值
当前节点key值 = 插入节点key值 ：直接返回false
在对应待插入位置插入
new节点，当前插入位置指向该节点
右插入：当前节点key值 < 插入节点key值
左插入: 当前节点key值 > 插入节点key值
当前被插入节点父指针指向指向被连接节点
自动平衡
更新平衡因子
改变被插入节点父节点平衡因子
被插入节点在其父节点右子树中：父节点平衡因子+1
被插入节点在其父节点左子树中：父节点平衡因子-1
判断是否继续向上更新平衡因子
父节点平衡因子为1或者-1，继续更新
父节点平衡因子为0，无需更新
父节点平衡因子为2或者-2，子树不平衡，旋转处理使得平衡（旋转处理）
parent->_balanceFactor == 2 && cur->_balanceFactor == 1 --> 左单旋
parent->_balanceFactor == -2 && cur->_balanceFactor == -1 --> 右单旋
parent->_balanceFactor == -2 && cur->_balanceFactor == 1 --> 先左后右旋
parent->_balanceFactor == 2 && cur->_balanceFactor == -1 --> 先右后左旋
#pragma once #include <iostream> #include <utility> #include <cassert> using namespace std; template <class KEY, class VAULE> struct AVLtree_node { AVLtree_node<KEY, VAULE>* _left; //左节点指向 AVLtree_node<KEY, VAULE>* _right; //右节点指向 AVLtree_node<KEY, VAULE>* _parent; //父节点指向 pair<KEY, VAULE> _couple; //存储key/value int _balanceFactor; //平衡因子(左右子树高度差) AVLtree_node(const pair<KEY, VAULE>& couple) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_couple(couple) ,_balanceFactor(0) {} }; template <class KEY, class VAULE> class AVLtree { typedef AVLtree_node<KEY, VAULE> node; public: bool insert(const pair<KEY, VAULE>& couple) { if (_root == nullptr) //根为空:直接new并指向返回 { _root = new node(couple); return true; } /*找插入位置*/ node* parent = nullptr; //起初根节点的父节点为nullptr node* cur = _root; //被插入节点指向 while (cur) { if (cur->_couple.first < couple.first) //右查找：当前节点key值 < 插入节点key值 { parent = cur; cur = cur->_right; } else if (cur->_couple.first > couple.first) //左查找: 当前节点key值 > 插入节点key值 { parent = cur; cur = cur->_left; } else //当前节点key值 = 插入节点key值：直接退出 { return false; } } /*在对应位置插入*/ cur = new node(couple); if (parent->_couple.first > couple.first) //左插入: 当前节点key值 > 插入节点key值 { parent->_left = cur; } else //右插入：当前节点key值 < 插入节点key值 { parent->_right = cur; } cur->_parent = parent; //反向链接 /*自动平衡 TODO*/ //更新平衡因子 while (parent) { if (cur == parent->_right) //被插入节点在其父节点右子树中 { parent->_balanceFactor++; } else //被插入节点在其父节点左子树中 { parent->_balanceFactor--; } if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) //继续更新平衡因子 { parent = parent->_parent; cur = cur->_parent; } else if (parent->_balanceFactor == 0) { break; } else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) //子树不平衡(旋转处理) { if (parent->_balanceFactor == 2 && cur->_balanceFactor == 1) //左单旋 { leftSingleRotate(parent); } else if (parent->_balanceFactor == -2 && cur->_balanceFactor == -1) //右单旋 { rightSingleRotate(parent); } else if (parent->_balanceFactor == -2 && cur->_balanceFactor == 1) //先左后右旋 { leftRightRotate(parent); } else if (parent->_balanceFactor == 2 && cur->_balanceFactor == -1) //先右后左旋 { rightLeftRotate(parent); } else { assert(false); } //旋转可以达到左右子树平衡并且降低高度 break; } else { assert(false); } } return true; } void inOrder() //中序遍历 { _inOrder(_root); cout << endl; } bool isBalance() //判断树是否为平衡树 { return _isBalance(_root); } private: void leftSingleRotate(node* parent) //左单旋 { //记录指针 node* parent_RightChild = parent->_right; //parent_RightChild = cur node* parent_RightChild_LeftChild = parent_RightChild->_left; //parent_RightChild_LeftChild = curLeft node* parent_parent = parent->_parent; //局部根或整棵树根的父节点 parent->_right = parent_RightChild_LeftChild; //让cur的左子树(curLeft)放在parent的右子树位置 if (parent_RightChild_LeftChild != nullptr) //H为0时,parent_RightChild_LeftChild=nullptr { parent_RightChild_LeftChild->_parent = parent; //curLeft的父节点指向指向parent } parent_RightChild->_left = parent; //让parent放在cur的左子树位置 parent->_parent = parent_RightChild; //parent的父节点指向指向cur //cur(parent_RightChild)变为子树或者整颗树的根 if (parent_parent == nullptr) //parent是整颗树的根 { _root = parent_RightChild; //cur(parent_RightChild)就是根 _root->_parent = nullptr; } else //parent是局部子树的根 { if (parent_parent->_left == parent) //parent节点在父节点的左子树位置 { parent_parent->_left = parent_RightChild; } else //parent节点在父节点的右子树位置 { parent_parent->_right = parent_RightChild; } parent_RightChild->_parent = parent_parent; //cur(parent_RightChild)指向局部根的父节点 } //更新平衡因子 parent->_balanceFactor = parent_RightChild->_balanceFactor = 0; } void rightSingleRotate(node* parent) //右单旋 { //记录指针 node* parent_LeftChild = parent->_left; //parent_LeftChild = cur node* parent_LeftChild_RightChild = parent_LeftChild->_right; //parent_LeftChild_RightChild = curRight node* parent_parent = parent->_parent; //局部根或整棵树根的父节点 parent->_left = parent_LeftChild_RightChild; //让cur的右子树(curRight)放在parent的左子树位置 if (parent_LeftChild_RightChild != nullptr) { parent_LeftChild_RightChild->_parent = parent; //让curRight父节点的指向指向parent } parent_LeftChild->_right = parent; //让parent放在cur的右子树位置 parent->_parent = parent_LeftChild; //让parent的父节点指向指向cur //cur(parent_LeftChild)变为子树或者整颗树的根 if (parent_parent == nullptr) //parent是整颗树的根 { _root = parent_LeftChild; //cur(parent_LeftChild)就是根 _root->_parent = nullptr; } else //parent是局部子树的根 { if (parent_parent->_left == parent) //parent节点在父节点的左子树位置 { parent_parent->_left = parent_LeftChild; } else //parent节点在父节点的右子树位置 { parent_parent->_right = parent_LeftChild; } parent_LeftChild->_parent = parent_parent; //cur(parent_LeftChild)指向局部根的父节点 } //更新平衡因子 parent->_balanceFactor = parent_LeftChild->_balanceFactor = 0; } void leftRightRotate(node* parent) //先左后右旋 { node* parent_LeftChild = parent->_left; //parent_LeftChild = cur node* parent_LeftChild_RightChild = parent_LeftChild->_right; //parent_LeftChild_RightChild = curRight int balanceFactor = parent_LeftChild_RightChild->_balanceFactor; //记录curRight的平衡因子值：确定在b子树还是c子树插入 leftSingleRotate(parent->_left); //左单旋cur为根的树 rightSingleRotate(parent); //右单旋parent为根的树 //更新cur、curRight、parent平衡因子（插入b，c子树不同位置会导致最终平衡因子的变化） if (balanceFactor == 1) //c子树插入 { parent->_balanceFactor = 0; parent_LeftChild_RightChild = 0; //curRight->_balanceFactor = 0 parent_LeftChild->_balanceFactor = -1; //cur->_balanceFactor = -1 } else if (balanceFactor == -1) //b子树插入 { parent->_balanceFactor = 1; parent_LeftChild_RightChild = 0; //curRight->_balanceFactor = 0 parent_LeftChild->_balanceFactor = 0; //cur->_balanceFactor = 0 } else if (balanceFactor == 0) //curRight自身是被插入节点 { parent->_balanceFactor = 0; parent_LeftChild_RightChild = 0; //curRight->_balanceFactor = 0 parent_LeftChild->_balanceFactor = 0; //cur->_balanceFactor = 0 } else { assert(false); } } void rightLeftRotate(node* parent) //先右后左旋 { node* parent_RightChild = parent->_right; //parent_RightChild = cur node* parent_RightChild_LeftChild = parent_RightChild->_left; //parent_RightChild_LeftChild = curLeft int balanceFactor = parent_RightChild_LeftChild->_balanceFactor; 记录curLeft的平衡因子值：确定在b子树还是c子树插入 rightSingleRotate(parent_RightChild); //右单旋cur为根的树 leftSingleRotate(parent); //左单旋parent为根的树 //更新cur、curRight、parent平衡因子（插入b，c子树不同位置会导致最终平衡因子的变化） if (balanceFactor == 1) //b子树插入 { parent_RightChild->_balanceFactor = 0; //cur->_balanceFactor = 0 parent->_balanceFactor = -1; parent_RightChild_LeftChild->_balanceFactor = 0; //curLeft->_balanceFactor = 0; } else if (balanceFactor == -1) //c子树插入 { parent_RightChild->_balanceFactor = 1; //cur->_balanceFactor = 1 parent->_balanceFactor = 0; parent_RightChild_LeftChild->_balanceFactor = 0; //curLeft->_balanceFactor = 0; } else if (balanceFactor == 0) //curLeft本身是被插入节点 { parent_RightChild->_balanceFactor = 0; //cur->_balanceFactor = 0 parent->_balanceFactor = 0; parent_RightChild_LeftChild->_balanceFactor = 0; //curLeft->_balanceFactor = 0; } else { assert(false); } } void _inOrder(node* root) //中序遍历 { if (root == nullptr) { return; } _inOrder(root->_left); cout << root->_couple.first << " "; _inOrder(root->_right); } int heightDiffer(node* root) { if (root == nullptr) return 0; int leftHeight = heightDiffer(root->_left); int rightHeight = heightDiffer(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } bool _isBalance(node* root) //判断树是否为平衡树(检查每个节点的左右子树高度差) { if (root == nullptr) return true; int leftHeight = heightDiffer(root->_left); int rightHeight = heightDiffer(root->_right); if (rightHeight - leftHeight != root->_balanceFactor) //不只是对高度检查还应该对平衡因子检查 { cout << "key:" << root->_couple.first << " node balanceFactor exception!" << endl; return false; } return abs(leftHeight - rightHeight) < 2 && _isBalance(root->_left) && _isBalance(root->_right); } private: node* _root = nullptr; }; /*测试*/ void test_AVLtree1() { //int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14}; AVLtree<int, int> tree; for (auto x : arr) { tree.insert(make_pair(x, x)); } tree.inOrder(); //中序遍历 cout << tree.isBalance() << endl; //判断是否为平衡树 } void test_perfermance() //测试性能 { srand(time(nullptr)); const size_t N = 100000; AVLtree<int, int> tree; for (size_t i = 0; i < N; ++i) { size_t x = rand(); tree.insert(make_pair(x, x)); } cout << tree.isBalance() << endl; }
