AVL 树的原理与实现

1 AVL 树的概念与性质

为了降低 二叉排序树 的高度,提高查询效率,前苏联数学家 G.M.Adelsen-Velskii 和 E.M.Landis 在 1962 年提出了一种高度平衡的二叉排序树,被称为 AVL 树 (又称平衡二叉排序树)。

AVL 树在保持二叉排序树性质的基础上,还需要满足以下两个性质:

  • 节点的左子树和右子树都是平衡二叉树;
  • 节点的左子树和右子树的高度差的绝对值不超过 1。

节点的左子树和右子树的高度差被称为平衡因子 (Balance Factor),处于平衡态的 AVL 树中任意一个节点的平衡因子只可能是 -1、0 或 1。

如果一个节点的平衡因子的绝对值等于 2,那么以该节点为根的子树就被称为最小不平衡子树,它是失衡后需要调整的目标。

学习过程中我们可以通过使用该网站上的工具来加深理解:AVL Tree Visualization

2 数据类型设定

首先,我们定义一个泛型类 AVLTree<K extends Comparable<K>, V> 表示 AVL 树,其中 K 表示节点键的类型,V 表示节点值的类型。该类包含 rootcount 两个属性,分别用于表示根节点和节点数。然后再在这个类内部声明一个三叉节点类型 Node<K extends Comparable<K>, V>,该静态内部类型包含六个属性:key 表示节点的键,value 表示节点的值,leftrightparent 分别表示节点的左子节点、右子节点和父节点,height 表示节点到的高度(用于计算平衡因子)。最后,在 AVLTree 中设置一些方便获取节点属性的静态方法(让后续的节点操作代码看起来更干净)。代码实现如下:

 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
public class AVLTree<K extends Comparable<K>, V> {

    /**
     * 根节点
     */
    private Node<K, V> root;

    /**
     * 节点总数
     */
    private int count;

    /**
     * 三叉节点类
     */
    private static class Node<K extends Comparable<K>, V> {
        K key;
        V value;
        Node<K, V> left, right, parent;
        int height;

        /**
         * Node 构造方法,创建节点时,需要设置节点的父节点,和节点高度
         */
        Node(K key, V value, Node<K, V> parent, int height) {
            this.key = key;
            this.value = value;
            this.parent = parent;
            this.height = height;
        }

        // getter setter ...
    }

    /**
     * 获取左子节点
     */
    private static <K extends Comparable<K>, V> Node<K, V> leftOf(Node<K, V> n) {
        return n == null ? null : n.left;
    }

    /**
     * 获取右子节点
     */
    private static <K extends Comparable<K>, V> Node<K, V> rightOf(Node<K, V> n) {
        return n == null ? null : n.right;
    }

    /**
     * 获取父节点
     */
    private static <K extends Comparable<K>, V> Node<K, V> parentOf(Node<K, V> n) {
        return n == null ? null : n.parent;
    }

    /**
     * 获取节点高度
     */
    private static <K extends Comparable<K>, V> int heightOf(Node<K, V> n) {
        return n == null ? 0 : n.height;
    }

    /**
     * 设置节点高度
     */
    private static <K extends Comparable<K>, V> void setHeight(Node<K, V> n, int height) {
        if (n != null) {
            n.height = height;
        }
    }

    /**
     * 更新节点高度,值为左右子树高度的较大值 + 1
     */
    private static <K extends Comparable<K>, V> void updateHeight(Node<K, V> n) {
        setHeight(n, Math.max(heightOf(n.left), heightOf(n.right)) + 1);
    }
}

3 旋转操作

当插入或删除节点导致 AVL 树失衡后,需要通过旋转操作恢复平衡。所有类型的二叉排序树的旋转规则都是通用的。

3.1 左旋操作

设有两个节点:pr,其中 rp 的右子节点。二叉树的左旋操作就是将 p 与其右子节点 r 反转:右子节点 r 将成为 p 的父节点,而 p 将成为 r 的左子节点,同时原先 r 的左子节点也将依据二叉排序树的有序性成为 p 的右子节点。代码实现如下:

 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
/**
 * 将 p、p->r 两个节点左旋,同时安置 r 的左子节点
 *  示意图:
 *
 *    pp               pp               pp
 *     \                \                \
 *      p                r                r
 *    /  \             /  \             /  \
 *   l    r    ==>    p   rr    ==>    p   rr
 *       / \         /                / \
 *      rl rr       l   rl           l   rl
 */
