相信很多初学者会跟我一样觉得这里的旋转操作十分抽象，其实十分简单，我们只需要搞清楚插入或删除是个什么情况，再进行对应的旋转即可
平衡二叉树定义
平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。 [1]
设“2-3 树”的每个结点存放一组与应用问题有关的数据, 且有一个关键字 (>0的整数) 作为标识。关键字的存放规则如下:对于结点X, 设左、中、右子树均不空, 则左子树任一结点的关键字小于中子树中任一结点的关键字;中子树中任一结点的关键字小于结点X的关键字;而X的关键字又小于右子树中任一结点的关键字, 称这样的“2-3树”为平衡树
平衡二叉树的插入
插入是考试题目中出现频率较高的，如果插入导致了不平衡就要调整各节点之间的关系以重新达到平衡，具体可以分为以下几种
1：LL平衡旋转（右单旋转）
发生这种不平衡的原因是在结点A的左孩子的左子树上插入了新结点，导致A的平衡因子由1变成2失去平衡，这个时候需要一次向右的旋转操作，将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树，文字描述还是十分抽象，下面用题目具体讲解
2：RR平衡旋转（左单旋转）
由于在结点A的右孩子的右子树上插入了新结点，A的平衡因为由-1减到-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作，将A的右孩子B向左上旋转代替A成为根结点，A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树
3：LR平衡旋转（先左后右双旋转）
由于在A的左孩子的右子树上插入新结点，此时需要进行两次旋转，先将A结点的左孩子B的右子树的根结点C向左上旋转提升B结点的位置，然后把该C结点向右上旋转提升到A结点的位置，只要理解了上述两种旋转这种组合旋转也是十分简单
4：RL平衡旋转
由于在A的左孩子的右子树上插入新结点，需要进行两次旋转操作，先右旋转后左旋转，先将A结点的右孩子B的左子树根结点C向右上旋转提升到B结点的位置，然后将C结点向左上旋转提升到A结点的位置
平衡二叉树的删除
它与插入操作类似，如果删除导致了不平衡，则向上回溯找到第一个不平衡的结点，然后根据上面不平衡的性质进行旋转，与插入的不同之处在于，删除的时候可能需要调整多棵子树进行多次旋转，难说有什么通解，只要把上面插入的四种旋转操作弄清楚这一块还是十分简单的
创作不易 觉得有帮助请点赞关注收藏~~~
