平衡BST：AVL树的实现与机制
目录
AVL树的简介
AVL节点的构建
AVL树体的构建
具体片段解析
旋转算法
AVL树的验证
AVL树的简介
AVL树是一种自平衡的二叉搜索树，它在19世纪60年代由Adelson-Velsky和Landis首次提出。在AVL树中，任何节点的两个子树的高度最大差别为1，这种平衡确保了树的操作（如插入、删除和查找）的时间复杂度为O(log n)。下面是AVL树在C++中的基本概念：
基本概念：
- 节点：AVL树的每个节点包含关键值、指向左右子树的指针以及一个表示该节点高度或平衡因子的值。
- 平衡因子：节点左右子树的高度差。在AVL树中，每个节点的平衡因子只能是-1、0或1。
- 旋转：为了维护树的平衡，AVL树在插入或删除节点后可能会进行旋转。旋转分为四种类型：右旋、左旋、左右旋和右左旋。
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在LogN，时间复杂度也是LogN
因此AVL树的构建是十分繁琐的，但是效率及其高效。
AVL节点的构建
我们构建一个K/V结构的AVL树，用来存储键值对。
由于牵扯到树形的连接，因此我们采用三叉链的形式，内部存储三个指针
同时_bf（binary factor）平衡因子用来检测树书否符规范
template<typename K, typename V>
struct AVLTreeNode {//三叉连锁树的节点结构AVLTreeNode* _left; //C++将struct之后的部分升级成了类名，可以直接用来创建对象AVLTreeNode* _right;AVLTreeNode* _parent;pair<K, V> _kv;int _bf; //平衡因子，左子树的高度减去右子树的高度 balance factorAVLTreeNode(const pair<K, V>& kv): _left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv), //调用默认构造函数，初始化_kv_bf(0){}
};AVL树体的构建
成员变量只需要一个树根
Node* _root;
AVL树体重点是插入的实现
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子
插入具体分为三部分： //1.插入 2.连接 3.调整 
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 (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}//cur为空，说明找到了插入位置cur = new Node(kv);if (kv.first < parent->_kv.first){parent->_left = cur; //连接cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//调整（针对平衡因子）while (parent) //向上调整{if (cur == parent->_left)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0)break; //平衡else if (parent->_bf == 1 || parent->_bf == -1) //需要向上检查{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_right->_bf == -2) //调整（插入之前不可能为2或者-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)RotateRL(parent);else if (parent->_bf == -2 && cur->_bf == 1)RotateLR(parent);// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新break;}elseassert(false);}}
具体片段解析
1.空树直接插入
if (_root == nullptr) {_root = new Node(kv);return true;}
2.寻找合适的位置插入（找到空位置）
while (cur)
{if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}
}3.插入后进行连接
if (kv.first < parent->_kv.first)
{parent->_left = cur; //连接cur->_parent = parent;
}
else
{parent->_right = cur;cur->_parent = parent;
}4.进行平衡因子的调整（重难点）
4.1根据插入的位置，插入左树，_bf--，否则++
if (cur == parent->_left)parent->_bf--;elseparent->_bf++;
4.2平衡因子发生变化之后，进行调整
若插入之后，abs(_bf) == 1，那说明该树处于临界状态，此时需要向上检查
若abs(_bf) == 2,说明插入之后，树已经失衡，需要进行旋转调整
同时，旋转之后，不仅完成了树的平衡，还使得高度--，树变成了平衡状态
此时abs（parent->_bf) == 2,abs(cur->_bf) == 1，所以四种情况
if (parent->_bf == 0)break; //平衡
else if (parent->_bf == 1 || parent->_bf == -1) //需要向上检查
{cur = parent;parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_right->_bf == -2) //调整（插入之前不可能为2或者-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)RotateRL(parent);else if (parent->_bf == -2 && cur->_bf == 1)RotateLR(parent);// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新break;
}elseassert(false);旋转算法
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，
使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
1. 新节点插入较高左子树的左侧---左左：右单旋
核心就是对SubL 和SubRL（ 注意是否为空）这两个节点的处理。
同时需要注意parent是不是根节点
上图在插入前， AVL 树是平衡的，新节点插入到 30 的左子树 ( 注意：此处不是左孩子 ) 中， 30 左
子树增加
了一层，导致以 60 为根的二叉树不平衡，要让 60 平衡，只能将 60 左子树的高度减少一层，右子
树增加一层，
即将左子树往上提，这样 60 转下来，因为 60 比 30 大，只能将其放在 30 的右子树，而如果 30 有
右子树，右子树根的值一定大于 30 ，小于 60 ，只能将其放在 60 的左子树，旋转完成后，更新节点
的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30 节点的右孩子可能存在，也可能不存在
2. 60 可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树
//1旋转 2调整bf
void RotateR(Node* parent){Node* SubL = parent->_left; //最关键的两个节点Node* SubLR = SubL->_right;//连接parent->_left = SubLR;SubL->_right = parent;//处理剩余关系线parent->_parent = SubL;if (SubLR) //如果subLR为空，那么parent->right一定为空SubLR->_parent = parent;Node* parentParent = parent->_parent;if (_root == parent) //有可能parent是根节点，也有可能不是根节点{_root = SubL;subL->_parent = nullptr;}else //不是根节点{if (parent == parentParent->_left) //判断是左子树还是右子树{parentParent->_left = SubL;subL->_parent = parentParent;}else{parentParent->_right = SubL;subL->_parent = parentParent;}}subL->_bf = 0; parent->_bf = 0; //如果subLR为空，那么parent->right一定为空，最终的_bf一定都是空}
2. 新节点插入较高右子树的右侧---右右：左单旋
void RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;//连接parent->_right = SubRL;SubR->_left = parent;//处理剩余关系线parent->_parent = SubR;if (SubRL) //如果subRL为空，那么parent->left一定为空SubRL->_parent = parent;Node* parentParent = parent->_parent;if (_root == parent) //有可能parent是根节点，也有可能不是根节点{_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left) //判断是左子树还是右子树{parentParent->_left = SubR;subR->_parent = parentParent;}else{parentParent->_right = SubR;subR->_parent = parentParent;}}subR->_bf = 0;parent->_bf = 0; //如果subRL为空，那么parent->left一定为空，最终的_bf一定都是空}
3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋
将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再
考虑平衡因子的更新。
需要考虑的是，插入之后_bf的调整。
同时每次插入都需要考虑新插入的节点是不是空节点
void RotateLR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right; //可能为空int bf = SubLR->_bf; //可能为0(如果为0，说明SubLR为空）RotateL(SubL);RotateR(parent);if (bf == 0){//说明SubLR就是新增parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == 1){//说明SubLR是新增的右子树parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){//说明SubLR是新增的左子树parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}
4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋
void RotateRL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left; //可能为空int bf = SubRL->_bf; //可能为0(如果为0，说明SubRL为空）RotateR(SubR);RotateL(parent);if (bf == 0){//说明SubRL就是新增parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){//说明SubRL是新增的右子树parent->_bf = 0;subR->_bf = -1;subRL->_bf = 0;}else if (bf == -1){//说明SubRL是新增的左子树parent->_bf = 1;subR->_bf = 0;subRL->_bf = 0;}else{assert(false);}}
总结：
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时，执行左单旋
当pSubR的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是，执行右单旋
当pSubL的平衡因子为1时，执行左右双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。
AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1. 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确
采用了双重保险：1.检测右-左是否为_bf 2.检测abs(_bf)是否为<2
在高度求解时，采用了递归算法。求左子树高度（求子树高度不能 + 1） ，再求右子树高度。总高度 = max（左子树，右子树） + 1 （在algorithm算法库中）
int _Height(Node* root)
{if (root == nullptr)return 0;int leftHeight = _Height(root->_left); //求的是子树的高度，不包括自身，不能加1int rightHeight = _Height(root->_right);return max(leftHeight, rightHeight) + 1;
}bool _IsBalanced(Node* node) //进行遍历
{if (node == 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);
}