KWAN的解忧杂货铺

# 一.简介

# 1.AVL 历史

AVL 树是一种自平衡二叉搜索树，由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字：Adelson-Velsky 和 Landis，他们是苏联数学家，于 1962 年发表了一篇论文，详细介绍了 AVL 树的概念和性质。

在二叉搜索树中，如果插入的元素按照特定的顺序排列，可能会导致树变得非常不平衡，从而降低搜索、插入和删除的效率。为了解决这个问题，AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2，则通过旋转操作来重新平衡树。

AVL 树是用于存储有序数据的一种重要数据结构，它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率，而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展，AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。

如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下图

image-20230313090500760

通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边仍然小，右边仍然大）

image-20230313090817485

# 2.如何判断失衡？

如果一个节点的左右孩子，高度差超过 1，则此节点失衡，才需要旋转

叶子节点的高度默认为 1

网上遍历,高度越高

# 3.节点的高度

如何得到节点高度？一种方式之前做过的一道题目：E05. 求二叉树的最大深度（高度），但由于求高度是一个非常频繁的操作，因此将高度作为节点的一个属性，将来新增或删除时及时更新，默认为 1（按力扣说法）

static class AVLNode {
    int height = 1;
    int key;
    Object value;
    AVLNode left;
    AVLNode right;
    // ...
}
1
2
3
4
5
6
7
8

求高度代码

这里加入了 height 函数方便求节点为 null 时的高度

private int height(AVLNode node) {
    return node == null ? 0 : node.height;
}
1
2
3

更新高度代码

将来新增、删除、旋转时，高度都可能发生变化，需要更新。下面是更新高度的代码

private void updateHeight(AVLNode node) {
    node.height = Integer.max(height(node.left), height(node.right)) + 1;
}
1
2
3

# 4.何时触发失衡判断？

定义平衡因子（balance factor）如下

$$ 平衡因子 = 左子树高度 - 右子树高度 $$

当平衡因子

  • bf = 0，1，-1 时，表示左右平衡
  • bf > 1 时，表示左边太高
  • bf < -1 时，表示右边太高

对应代码

private int bf(AVLNode node) {
    return height(node.left) - height(node.right);
}
1
2
3

当插入新节点，或删除节点时，引起高度变化时，例如

image-20230310153645397

目前此树平衡，当再插入一个 4 时，节点们的高度都产生了相应的变化，8 节点失衡了

image-20230310153803661

在比如说，下面这棵树一开始也是平衡的

image-20230310154155728

当删除节点 8 时，节点们的高度都产生了相应的变化，6 节点失衡了

image-20230310154232729

# 二.自平衡

# 1.失衡的四种情况

  • LL
  • LR
  • RL
  • RR

# 2.LL

image-20230310154459709

  • 失衡节点（图中 8 红色）的 bf > 1，即左边更高
  • 失衡节点的左孩子（图中 6）的 bf >= 0 即左孩子这边也是左边更高或等高

# 3.LR

image-20230310154858754

  • 失衡节点（图中 8）的 bf > 1，即左边更高
  • 失衡节点的左孩子（图中 6 红色）的 bf < 0 即左孩子这边是右边更高

对称的还有两种情况

# 4.RL

image-20230310155048187

  • 失衡节点（图中 3）的 bf <-1，即右边更高
  • 失衡节点的右孩子（图中 6 红色）的 bf > 0，即右孩子这边左边更高

# 5.RR

image-20230310155347349

  • 失衡节点（图中 3）的 bf <-1，即右边更高
  • 失衡节点的右孩子（图中 6 红色）的 bf <= 0，即右孩子这边右边更高或等高

# 6.解决失衡

失衡可以通过树的旋转解决。什么是树的旋转呢？它是在不干扰元素顺序的情况下更改结构，通常用来让树的高度变得平衡。

