<commit_before>---
layout: post
title: 什么是平衡二叉树
categories: [DataStructure]
description: 
keywords: 
---

* content
{:toc}


## 什么是平衡二叉树

<img src="http://www.milky.show/images/datastructure/avl/avl_1.png" alt="http://www.milky.show/images/datastructure/avl/avl_1.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_2.png" alt="http://www.milky.show/images/datastructure/avl/avl_2.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_3.png" alt="http://www.milky.show/images/datastructure/avl/avl_3.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_4.png" alt="http://www.milky.show/images/datastructure/avl/avl_4.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_5.png" alt="http://www.milky.show/images/datastructure/avl/avl_5.png" style="zoom:67%;" />

在红黑树当中，我们通过红色结点和黑色结点作为辅助，来判断一颗二叉树是否相对平衡。

<img src="http://www.milky.show/images/datastructure/avl/avl_6.png" alt="http://www.milky.show/images/datastructure/avl/avl_6.png" style="zoom:67%;" />

而在AVL树当中，我们通过“平衡因子”来判断一颗二叉树是否符合高度平衡。

到底什么是AVL树的平衡因子呢？

对于AVL树的每一个结点，平衡因子是它的**左子树高度和右子树高度的差值**。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候，这颗二叉树才是一颗合格的AVL树。

举个例子，下图就是一颗典型的AVL树，每个节点旁边都标注了平衡因子：

<img src="http://www.milky.show/images/datastructure/avl/avl_7.png" alt="http://www.milky.show/images/datastructure/avl/avl_7.png" style="zoom:67%;" />

其中结点4的左子树高度是1，右子树不存在，所以该结点的平衡因子是1-0=1。



结点7的左子树不存在，右子树高度是1，所以平衡因子是0-1=-1。



所有的叶子结点，不存在左右子树，所以平衡因子都是0。

<img src="http://www.milky.show/images/datastructure/avl/avl_8.png" alt="http://www.milky.show/images/datastructure/avl/avl_8.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_9.png" alt="http://www.milky.show/images/datastructure/avl/avl_9.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_10.png" alt="http://www.milky.show/images/datastructure/avl/avl_10.png" style="zoom:67%;" />

上图原本是一个平衡的AVL树，当插入了新结点1时，父结点2的平衡因子变成了1，祖父结点4的平衡因子变成了2。



此时，结点4的左右子树高度差超过了1，打破了AVL树的平衡。





那么，怎样才能重新恢复AVL的平衡呢？



之前讲解红黑树的时候，我们提到红黑树包括左旋转、右旋转、变色这三种操作。



而AVL树不存在变色的问题，只有**左旋转**、**右旋转**这两种操作。



**左旋转：**



**逆时针**旋转AVL树的两个结点X和Y，使得父结点被自己的右孩子取代，而自己成为自己的左孩子。说起来有些绕，见下图（标号1,2,3的三角形，是结点X和Y的子树）：

<img src="http://www.milky.show/images/datastructure/avl/avl_11.png" alt="http://www.milky.show/images/datastructure/avl/avl_11.png" style="zoom:67%;" />

图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。





**右旋转：**



**顺时针**旋转AVL树的两个结点X和Y，使得父结点被自己的左孩子取代，而自己成为自己的右孩子。见下图：

<img src="http://www.milky.show/images/datastructure/avl/avl_12.png" alt="http://www.milky.show/images/datastructure/avl/avl_12.png" style="zoom:67%;" />

图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。

<img src="http://www.milky.show/images/datastructure/avl/avl_13.png" alt="http://www.milky.show/images/datastructure/avl/avl_13.png" style="zoom:67%;" />

AVL 树的调整分成四种局面

1.  **左左局面（LL）**

    <img src="http://www.milky.show/images/datastructure/avl/avl_14.png" alt="http://www.milky.show/images/datastructure/avl/avl_14.png" style="zoom:67%;" />

    顾名思义，祖父结点A有一个左孩子结点B，而结点B又有一个左孩子结点C。标号1,2,3,4的三角形是各个结点的子树。

    

    在这种局面下，我们以结点A为轴，进行**右旋**操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_15.png" alt="http://www.milky.show/images/datastructure/avl/avl_15.png" style="zoom:67%;" />

