【数据结构与算法】系列十三 - AVL树

发表于 | 分类于 ， ， ，
| 字数统计 2.4k 字 | 阅读时长 10 分钟

AVL树是最早发明的自平衡二叉搜索树之一。

一、AVL树

AVL取名于两位发明者的名字（*G. M. Adelson-Velsky 和 E. M. Landis*）。也有人把AVL树念做“艾薇儿树”。

1.1. 平衡因子

平衡因子（Balance Factor）：某结点的左右子树的高度差。

如上图，节点5、10、14都是叶子节点，平衡因子是0；节点12只有一个左子节点，平衡因子是1；节点13左子树高度是2，右子树高度是1，平衡因子是1；节点4没有左子树，右子树高度是1，平衡因子是-1；节点9没有左子树，右子树高度是3，平衡因子是-3；节点7的左子树高度是2，右子树高度是4，平衡因子是-2。

1.2. AVL树的特点

  • 每个节点的平衡因子只可能是1、0、-1（绝对值 ≤ 1，如果超过 1，称之为“失衡”），所以每个节点的左右子树高度差不超过1
  • 搜索、添加、删除的时间复杂度是O(logn)

1.3. 平衡对比

输入数据：35, 37, 34, 56, 25, 62, 57, 9, 74, 32, 94, 80, 75, 100, 16, 82。

1.4. 继承结构

二叉搜索树继承自二叉树，而AVL树和红黑树是在二叉搜索树基础上进行的调整，所以AVL树和红黑树可以是二叉搜索树的子类。

1.5. 添加导致的失衡

示例：往下面这棵子树中添加13（注意：上图中节点9并不是根节点。）。

在没有添加13之前，是一棵平衡树。添加13后，节点14和节点15的平衡因子变成了2（原来是1），节点9的平衡因子变成-2（原来是-1），所以添加13后导致失衡。最坏情况是可能会导致所有祖先节点都失衡，但是父节点（节点12）和非祖先节点（节点4、6、8、16）都不可能失衡。

解决方案：单旋和双旋。

二、单旋和双旋

在每一次插入数值之后，树的平衡性都可能被破坏，这时可以通过一个简单的操作来矫正平衡，这个操作就是旋转。

旋转的目的就是降低高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

  • 所谓的左旋和右旋都是以子树为原点的：如b是a的子树，那么旋转就围绕b来进行。
  • 如果b是a的左子树，那么就围绕b将a向右旋转，看着就像是a直接掉下来了，掉成了b的右子树。
  • 如果b是a的右子树，那么就围绕b将a向左旋转，看着就像是a直接掉下来了，掉成了b的左子树。

插入节点时分四种情况，四种情况对应的旋转方法是不同的，例如对于被破坏平衡的节点 a 来说：

插入方式 描述 旋转方式
LL 在a的左子树根节点的左子树上（a.left.left）插入节点而破坏平衡 右旋转
RR 在a的右子树根节点的右子树上（a.right.right）插入节点而破坏平衡 左旋转
LR 在a的左子树根节点的右子树上插入节点而破坏平衡 先左旋后右旋
RL 在a的右子树根节点的左子树上插入节点而破坏平衡 先右旋后左旋

LL和RR因为只旋转一次，又称为单旋；LR和RL旋转了两次，称为双旋。

2.1. LL - 右旋转

如上图一个简单的AVL树，如果在插入一个元素3，就会变成下面这样，破坏平衡。

被破坏了平衡首先要找到是哪个树被破坏了平衡，然后调整这个树。然后继续往上一个一个的调整。

既然是被新插入的节点3破坏的，那么不平衡的树一定在从新插入的节点3到根节点8的路径上。找离新插入的节点最近的不平衡的树进行调整。上图中就是节点7，节点7的左子树高度为2，右子树为空，高度为2 ，不平衡。根据表格要进行右旋转。

先把7这颗不平衡的树挑出来：

这棵树是最近的不平衡的树，把左子树5向上提一下，这时旋转就很明显了，抓着5向上一提，7就掉到5的右边了，成了5的右子树。

这个过程就是右旋：

这时继续往上找，发现每个节点都符合了平衡条件，所以整棵树就变成了AVL树。

那如果节点5本来就有了右子树呢？照样右旋转，只要把原来5的右子树变成旋转后的7的左子树就行了。因为5的右子树肯定比5大，但是也肯定比7小的：

但这棵树的根节点是不平衡的，还需要使用后面的LR旋转来调整。

2.2. RR - 左旋转

在右子树的右子树上插入节点破坏的平衡需要左旋转来矫正。左旋转和右旋转类似，都是单旋转。

2.3. LR - 先左旋再右旋

如果在第一个例子中插入的不是3，而是6，就成了下面的样子，依然说破坏了平衡。

被破坏平衡的树依然是7，但是这次就不能通过一次旋转解决了，怎么旋转都不行。要从6开始到7进行先左旋再右旋才可以矫正平衡：

