Savage

G

0%

二叉树PLUS（搜索树、平衡树）

发表于 分类于
总结一下二叉树的升级版，搜索树和平衡树。

二叉树PLUS（搜索树、平衡树）

搜索树

二叉搜索树（Binary Search Tree，BST）是一种常见的二叉树数据结构，它在二叉树的基础上多了一下几个特点：

条件一：对于任意节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。

条件二：如果满足条件一，那么对搜索树进行中序遍历，就会得到一个有序的序列。

1
2
3
4
5
6
7
8
搜索树  
    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

中序遍历：1 3 4 6 7 8 10 13 14

可以看到这颗二叉树任意节点都大于的左子树上的节点，小于右子树上的节点

构建搜索树

在构建搜索树时，按照条件一对元素进行插入就可以，但是在极端情况下搜索树会变成链表，这种情况就是使用有序序列构建搜索树时

1
2
3
4
5
6
7
8
9
//序列 1 3 4 6 7 8 10 13 14
1
 \
  3
   \
    4
     \
      6
      ......

可以看到这棵树变成了链表，为了避免这种情况，后面诞生了平衡搜索树

基础操作

搜索树实际上维护了一个有序的序列，我们对照有序数组看看两者的插入和删除操作有什么不同。

有序数组

对数组中的元素进行插入和删除操作，第一步就是先找到这个元素，使用二分查找可以很快找到需要插入的元素位置O(log n)，然后插入时需要把后面的对象依次向后移动，这里时间复杂度为O(n)级别的，删除操作需要把该元素后面的对象依次向前移动，时间复杂度还是O(n)。

1
2
3
4
5
6
1 3 4 6 7 8 10 13 14
插入：9
1 3 4 6 7 8 [9] *10 13 14*
删除：9
1 3 4 6 7 8 [ ] *10 13 14*
//红色是需要移动的元素

搜索树

在比较平衡的搜索树中找到这个元素的效率和有序数组一样O(log n)，但是在删除时不需要移动那么多元素，插入时更是不需要移动元素。所以搜索树是一种插入删除高效的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    8       
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13
  
     8
   /   \
  3     10
 / \   /  \            //插入9
1   6 [9] 14
   / \   /
  4   7 13
 
     8       
   /   \
  3    [14]
 / \    / 
1   6  13           //删除10
   / \   
  4   7

删除

上面的插入操作很好理解，现在看一下删除，删除一个节点后要如何处理该节点的子节点呢？

删除规则：用删除节点的左子树最大节点替换该节点，或者使用删除节点的右子树最小节点替换该节点

为什么要这样做呢？我们看一下下面这个序列：

1
1 3 4 6 [7] 8 [10] 13 14

现在要删除根节点8，按照上面的规则其实就会选出最接近删除节点的元素替换它。左子树就会选出7，右子树会选出10，按照这样的规则删除的好处是避免移动过多的节点。

AVL树

AVL树也叫平衡二叉树，是由两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明的，为了纪念他们，将平衡二叉树称为 AVL树。

AVL树满足的条件：

条件一：是一颗二叉搜索树。

条件二：每个节点的左子树和右子树的高度最多相差1，即任何节点的平衡因子（左子树高度减去右子树高度的绝对值）不超过1。

条件三：每个节点的左子树和右子树都是AVL树。

平衡因子（Balance Factor）：节点的平衡因子其实就是左子树高度与右子树高度的差的绝对值

$$
BF = 左子树高度 - 右子树高度
$$

1
2
3
4
5
6
7
8
9
10
11
12
  1
 / \
0   3
   / \
  2   4            //节点1的左子树高度 = 1
       \           //节点1的右子树高度 = 3
        6          // BF = -2    
  1
 / \
0   3              //节点1的左子树高度 = 1
   / \             //节点1的右子树高度 = 2
  2   4            // BF = -1

基本操作

AVL树也是一颗二叉搜索树，所以查找、插入、删除操作和二叉树基本一样，唯一需要注意的是再删除和插入后需要保证AVL树的平衡，就是保证节点的平衡因子为小于等于1

左旋

让该节点成为它右子节点的左子节点

冲突情况：如果左旋的节点与右子节点的左子节点发生冲突，就让原来位置的节点成为左旋节点的右子节点。

对于这颗不平衡的二叉搜索树（节点1的平衡因子是-2），可以通过左旋来实现平衡

1
2
3
4
5
6
7
 [1]              
   \         
    3                3
     \              / \
      4           [1]  4

节点1通过左旋，成为了它右子节点3的左子节点

现在来看一下复杂的情况，对于下面这颗树，如果还是左旋，节点1和节点2就会发生冲突

1
2
3
4
5
6
7
 [1]                   3     
   \                  / \
    3               [1]  4
   / \                \
  2   4                2

节点1左旋时与2发生了冲突，就让原来位置的节点2，成为左旋后节点1的右子节点

对于左旋操作，冲突的节点变成旋转节点的右孩子

右旋

让该节点成为它左子节点的右子节点

冲突情况：如果左旋的节点与左子节点的右子节点发生冲突，就让原来位置的节点成为右旋节点的左子节点。

对于这颗不平衡的二叉搜索树（节点4的平衡因子是2），可以通过右旋来实现平衡

1
2
3
4
5
6
7
    [4]              
    /          
   2                2
  /                / \
 1                1  [4]

