数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解（题目讲解简单易懂）

深藏阁楼爱情的钟 2023-10-09 20:11 39阅读 0赞

相信很多初学者会跟我一样觉得这里的旋转操作十分抽象，其实十分简单，我们只需要搞清楚插入或删除是个什么情况，再进行对应的旋转即可

## 平衡二叉树定义 ##

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，[B树][B]（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作, [时间复杂度][Link 1]和[空间复杂度][Link 2]相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的[途径][Link 3]。 \[1\]

设“2-3 树”的每个[结点][Link 4]存放一组与应用问题有关的数据, 且有一个关键字 (>0的整数) 作为标识。关键字的存放规则如下:对于结点X, 设左、中、右子树均不空, 则左子树任一结点的关键字小于中子树中任一结点的关键字;中子树中任一结点的关键字小于结点X的关键字;而X的关键字又小于右子树中任一结点的关键字, 称这样的“2-3树”为平衡树

## 平衡二叉树的插入 ##

插入是考试题目中出现频率较高的，如果插入导致了不平衡就要调整各节点之间的关系以重新达到平衡，具体可以分为以下几种

### 1：LL平衡旋转（右单旋转） ###

发生这种不平衡的原因是在**结点A的左孩子的左子树上插入了新结点**，导致A的平衡因子由1变成2失去平衡，这个时候需要一次向右的旋转操作，**将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树，文字描述还是十分抽象，下面用题目具体讲解**

![ea0eb8a3b2d7406c831cc0216832eced.jpeg][]

### 2：RR平衡旋转（左单旋转） ###

由于在结点A的右孩子的右子树上插入了新结点，A的平衡因为由-1减到-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作，**将A的右孩子B向左上旋转代替A成为根结点，A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树**

![154bdbac6d0248e58b4521fb3d30c0f6.png][]

### 3：LR平衡旋转（先左后右双旋转） ###

由于在A的左孩子的右子树上插入新结点，此时需要进行两次旋转，先将A结点的左孩子B的右子树的根结点C向左上旋转提升B结点的位置，然后把该C结点向右上旋转提升到A结点的位置，只要理解了上述两种旋转这种组合旋转也是十分简单

![bcf4405eeb8c47dd9cd599c8c6e55e38.png][]

### 4：RL平衡旋转 ###

由于在A的左孩子的右子树上插入新结点，需要进行两次旋转操作，先右旋转后左旋转，**先将A结点的右孩子B的左子树根结点C向右上旋转提升到B结点的位置，然后将C结点向左上旋转提升到A结点的位置**

![e5358b12673d49ae9cf4f6e8f26997ff.jpeg][]

## 平衡二叉树的删除 ##

它与插入操作类似，如果删除导致了不平衡，则向上回溯找到第一个不平衡的结点，然后根据上面不平衡的性质进行旋转，**与插入的不同之处在于，删除的时候可能需要调整多棵子树进行多次旋转**，难说有什么通解，只要把上面插入的四种旋转操作弄清楚这一块还是十分简单的

**创作不易 觉得有帮助请点赞关注收藏~~~**

[B]: https://baike.baidu.com/item/B%E6%A0%91/5411672
[Link 1]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057
[Link 2]: https://baike.baidu.com/item/%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/9664257
[Link 3]: https://baike.baidu.com/item/%E9%80%94%E5%BE%84/9150896
[Link 4]: https://baike.baidu.com/item/%E7%BB%93%E7%82%B9/9794643
[ea0eb8a3b2d7406c831cc0216832eced.jpeg]: https://img-blog.csdnimg.cn/ea0eb8a3b2d7406c831cc0216832eced.jpeg
[154bdbac6d0248e58b4521fb3d30c0f6.png]: https://img-blog.csdnimg.cn/154bdbac6d0248e58b4521fb3d30c0f6.png
[bcf4405eeb8c47dd9cd599c8c6e55e38.png]: https://img-blog.csdnimg.cn/bcf4405eeb8c47dd9cd599c8c6e55e38.png
[e5358b12673d49ae9cf4f6e8f26997ff.jpeg]: https://img-blog.csdnimg.cn/e5358b12673d49ae9cf4f6e8f26997ff.jpeg