观察下面一棵二叉搜索树，可以看到，旋转后，并未改变树的左小右大特性，但根、父、孩子节点都发生了变化

      4                                   2
     / \             4 right             / \
    2   5      -------------------->    1   4
   / \         <--------------------       / \
  1   3              2 left               3   5
1
2
3
4
5

# 7.右旋

旋转前

image-20230310162158692

  • 红色节点，旧根（失衡节点）
  • 黄色节点，旧根的左孩子，将来作为新根，旧根是它右孩子
  • 绿色节点，新根的右孩子，将来要换爹作为旧根的左孩子

旋转后

image-20230310162442932

代码

private AVLNode rightRotate(AVLNode red) {
    AVLNode yellow = red.left;
    AVLNode green = yellow.right;
    yellow.right = red;
    red.left = green;
    return yellow;
}
1
2
3
4
5
6
7

# 8.左旋

旋转前

image-20230310162945078

  • 红色节点，旧根（失衡节点）
  • 黄色节点，旧根的右孩子，将来作为新根，旧根是它左孩子
  • 绿色节点，新根的左孩子，将来要换爹作为旧根的右孩子

旋转后

image-20230310163019508

代码

private AVLNode leftRotate(AVLNode red) {
    AVLNode yellow = red.right;
    AVLNode green = yellow.left;
    yellow.left = red;
    red.right = green;
    return yellow;
}
1
2
3
4
5
6
7

# 9.左右旋

指先左旋左子树，再右旋根节点（失衡），这时一次旋转并不能解决失衡

image-20230310171424362

左子树旋转后

image-20230310171636904

根右旋前

image-20230310171821578

根右旋后

image-20230310171903417

代码

private AVLNode leftRightRotate(AVLNode root) {
    root.left = leftRotate(root.left);
    return rightRotate(root);
}
1
2
3
4

# 10.右左旋

指先右旋右子树，再左旋根节点（失衡）

image-20230310172212302

右子树右旋后

image-20230310172234154

根左旋前

image-20230310172303012

根左旋后

image-20230310172317379

代码

private AVLNode rightLeftRotate(AVLNode root) {
    root.right = rightRotate(root.right);
    return leftRotate(root);
}
1
2
3
4

判断及调整平衡代码

