树（二）平衡二叉树

迷南。 2023-06-22 04:22 14阅读 0赞

### [树（一）二叉查找树][Link 1] ###

### [树（三）红黑树与平衡二叉树的区别][Link 2] ###

## 1 为什么有平衡二叉树 ##

二叉查找树（二叉搜索树）的构造是为了加快查询的效率，其查找的思想类似于折半查找法。而搜索树节点不同的插入次序会导致不同的查找效率。也就是拥有相同的数据内容，由于树的插入次序的不同导致了不同的树的深度与平均查找长度。

比如有8个数据分别是1,2,3,4,5,6,7,8，如果按照由小到的的顺序依次插入，构造的树是这样的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70][]

**这棵树有8个节点，根节点的高度为7，平均查找长度为(1+2+3+4+5+6+7+8)/8 = 4.5。**

**       ** 实际上，以这种插入方式构造的树与链表的结构也没什么差别了，很显然这并不是我们想要的结果，于是就有了平衡二叉树。

## 2 什么是平衡二叉树 ##

平衡二叉树（Balanced Binary Tree）的定义是这样的——空树，或者**任一节点左、右子树高度差的绝对值不超过1**，称为平衡二叉树。

比如，我们将1,2,3,4,5,6,7,8这几个节点以5,3,1,4,2,7,6,8的顺序插入构造查找二叉树，**这棵树就是一个平衡二叉树**，它的根节点高度为3，平均查找长度为(1\*1+ 2\*2 + 4\*3 + 1\*4)/8 = 2.625,，并且它的**任一节点左、右子树高度差的绝对值不超过1。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 1][]

而如果按照6,4,3,5,2,1,7,8的顺序插入构造查找二叉树，**这棵树也不能称为平衡二叉树**，因为它的根节点的左子树高度为4，而右子树的高度为2，相差大于1；而对于4这一个节点，它的左子树高度为3，右子树的高度为1，相差也大于1。而这棵树的平均查找长度为（1\*1 + 2\*2 + 3\*3 + 4\*1 + 5\*1）/ 8 = 2.875（这里数据量较小，看不出与平衡二叉树的明显差别）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 2][]

## 3 平衡二叉树的旋转 ##

一棵树为平衡二叉树，此时插入一个节点可能会导致这棵树的不平衡，比如下面这棵树，原为一棵平衡二叉树，在插入9这个节点后，根节点的左子树深度为1，右子树深度为3，两边深度差别的绝对值大于1，所以在插入9这个节点后，不再是一棵平衡二叉树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 3][]

### 3.1 右单旋 ###

上面这张图所示的内容中，受到影响的是5这一个根节点，我们称这一个节点为“发现者”，而9这一个节点称为“麻烦节点”，“麻烦节点”在“发现者”的右边，因此叫做RR插入；而要保持这棵树继续为一棵平衡二叉树，需要做RR旋转，也就是右单旋，它是一个顺时针的旋转，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 5][]

### 3.2 左单旋 ###

左单旋（LL旋转）与右单旋是类似的，“麻烦节点”在“发现者”的左边，因此需要左单旋，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 6][]

### 3.3 LR旋转 ###

如果“麻烦节点”的插入是在“发现者”的左子树的右子树，需要进行LR旋转，这一个旋转需要调整的关注点是在“发现者”与“发现者”的左子树，以及这一个左子树的右子树节点,如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 7][]

### 3.4 RL旋转 ###

与LR旋转类似，如果“麻烦节点”的插入是在“发现者”的右子树的左子树，则需要进行RL旋转，这一旋转需要调整的关注点是在“发现者”与“发现者”的右子树，以及这一个右子树的左子树，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 8][]

### 3.5 在一棵树中寻找“发现者” ###

值得注意的是，在调整二叉树时，被破坏平衡的节点与破坏平衡的节点很可能与根节点无关，我们只需要**找出“不平衡”的这部分的节点**，以旋转的方式加以调整即可保证整个二叉树的平衡。

[Link 1]: https://blog.csdn.net/y506798278/article/details/103525788
[Link 2]: https://blog.csdn.net/y506798278/article/details/104275033
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200206180545660.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200206183729631.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200206191520467.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200207153534711.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200207155000373.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200207155325514.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200207161514389.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200207165329872.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200207171443705.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70