平衡查找树之AVL树

发表于 | 分类于 ， ， | | 阅读次数

概述

AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis,它是最先发明的自平衡二叉查找树.

在AVL树中任何节点的两个子树的高度最大差别为一.并且,查找、插入、删除等操作在平均和最坏情况下都是O(log n).

AVL树的基本操作都与二叉查找树的算法一致,只有在插入、删除等这种会改变树的平衡性的操作需要使用一些旋转操作来修正树的平衡性.

平衡因子

节点的平衡因子一般是它的左子树的高度减去它的右子树的高度(相反也可以).带有平衡因子为1、0或-1的节点被认为是平衡的.带有平衡因子为-2或2的节点被认为是不平衡的.

计算树的高度与平衡因子的代码如下.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// calculate node x depth
private int calcDepth(Node x) {
    int depth = 0;
    if (x.left != null)
        depth = x.left.depth;
    if (x.right != null && x.right.depth > depth)
        depth = x.right.depth;
    // parent + left or right depth
    depth++;
    return depth;
}
// calculate node x balance(left.depth - right.depth)
private int calcBalance(Node x) {
    int leftDepth = 0;
    int rightDepth = 0;
    if (x.left != null)
        leftDepth = x.left.depth;
    if (x.right != null)
        rightDepth = x.right.depth;
    return leftDepth - rightDepth;
}

旋转

旋转操作是用于修复树的平衡性的,它保证了树的有序性与平衡性(旋转操作的具体讲解可以参考《Algorithms,4th Edition》读书笔记-红黑二叉查找树).

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
private Node rotateLeft(Node x) {
    Node t = x.right;
    x.right = t.left;
    t.left = x;
    if (x.parent != null) {
        t.parent = x.parent;
        if (x.parent.left == x)
            x.parent.left = t;
        else
            x.parent.right = t;
    } else {
        t.parent = null;
        root = t;
    }
    x.parent = t;
    // calculate depth and balance
    x.depth = calcDepth(x);
    x.balance = calcBalance(x);
    t.depth = calcDepth(t);
    t.balance = calcBalance(t);
    // calculate size
    t.size = x.size;
    x.size = 1 + size(x.left) + size(x.right);
    return t;
}
private Node rotateRight(Node x) {
    Node t = x.left;
    x.left = t.right;
    t.right = x;
    if (x.parent != null) {
        t.parent = x.parent;
        if (x.parent.left == x)
            x.parent.left = t;
        else
            x.parent.right = t;
    } else {
        t.parent = null;
        root = t;
    }
    x.parent = t;
    // calculate depth and balance
    x.depth = calcDepth(x);
    x.balance = calcBalance(x);
    t.depth = calcDepth(t);
    t.balance = calcBalance(t);
    // calculate size
    t.size = x.size;
    x.size = 1 + size(x.left) + size(x.right);
    return t;
}

平衡修正

当一个节点被认为是不平衡的时候,我们需要使用一些旋转操作来修正树的平衡,一般有以下情况需要进行旋转.

  • 例如当前节点为x,对x进行平衡修正需要进行以下判断.
  • 当x的平衡因子大于等于2时(左子树高度偏高),对其进行右旋转.
  • 当x的左子树的平衡因子等于-1时(左子树的右子节点高度偏高),对x的左子树进行左旋转.
  • 当x的平衡因子小于等于-2时(右子树高度偏高),对其进行左旋转.
  • 当x的右子树的平衡因子等于1时(右子树的左子节点高度偏高),对x的右子树进行右旋转.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void balance(Node x) {
    while (x != null) {
        x.depth = calcDepth(x);
        x.balance = calcBalance(x);
        // if x left subtree high,rotateRight
        if (x.balance >= 2) {
            // if x.left.right high,rotateLeft
            if (x.left != null && x.left.balance == -1) {
                x.left = rotateLeft(x.left);
            }
            x = rotateRight(x);
        }
        // if x right subtree high,rotateLeft
        if (x.balance <= -2) {
            // if x.right.left high,rotateRight
            if (x.right != null && x.right.balance == 1) {
                x.right = rotateRight(x.right);
            }
            x = rotateLeft(x);
        }
        x.size = 1 + size(x.left) + size(x.right);
        x = x.parent;
    }
}

插入

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
public void put(K key, V value) {
    if (key == null)
        throw new IllegalArgumentException("called put() with key is null.");
    if (value == null) {
        remove(key);
        return;
    }
    put(root, key, value);
}
private void put(Node x, K key, V value) {
    Node parent = x;
    int cmp = 0;
    while (x != null) {
        parent = x;
        cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x = x.left;
        } else if (cmp > 0) {
            x = x.right;
        } else {
            x.value = value;
            return;
        }
    }
    // if not find key,create new node
    x = new Node(key, value, 1, parent);
    if (parent != null) {
        if (cmp < 0)
            parent.left = x;
        else
            parent.right = x;
    } else {
        root = x;
    }
    // fixup balance
    balance(x);
}

end

  • Email : sylvanassun_xtz@163.com
  • 文中的完整实现代码见我的GitHub & Gist
分享