节点1通过左旋，成为了它右子节点3的左子节点

现在来看一下复杂的情况，对于下面这颗树，如果还是左旋，节点1和节点2就会发生冲突

1
2
3
4
5
6
7
    [4]            2 
    /             / \
   2             1  [4] 
  / \               / 
 1   3             3  
 
节点1左旋时与2发生了冲突，就让原来位置的节点2，成为左旋后节点1的右子节点

对于右旋操作，冲突的节点变成旋转节点的左孩子

插入节点破坏平衡后的四种旋转情况

LL（失衡节点的左子树，发生左失衡）

失衡节点：平衡因子 = 2

失衡节点左子节点：平衡因子 = 1

恢复平衡方法：失衡节点右旋

1
2
3
4
5
6
7
8
9
      [14]          
      /  \          
     6   17           6
    / \              / \
   5   9            5  [14]
  /                /   /  \
[3]               3   9    17
  
   右旋前           右旋后

我们来看一下上面这颗树，节点3的加入，导致搜索树不平衡，这时候14节点的平衡因子 = 2 ，6节点的平衡因子 = 1 ，这种情况只需要对14节点右旋就可以恢复平衡。

RR（失衡节点的右子树，发生右失衡）

失衡节点：平衡因子 = -2

失衡节点右子节点：平衡因子 = -1

恢复平衡方法：失衡节点左旋

1
2
3
4
5
6
7
8
9
   [5]          
  /  \          
 3    9              9
     / \            / \
    6  14         [5]  14
         \        / \    \
        [17]     3   6  [17]
   
左旋前             左旋后

我们来看一下上面这颗树，节点17的加入，导致搜索树不平衡，这时候节点5的平衡因子 = -2 ，9节点的平衡因子 = -1 ，这种情况只需要对节点5左旋就可以恢复平衡。

LR（失衡节点的左子树，发生右失衡）

失衡节点：平衡因子 = 2

失衡节点左子节点：平衡因子 = -1

恢复平衡方法：失衡节点左子节点左旋，失衡节点右旋

1
2
3
4
5
6
7
8
9
    [9]              [9]             8
   /  \             /   \           / \
  5    14          8     14        5  [9]    
 / \              /               / \   \
3   8            5               3  [6]  14
   /            / \
  [6]          3  [6]
   
增加节点6       节点5左旋后    节点9右旋后

我们来看一下上面这颗树，节点6的加入，导致搜索树不平衡，这时候节点9的平衡因子 = 2 ，5节点的平衡因子 = -1 ，这种情况先对节点5左旋，然后对节点9右旋，就可以恢复平衡。

RL（失衡节点的右子树，发生左失衡）

失衡节点：平衡因子 = -2

失衡节点右子节点：平衡因子 = 1

恢复平衡方法：失衡节点右子节点左旋，失衡节点左旋

1
2
3
4
5
6
7
8
9
   [5]               [5]                6
  /  \              /  \               / \
 3    9            3    6            [5]  9
     / \                 \           /   / \
    6  14                 9         3  [8]  14
     \                   / \
     [8]               [8]  14
   
增加节点8           节点9右旋后    节点5左旋后

我们来看一下上面这颗树，节点8的加入，导致搜索树不平衡，这时候节点5的平衡因子 = -2 ，9节点的平衡因子 = 1 ，这种情况先对节点9右旋，然后对节点5左旋，就可以恢复平衡。

插入时多个节点失衡

插入节点时如果多个节点都失衡，则调整距离插入节点最近的失衡节点，注意这里只需要调整一次

1
2
3
4
5
6
7
8
9
  [1]              
 /  \         
0   [3]                [1]
      \               /  \
       4             0    4
        \                / \
        [5]            [3] [5]
   
节点1，节点3失衡     节点3左旋后

失衡节点：1节点平衡因子 = -2 ，3节点平衡因子 = -2

恢复平衡方法：调整距离插入节点5最近的节点3，对节点3进行左旋

删除节点失衡，调整好导致多次失衡

删除节点和插入有一点不同，删除节点，需要依次对祖先节点进行检查，如果失衡就需要调整，这时候我们就需要调整多次节点。

1
2
3
4
5
6
7
8
9
        11              
    /        \         
   7          17             
  / \       /   \              
[5]  8     14   19          
      \    /   /  \            
       9  12  18  27
                  /
                 23

在这棵AVL中删除节点5，此时节点7的平衡因子= -2 ，我们可以通过左旋节点7来平衡树 

1
2
3
4
5
6
7
8
9
       11              
   /        \         
  8          17             
 / \       /   \              
7   9     14   19          
         /   /  \            
        12  18  27
                 /
                23

此时会发现节点11的平衡因子= -2 ，我们需要继续对节点11进行左旋

1
2
3
4
5
6
7
8
         17              
     /        \         
    11        19             
   /  \       / \              
  8    14   18   27          
 / \   /         /            
7   9 12        23

对节点11进行左旋，节点14发生冲突，把节点14变味节点11的右子节点，调整结束这就是一颗AVL树

平衡二叉树(AVL树)_哔哩哔哩_bilibili

如果觉得我的文章对您有用，赏我一包辣条吧！您的支持将鼓励我继续创作！也可以加我微信一起交流学习，折腾点有意思事情。