个人主页：仍有未知等待探索-CSDN博客
专题分栏：C++
目录
一、概念
二、平衡因子
三、操作
插入
旋转
左单旋
右单旋
左右双旋
右左双旋
一、概念
二叉平衡搜索树又称AVL树，是一种特殊的二叉搜索树。一般的二叉搜索树在遇到数据有序时，查找的效率比较的低。
而二叉平衡搜索树，为了防止有这种极端的情况出现，其保证了任一节点的左右子树的高度差不超过1，通过控制高度，使查找的次数降低。
二、平衡因子
二叉平衡搜索树，在对节点的结构进行定义的时候多添加了一个平衡因子的变量（bf），用来判断树是否是平衡的。
平衡因子 = 右子树的高度 - 左子树的高度
平衡因子的取值为 ：0、+1、-1、+2、-2
当平衡因子为+2、-2的时候，代表了这棵树需要进行调整。
三、操作
插入
插入的步骤就是这些。
为什么调节完，平衡因子为1、-1的时候要向上进行调整？
如果调节完，平衡因子为1、-1，则在没有调整的时候，平衡因子为0。新增了一个结点之后，高度发生了变化。以当前节点为根节点的子树的高度发生了变化，则以当前节点为其中的一个节点的子树的高度也同样发生了变化，所以需要进行调整。
旋转
对于要通过旋转进行调节平衡因子的情况不细分的话，有4种：左单旋、右单旋、左右双旋、右左双旋。
注意：在进行旋转的时候，对于每个节点的指针变化，要特别的细心。
节点中有三个指针，一个指向左孩子、一个指向右孩子、另外一个指向双亲。
旋转点：进行旋转的一个基准点。就比如左单旋的话，parent就是旋转点。
左单旋
左单旋变换：subrl 变成 parent 的右子树，parent 成为 subr 的左子树。
直接看图变换是不难，但是写代码就会有很多的坑（指针的变换）。
// 左单旋
// 参数是图中的parent，也称为旋转点
void RotateL(node* parent)
{node* subr = parent->right;node* subrl = subr->left;// subrl 成为 parent 的右子树 parent->right = subrl;if (subrl)subrl->parent = parent;subr->left = parent;node* pparent = parent->parent;parent->parent = subr;if (_root != parent){if (pparent->left == parent){pparent->left = subr;}else {pparent->right = subr;}subr->parent = pparent;}else{_root = subr;subr->parent = nullptr;}parent->bf = subr->bf = 0;
}右单旋
如图是右单旋的情况。
右单旋的变换：sublr 变成 parent 的左子树，将parent 变成 subl 的右子树。
直接看图变换是不难，但是写代码就会有很多的坑（指针的变换）。
// 右单旋
// parent 为旋转点
void RotateR(node* parent)
{node* subl = parent->left;node* sublr = subl->right;// sublr成为parent的左子树parent->left = sublr;// 如果sublr是空的话，不需要更新它的双亲结点，因为空指针不能进行解引用if (sublr)sublr->parent = parent;// parent成为subl的右子树subl->right = parent;// 记录一下这个子树的根节点的双亲结点node* pparent = parent->parent;// 更新parent的双亲节点parent->parent = subl;// 判断该子树的根节点是不是整个子树的根节点// 不是的话，也需要更新该子树的根节点的双亲结点if (_root != parent){if (pparent->left == parent){pparent->left = subl;}else {pparent->right = subl;}subl->parent = pparent;}else{_root = subl;subl->parent = nullptr;}// 更新平衡因子parent->bf = subl->bf = 0;
}
左右双旋
左右双旋的变换：先以 subl 为旋转点进行左单旋，然后再以 parent 为旋转点进行右单旋。
注意：1、指针的变换 2、注意新的节点插入在 b 子树的左子树和右子树的时候，平衡因子的变化。
// 左右双旋
// 传参传的节点还是parent
void RotateLR(node* parent)
{node* psubl = parent->left;node* psublr = psubl->right;// 记录之前的 sublr 节点的平衡因子int bf = psublr->bf;// 先以 subl 为旋转点进行左单旋RotateL(parent->left);// 然后再以 parent 为旋转点进行右单旋RotateR(parent);// 在完成旋转调整平衡后，在对该子树的平衡因子进行变换// 至于为什么平衡因子等于这些值，可以去看看我画的图然后进行对比// 还是比较清楚的if (-1 == bf){psubl->bf = psublr->bf = 0;parent->bf = 1;}else if (1 == bf){parent->bf = psublr->bf = 0;psubl->bf = -1; }else if (0 == bf) // 如果在旋转之前的平衡因子就是为0，则调整完之后的平衡因子都是0{parent->bf = psubl->bf = psublr->bf = 0;}else // 这种情况一般是没有的，如果有，则是你写的AVL树是有错误的{assert(false);}
}
右左双旋
右左双旋的变换：先以 subr 为旋转点进行右单旋，然后再以 parent 为旋转点进行左单旋。
注意：1、指针的变换 2、注意新的节点插入在 c 子树的左子树和右子树的时候，平衡因子的变化。
// 右左双旋
void RotateRL(node* parent)
{node* psubr = parent->right;node* psubrl = parent->left;int bf = psubrl->bf;// 先以subr为旋转点进行右单旋RotateR(parent->right);// 再以parent为旋转点进行左单旋RotateL(parent);// 更新平衡因子if (1 == bf){psubr->bf = psubrl->bf = 0;parent->bf = -1;}else if (-1 == bf){parent->bf = psubrl->bf = 0;psubr->bf = 1;}else if (0 == bf){parent->bf = psubr->bf = psubrl->bf = 0;}else {assert(false);}
}