private void rotateLeft(Node<K, V> p) {
    if (p != null) {
        // rl 需要左摆到 p 右子节点处,所以先缓存 r 引用
        Node<K, V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        // 然后让 r 短接 p
        r.parent = p.parent;
        if (p.parent == null) {
            // 如果 p 是根节点,则 r 将称为新的根节点
            root = r;
        } else if (p.parent.left == p) {
            // 如果 p 是 p 父节点的左子,那么 r 也做它的左子
            p.parent.left = r;
        } else {
            // 如果 p 是 p 父节点的右子,那么 r 也做它的右子
            p.parent.right = r;
        }
        // 最终,颠倒 p 与 r 的关系
        r.left = p;
        p.parent = r;
    }
}

3.2 右旋操作

右旋操作与左旋操作是镜像的,这里就不再展开了,代码实现如下:

 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
/**
 * 将 p、p->r 两个节点左旋,同时安置 l 的右子节点
 *  示意图:
 *
 *      pp               pp               pp
 *       \                \                \
 *        p                l                l
 *      /  \             /  \             /  \
 *     l    r    ==>    ll   p    ==>    ll   p
 *    / \                     \              / \
 *   ll  lr               lr   r            lr  r
 */
private void rotateRight(Node<K, V> p) {
    if (p != null) {
        Node<K, V> l = p.left;
        // rl 需要左摆到 p 右子节点处,所以先缓存 r 引用
        p.left = l.right;
        if (l.right != null)
            l.right.parent = p;
        // 然后用 l 短接 p
        l.parent = p.parent;
        if (p.parent == null) {
            root = l;
        } else if (p.parent.left == p) {
            p.parent.left = l;
        } else {
            p.parent.right = l;
        }
        // 最后颠倒 l 与 p
        p.parent = l;
        l.right = p;
    }
}

4 再平衡操作

上文说过,最小不平衡子树根节点的左右子树高度差为 2,因此我们需要以这个根节点为中心,往较矮子树的一侧旋转:

  • 如果左子树的高度高于右子树,则将子树的根节点与其左节点向右旋转;
  • 如果右子树的高度高于左子树,则将子树的根节点与其右节点向左旋转。

旋转完成后,还需要从最小不平衡子树的根节点开始,向上遍历更新节点的高度,直到 root 节点。代码实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 最小不平衡子树的再平衡操作
 * @param n 最小不平衡子树的根节点
 */
private void rebalanced(Node<K, V> n) {
    // 获取左右子树的高度
    int lh = Math.abs(heightOf(leftOf(n)));
    int rh = Math.abs(heightOf(rightOf(n)));
    if (lh > rh) {
        // 如果左子树深度大于右子树,右旋
        rotateRight(n);
    } else {
        // 否则左旋
        rotateLeft(n);
    }
    // 从 n 开始,向上遍历更新各节点高度,直到 root
    Node<K, V> p = n;
    do {
        updateHeight(p);
        p = parentOf(p);
    } while (p != null);
}

5 插入节点

AVL 树插入节点的过程与 二叉排序树相似,都是通过二分法查找空位并插入。只是向 AVL 树中插入节点时需要维护新节点所在链路的节点的高度,并且在插入完成后需要寻找最小不平衡子树并执行再平衡操作。代码实现如下:

 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
public void insert(K key, V value) {
    Node<K, V> t = this.root;
    if (t == null) {
        // 空树,直接作为根节点插入
        root = new Node<>(key, value, null, 1);
        count = 1;
        return;
    }

    // 递归查找插入位置,同二叉排序树
    Node<K, V> p;
    int compare;
    do {
        p = t;
        compare = key.compareTo(t.key);
        if (compare < 0) {
            // 向左递归
            t = t.left;
        } else if (compare > 0){
            // 向右递归
            t = t.right;
        } else {
            // 执行更新操作
            t.setValue(value);
            return;
        }
    } while (t != null);
    ++count;
    Node<K, V> e = new Node<>(key, value, p, 1);
    if (compare < 0) {
        // 作为左子节点插入
        p.left = e;
    } else {
        // 作为右子节点插入
        p.right = e;
    }

    // 从插入节点的父节点开始,向上寻找最小不平衡子树根节点
    // 同时,更新一路上遇到的节点的高度
    Node<K, V> n = null;
    do {
        updateHeight(p);
        int lh = Math.abs(heightOf(leftOf(p)));
        int rh = Math.abs(heightOf(rightOf(p)));
        int balanceFactor = lh - rh;
        if (balanceFactor > 1 || balanceFactor < -1) {
            n = p;
            break;
        } else {
            p = p.parent;
        }
    } while (p != null);
    // 如果存在最小不平衡子树,则执行再平衡操作
    if (n != null) {
        rebalanced(n);
    }
}