2.4. RL - 先右旋再左旋

当破坏平衡的节点是这个树的右子树的左子树时，要进行先右旋转再左旋转来矫正。

同样是从破坏平衡的那个节点开始旋转，先右旋转后左旋转：

2.5. 总结

  • 添加
    • 可能会导致所有祖先节点都失衡
    • 只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡（仅需O(1)次调整）
  • 删除
    • 可能会导致父节点或祖先节点失衡（只有1个节点会失衡）
    • 恢复平衡后，可能会导致更高层的祖先节点失衡（最多需要O(logn)次调整）
  • 平均时间复杂度
    • 搜索：O(logn)
    • 添加：O(logn)，仅需O(1)次的旋转操作
    • 删除：O(logn)，最多需要O(logn)次的旋转操作

2.6. 代码

不管是哪一种旋转方式（LL、RR、LR、RL），同一份数据不同二叉搜索树，旋转后的结果都是一样的，因此也可以使用统一旋转对树恢复平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
package com.daben.tree;

import java.util.Comparator;

public class AVLTree<E> extends BST<E> {
  public AVLTree() {
    this(null);
  }

  public AVLTree(Comparator<E> comparator) {
    super(comparator);
  }

  @Override
  protected Node<E> createNode(E element, Node<E> parent) {
    return new AVLNode<>(element, parent);
  }

  @Override
  // 添加节点后（需要更新高度和恢复平衡）
  protected void afterAdd(Node<E> node) {
    while ((node = node.parent) != null) {
      if (isBalanced(node)) {
        // 更新高度
        updateHeight(node);
      } else {
        // 恢复平衡
        rebalance(node);
        // 整棵树恢复平衡（添加只会导致一个节点失衡）
        break;
      }
    }
  }

  @Override
  // 删除节点后（需要更新高度和恢复平衡）
  protected void afterRemove(Node<E> node) {
    while ((node = node.parent) != null) {
      if (isBalanced(node)) {
        // 更新高度
        updateHeight(node);
      } else {
        // 恢复平衡（删除会导致上层节点全部失衡）
        rebalance(node);
      }
    }
  }

  /**
    * 恢复平衡
    * @param grand 高度最低的那个不平衡节点
    */
  @SuppressWarnings("unused")
  private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>)grand).tallerChild();
    Node<E> node = ((AVLNode<E>)parent).tallerChild();
    if (parent.isLeftChild()) { // L
      if (node.isLeftChild()) { // LL
        rotateRight(grand);
      } else { // LR
        rotateLeft(parent);
        rotateRight(grand);
      }
    } else { // R
      if (node.isLeftChild()) { // RL
        rotateRight(parent);
        rotateLeft(grand);
      } else { // RR
        rotateLeft(grand);
      }
    }
  }

  // 左旋
  private void rotateLeft(Node<E> grand) {
    Node<E> parent = grand.right;
    Node<E> child = parent.left;
    grand.right = child;
    parent.left = grand;
    afterRotate(grand, parent, child);
  }

  // 右旋
  private void rotateRight(Node<E> grand) {
    Node<E> parent = grand.left;
    Node<E> child = parent.right;
    grand.left = child;
    parent.right = grand;
    afterRotate(grand, parent, child);
  }

  // 旋转后需要更新父节点和高度
  private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
    // 让parent成为子树的根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
      grand.parent.left = parent;
    } else if (grand.isRightChild()) {
      grand.parent.right = parent;
    } else { // grand是root节点
      root = parent;
    }
    
    // 更新child的parent
    if (child != null) {
      child.parent = grand;
    }
    
    // 更新grand的parent
    grand.parent = parent;
    
    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
  }

  // 是否平衡
  private boolean isBalanced(Node<E> node) {
    return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
  }

  // 更新高度（该方法主要是为了减少类型强制转换）
  private void updateHeight(Node<E> node) {
    ((AVLNode<E>)node).updateHeight();
  }

  private static class AVLNode<E> extends Node<E> {
    int height = 1;
    
    public AVLNode(E element, Node<E> parent) {
      super(element, parent);
    }
    
    // 计算平衡因子
    public int balanceFactor() {
      int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
      int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
      return leftHeight - rightHeight;
    }
    
    // 更新节点高度
    public void updateHeight() {
      int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
      int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
      height = 1 + Math.max(leftHeight, rightHeight);
    }
    
    // 查找最高子节点
    public Node<E> tallerChild() {
      int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
      int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
      if (leftHeight > rightHeight) return left;
      if (leftHeight < rightHeight) return right;
      return isLeftChild() ? left : right;
    }
    
    @Override
    public String toString() {
      String parentString = "null";
      if (parent != null) {
        parentString = parent.element.toString();
      }
      return element + "_p(" + parentString + ")_h(" + height + ")";
    }
  }
}

LeetCode-平衡二叉树：https://leetcode-cn.com/problems/balanced-binary-tree/

参考资料：
http://blog.csdn.net/qq_25806863/article/details/74755131