2.  **右右局面（RR）**

    <img src="http://www.milky.show/images/datastructure/avl/avl_16.png" alt="http://www.milky.show/images/datastructure/avl/avl_16.png" style="zoom:67%;" />

    祖父结点A有一个右孩子结点B，而结点B又有一个右孩子结点C。

    

    在这种局面下，我们以结点A为轴，进行**左旋**操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_17.png" alt="http://www.milky.show/images/datastructure/avl/avl_17.png" style="zoom:67%;" />

3.  **左右局面（LR）**

    <img src="http://www.milky.show/images/datastructure/avl/avl_18.png" alt="http://www.milky.show/images/datastructure/avl/avl_18.png" style="zoom:67%;" />

    
    祖父结点A有一个左孩子结点B，而结点B又有一个右孩子结点C。

    

    在这种局面下，我们先以结点B为轴，进行**左旋**操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_19.png" alt="http://www.milky.show/images/datastructure/avl/avl_19.png" style="zoom:67%;" />

    这样就转化成了左左局面。我们继续以结点A为轴，进行右旋操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_20.png" alt="http://www.milky.show/images/datastructure/avl/avl_20.png" style="zoom:67%;" />

4.  **右左局面（RL）**

    <img src="http://www.milky.show/images/datastructure/avl/avl_21.png" alt="http://www.milky.show/images/datastructure/avl/avl_21.png" style="zoom:67%;" />

    祖父结点A有一个右孩子结点B，而结点B又有一个左孩子结点C。

    

    在这种局面下，我们先以结点B为轴，进行**右旋**操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_22.png" alt="http://www.milky.show/images/datastructure/avl/avl_22.png" style="zoom:67%;" />

    这样就转化成了右右局面。我们继续以结点A为轴，进行左旋操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_23.png" alt="http://www.milky.show/images/datastructure/avl/avl_23.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_24.png" alt="http://www.milky.show/images/datastructure/avl/avl_24.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_25.png" alt="http://www.milky.show/images/datastructure/avl/avl_25.png" style="zoom:67%;" />

例子中，以结点4为根的子树出现了不平衡的情况。



不难看出，这个子树正好符合 “左左局面”。



于是，我们以结点4为轴，进行右旋操作：

<img src="http://www.milky.show/images/datastructure/avl/avl_26.png" alt="http://www.milky.show/images/datastructure/avl/avl_26.png" style="zoom:67%;" />

这样一来，这颗AVL树重新恢复了高度平衡。

<img src="http://www.milky.show/images/datastructure/avl/avl_27.png" alt="http://www.milky.show/images/datastructure/avl/avl_27.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_28.png" alt="http://www.milky.show/images/datastructure/avl/avl_28.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_29.png" alt="http://www.milky.show/images/datastructure/avl/avl_29.png" style="zoom:67%;" />

如上图所示，在AVL树中删除了结点1，导致父节点2的平衡因子变为-2，打破了平衡。



此时，以结点2为根的子树正好形成了“右左局面”，于是我们首先以结点4为轴进行右旋：

<img src="http://www.milky.show/images/datastructure/avl/avl_30.png" alt="http://www.milky.show/images/datastructure/avl/avl_30.png" style="zoom:67%;" />

然后以结点2为轴进行左旋：

<img src="http://www.milky.show/images/datastructure/avl/avl_31.png" alt="http://www.milky.show/images/datastructure/avl/avl_31.png" style="zoom:67%;" />

如此一来，AVL树重新恢复了高度平衡。<commit_msg>update blog<commit_after>---
layout: post
title: 什么是平衡二叉树
categories: [DataStructure]
description: 
keywords: 
---

* content
{:toc}


## 什么是平衡二叉树

<img src="http://www.milky.show/images/datastructure/avl/avl_1.png" alt="http://www.milky.show/images/datastructure/avl/avl_1.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_2.png" alt="http://www.milky.show/images/datastructure/avl/avl_2.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_3.png" alt="http://www.milky.show/images/datastructure/avl/avl_3.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_4.png" alt="http://www.milky.show/images/datastructure/avl/avl_4.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_5.png" alt="http://www.milky.show/images/datastructure/avl/avl_5.png" style="zoom:67%;" />