6 删除节点

AVL 树删除节点的过程也与 二叉排序树相似,都是通过二分法找到目标节点并删除。只是在删除过程中,AVL 树需要维护节点的高度,并且删除完成后需要向上寻找最小不平衡子树的根节点,对其进行再平衡操作。代码实现如下:

 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
public V remove(K key) {
    Node<K, V> n = this.root;
    if (n == null) { //判空
        return null;
    }
    // 递归查找删除位置,同二叉排序树
    Node<K, V> t = null;
    int compare;
    do {
        compare = key.compareTo(n.key);
        if (compare < 0) {
            n = n.left; // 向左递归
        } else if (compare > 0) {
            n = n.right; // 向右递归
        } else {
            // 找到了
            t = n;
            break;
        }
    } while (n != null);
    if (t == null) { // 没找到目标节点
        return null;
    }
    // 缓存旧值
    V oldValue = t.value;
    // 删除节点 t,如果失衡则进行再平衡
    deleteNode(t);
    return oldValue;
}

该方法找到 key 等于参数的节点后,会调用 deleteNode 方法完成后续工作。deleteNode 删除节点时会观察被删除节点的子节点情况:

  1. 如果被删除节点是叶子节点,则直接删除这个节点,并从被删节点的父节点开始向上寻找最小不平衡子树;
  2. 如果被删除节点存在唯一子节点,则用这个唯一的子节点代替被删除节点,然后从这个被挪上来的子节点开始,向上寻找最小不平衡子树;
  3. 如果被删除节点存在两个子节点,则用其左子树中的最大节点覆盖被删除节点,然后递归删除这个左子树中的最大节点。

    也可以使用右子树中的最小节点

代码实现如下:

 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
private void deleteNode(Node<K, V> e) {
    --count;

    // 如果被删除节点的左右子节点均不为空,则使用左子树中的最大节点覆盖被删除的节点
    if (e.left != null && e.right != null) {
        Node<K, V> s = getMaxNode(e.left);
        e.key = s.key;
        e.value = s.value;
        // 并将 e 引用指向左子树最大节点,准备删除
        e = s;
    }

    if (e.left == null && e.right == null) {
        // 如果 e 是叶子节点,直接删除即可
        if (e.parent.left == e)
            e.parent.left = null;
        else
            e.parent.right = null;
    } else if (e.left != null) {
        // 如果 e 存在左子节点,则用左子节点短接 e
        if (e.parent.left == e)
            e.parent.left = e.left;
        else
            e.parent.right = e.left;
    } else {
        // 如果 e 存在右子节点,则用右子节点短接 e
        if (e.parent.left == e)
            e.parent.left = e.right;
        else
            e.parent.right = e.right;
    }
    Node<K, V> p = e.parent; // 先缓存 e 的父节点
    e.parent = null; // 彻底摘下 e

    // 从被摘下节点 e 的父节点开始,向上寻找最小不平衡子树根节点
    // 同时,更新一路上遇到的节点的高度
    Node<K, V> n = null;
    do {
        updateHeight(p);
        int lh = Math.abs(heightOf(leftOf(p)));
        int rh = Math.abs(heightOf(rightOf(p)));
        int balanceFactor = lh - rh;
        if (balanceFactor > 1 || balanceFactor < -1) {
            n = p;
            break;
        } else {
            p = p.parent;
        }
    } while (p != null);
    // 如果存在最小不平衡子树,则执行再平衡操作
    if (n != null) {
        rebalanced(n);
    }
}
  • 其中,获取左子树的最大节点的方法实现如下:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    
    /**
     * 获取子树中的最大节点
     * @param r 子树根节点
     */
    private Node<K, V> getMaxNode(Node<K, V> r) {
        if (r.right == null) {
            return r;
        } else {
            return getMaxNode(r.right);
        }
    }

至此,AVL 树的特性就介绍完了。