private AVLNode balance(AVLNode node) {
    if (node == null) {
        return null;
    }
    int bf = bf(node);
    if (bf > 1 && bf(node.left) >= 0) {
        return rightRotate(node);
    } else if (bf > 1 && bf(node.left) < 0) {
        return rightLeftRotate(node);
    } else if (bf < -1 && bf(node.right) > 0) {
        return leftRightRotate(node);
    } else if (bf < -1 && bf(node.right) <= 0) {
        return rightRotate(node);
    }
    return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

以上四种旋转代码里，都需要更新高度，需要更新的节点是红色、黄色，而绿色节点高度不变

# 三.新增与删除

# 1.新增

public void put(int key, Object value) {
    root = doPut(root, key, value);
}

private AVLNode doPut(AVLNode node, int key, Object value) {
    if (node == null) {
        return new AVLNode(key, value);
    }
    if (key == node.key) {
        node.value = value;
        return node;
    }
    if (key < node.key) {
        node.left = doPut(node.left, key, value);
    } else {
        node.right = doPut(node.right, key, value);
    }
    updateHeight(node);
    return balance(node);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 2.删除

public void remove(int key) {
    root = doRemove(root, key);
}

private AVLNode doRemove(AVLNode node, int key) {
    if (node == null) {
        return null;
    }
    if (key < node.key) {
        node.left = doRemove(node.left, key);
    } else if (node.key < key) {
        node.right = doRemove(node.right, key);
    } else {
        if (node.left == null) {
            node = node.right;
        } else if (node.right == null) {
            node = node.left;
        } else {
            AVLNode s = node.right;
            while (s.left != null) {
                s = s.left;
            }
            s.right = doRemove(node.right, s.key);
            s.left = node.left;
            node = s;
        }
    }
    if (node == null) {
        return null;
    }
    updateHeight(node);
    return balance(node);
}
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

# 3.完整代码

public class AVLTree {
    static class AVLNode {
        int height = 1;
        int key;
        Object value;
        AVLNode left;
        AVLNode right;

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    AVLNode root;

    private AVLNode leftRotate(AVLNode p) {
        AVLNode r = p.right;
        AVLNode b = r.left;
        r.left = p;
        p.right = b;
        updateHeight(p);
        updateHeight(r);
        return r;
    }

    private void updateHeight(AVLNode node) {
        node.height = Integer.max(height(node.left), height(node.right)) + 1;
    }

    private AVLNode rightRotate(AVLNode r) {
        AVLNode a = r.left;
        AVLNode b = a.right;
        a.right = r;
        r.left = b;
        updateHeight(r);
        updateHeight(a);
        return a;
    }

    private AVLNode leftRightRotate(AVLNode p) {
        AVLNode r = p.left;
        p.left = leftRotate(r);
        return rightRotate(p);
    }

    private AVLNode rightLeftRotate(AVLNode p) {
        AVLNode r = p.right;
        p.right = rightRotate(r);
        return leftRotate(p);
    }

    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }



    public void remove(int key) {
        root = doRemove(root, key);
    }

    private AVLNode doRemove(AVLNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = doRemove(node.left, key);
        } else if (node.key < key) {
            node.right = doRemove(node.right, key);
        } else {
            if (node.left == null) {
                node = node.right;
            } else if (node.right == null) {
                node = node.left;
            } else {
                AVLNode s = node.right;
                while (s.left != null) {
                    s = s.left;
                }
                s.right = doRemove(node.right, s.key);
                s.left = node.left;
                node = s;
            }
        }
        if (node == null) {
            return null;
        }
        updateHeight(node);
        return balance(node);
    }

    public void put(int key, Object value) {
        root = doPut(root, key, value);
    }

    private AVLNode doPut(AVLNode node, int key, Object value) {
        if (node == null) {
            return new AVLNode(key, value);
        }
        if (key == node.key) {
            node.value = value;
            return node;
        }
        if (key < node.key) {
            node.left = doPut(node.left, key, value);
        } else {
            node.right = doPut(node.right, key, value);
        }
        updateHeight(node);
        return balance(node);
    }

    private int bf(AVLNode node) {
        return height(node.left) - height(node.right);
    }

    private AVLNode balance(AVLNode node) {
        if (node == null) {
            return null;
        }
        int bf = bf(node);
        if (bf > 1 && bf(node.left) >= 0) {
            return rightRotate(node);
        } else if (bf > 1 && bf(node.left) < 0) {
            return rightLeftRotate(node);
        } else if (bf < -1 && bf(node.right) > 0) {
            return leftRightRotate(node);
        } else if (bf < -1 && bf(node.right) <= 0) {
            return rightRotate(node);
        }
        return node;
    }
}
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

# 4.小结

AVL 树的优点：

  1. AVL 树是一种自平衡树，保证了树的高度平衡，从而保证了树的查询和插入操作的时间复杂度均为 O(logn)。
  2. 相比于一般二叉搜索树，AVL 树对查询效率的提升更为显著，因为其左右子树高度的差值不会超过 1，避免了二叉搜索树退化为链表的情况，使得整棵树的高度更低。
  3. AVL 树的删除操作比较简单，只需要像插入一样旋转即可，在旋转过程中树的平衡性可以得到维护。

AVL 树的缺点：

  1. AVL 树每次插入或删除节点时需要进行旋转操作，这个操作比较耗时，因此在一些应用中不太适用。
  2. 在 AVL 树进行插入或删除操作时，为保持树的平衡需要不断进行旋转操作，在一些高并发环节和大数据量环境下，这可能会导致多余的写锁导致性能瓶颈。
  3. AVL 树的旋转操作相对较多，因此在一些应用中可能会造成较大的空间浪费。
上次更新: 10/29/2024, 10:27:50 AM

← 05-红黑树 →