在红黑树当中, 我们通过红色结点和黑色结点作为辅助, 来判断一颗二叉树是否相对平衡. 

<img src="http://www.milky.show/images/datastructure/avl/avl_6.png" alt="http://www.milky.show/images/datastructure/avl/avl_6.png" style="zoom:67%;" />

而在AVL树当中, 我们通过“平衡因子”来判断一颗二叉树是否符合高度平衡. 

到底什么是AVL树的平衡因子呢？

对于AVL树的每一个结点, 平衡因子是它的**左子树高度和右子树高度的差值**. 只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候, 这颗二叉树才是一颗合格的AVL树. 

举个例子, 下图就是一颗典型的AVL树, 每个节点旁边都标注了平衡因子：

<img src="http://www.milky.show/images/datastructure/avl/avl_7.png" alt="http://www.milky.show/images/datastructure/avl/avl_7.png" style="zoom:67%;" />

其中结点4的左子树高度是1, 右子树不存在, 所以该结点的平衡因子是1-0=1. 

结点7的左子树不存在, 右子树高度是1, 所以平衡因子是0-1=-1. 

所有的叶子结点, 不存在左右子树, 所以平衡因子都是0. 

<img src="http://www.milky.show/images/datastructure/avl/avl_8.png" alt="http://www.milky.show/images/datastructure/avl/avl_8.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_9.png" alt="http://www.milky.show/images/datastructure/avl/avl_9.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_10.png" alt="http://www.milky.show/images/datastructure/avl/avl_10.png" style="zoom:67%;" />

上图原本是一个平衡的AVL树, 当插入了新结点1时, 父结点2的平衡因子变成了1, 祖父结点4的平衡因子变成了2. 

此时, 结点4的左右子树高度差超过了1, 打破了AVL树的平衡. 

那么, 怎样才能重新恢复AVL的平衡呢？

之前讲解红黑树的时候, 我们提到红黑树包括左旋转、右旋转、变色这三种操作. 

而AVL树不存在变色的问题, 只有**左旋转**、**右旋转**这两种操作. 

**左旋转：**

**逆时针**旋转AVL树的两个结点X和Y, 使得父结点被自己的右孩子取代, 而自己成为自己的左孩子. 说起来有些绕, 见下图（标号1,2,3的三角形, 是结点X和Y的子树）：

<img src="http://www.milky.show/images/datastructure/avl/avl_11.png" alt="http://www.milky.show/images/datastructure/avl/avl_11.png" style="zoom:67%;" />

图中, 身为右孩子的Y取代了X的位置, 而X变成了自己的左孩子. 此为左旋转. 

**右旋转：**

**顺时针**旋转AVL树的两个结点X和Y, 使得父结点被自己的左孩子取代, 而自己成为自己的右孩子. 见下图：

<img src="http://www.milky.show/images/datastructure/avl/avl_12.png" alt="http://www.milky.show/images/datastructure/avl/avl_12.png" style="zoom:67%;" />

图中, 身为左孩子的Y取代了X的位置, 而X变成了自己的右孩子. 此为右旋转. 

<img src="http://www.milky.show/images/datastructure/avl/avl_13.png" alt="http://www.milky.show/images/datastructure/avl/avl_13.png" style="zoom:67%;" />

AVL 树的调整分成四种局面

1.  **左左局面（LL）**

    <img src="http://www.milky.show/images/datastructure/avl/avl_14.png" alt="http://www.milky.show/images/datastructure/avl/avl_14.png" style="zoom:67%;" />

    顾名思义, 祖父结点A有一个左孩子结点B, 而结点B又有一个左孩子结点C. 标号1,2,3,4的三角形是各个结点的子树. 

    

    在这种局面下, 我们以结点A为轴, 进行**右旋**操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_15.png" alt="http://www.milky.show/images/datastructure/avl/avl_15.png" style="zoom:67%;" />

2.  **右右局面（RR）**

    <img src="http://www.milky.show/images/datastructure/avl/avl_16.png" alt="http://www.milky.show/images/datastructure/avl/avl_16.png" style="zoom:67%;" />

    祖父结点A有一个右孩子结点B, 而结点B又有一个右孩子结点C. 

    在这种局面下, 我们以结点A为轴, 进行**左旋**操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_17.png" alt="http://www.milky.show/images/datastructure/avl/avl_17.png" style="zoom:67%;" />

3.  **左右局面（LR）**

    <img src="http://www.milky.show/images/datastructure/avl/avl_18.png" alt="http://www.milky.show/images/datastructure/avl/avl_18.png" style="zoom:67%;" />
    祖父结点A有一个左孩子结点B, 而结点B又有一个右孩子结点C. 

    在这种局面下, 我们先以结点B为轴, 进行**左旋**操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_19.png" alt="http://www.milky.show/images/datastructure/avl/avl_19.png" style="zoom:67%;" />

    这样就转化成了左左局面. 我们继续以结点A为轴, 进行右旋操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_20.png" alt="http://www.milky.show/images/datastructure/avl/avl_20.png" style="zoom:67%;" />

4.  **右左局面（RL）**

    <img src="http://www.milky.show/images/datastructure/avl/avl_21.png" alt="http://www.milky.show/images/datastructure/avl/avl_21.png" style="zoom:67%;" />

    祖父结点A有一个右孩子结点B, 而结点B又有一个左孩子结点C. 

    

    在这种局面下, 我们先以结点B为轴, 进行**右旋**操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_22.png" alt="http://www.milky.show/images/datastructure/avl/avl_22.png" style="zoom:67%;" />

    这样就转化成了右右局面. 我们继续以结点A为轴, 进行左旋操作：

    <img src="http://www.milky.show/images/datastructure/avl/avl_23.png" alt="http://www.milky.show/images/datastructure/avl/avl_23.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_24.png" alt="http://www.milky.show/images/datastructure/avl/avl_24.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_25.png" alt="http://www.milky.show/images/datastructure/avl/avl_25.png" style="zoom:67%;" />

例子中, 以结点4为根的子树出现了不平衡的情况. 

不难看出, 这个子树正好符合 “左左局面”. 

于是, 我们以结点4为轴, 进行右旋操作：

<img src="http://www.milky.show/images/datastructure/avl/avl_26.png" alt="http://www.milky.show/images/datastructure/avl/avl_26.png" style="zoom:67%;" />

这样一来, 这颗AVL树重新恢复了高度平衡. 

<img src="http://www.milky.show/images/datastructure/avl/avl_27.png" alt="http://www.milky.show/images/datastructure/avl/avl_27.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_28.png" alt="http://www.milky.show/images/datastructure/avl/avl_28.png" style="zoom:67%;" />

<img src="http://www.milky.show/images/datastructure/avl/avl_29.png" alt="http://www.milky.show/images/datastructure/avl/avl_29.png" style="zoom:67%;" />

如上图所示, 在AVL树中删除了结点1, 导致父节点2的平衡因子变为-2, 打破了平衡. ?

此时, 以结点2为根的子树正好形成了“右左局面”, 于是我们首先以结点4为轴进行右旋：

<img src="http://www.milky.show/images/datastructure/avl/avl_30.png" alt="http://www.milky.show/images/datastructure/avl/avl_30.png" style="zoom:67%;" />

然后以结点2为轴进行左旋：

<img src="http://www.milky.show/images/datastructure/avl/avl_31.png" alt="http://www.milky.show/images/datastructure/avl/avl_31.png" style="zoom:67%;" />

如此一来, AVL树重新恢复了高度平衡. 
{'fraction_non_alphanumeric': 0.2015737097894006, 'fraction_numerical': 0.032091336881894625, 'mean_word_length': 5.010199350950394, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 65, 'https://': 0, 'lorem ipsum': 0, 'www.': 124, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4323313', 'n_tokens_mistral': 7237, 'n_tokens_neox': 7568, 'n_words': 437}