AVL树实现

发表于 本文字数： 1.4k 阅读时长 ≈ 5 分钟

AVL介绍

平衡二叉树(BST, Balanced Binary Tree又称AVL Tree)是自平衡的二叉搜索树(BST, Binary Search Tree)，二叉搜索树的问题是，如果插入顺序是有序的，会导致树退化为线性结构，查询的复杂度退化为$O(N)$。

定义

首先介绍平衡因子(BF, Balance Factor)：$BF(T) = h_L - h_R$，其中$h_L$和$h_R$分别是$T$左右子树的高度。
由此可以进行AVL树的定义：

  • 空树
  • 任一节点的$|BF(T)|<=1$

插入

  • 普通BST插入后，判断平衡因子，可以得到“偏斜”出现在左右哪个子孩子，再判断那个子孩子的平衡因子，即可得知导致不平衡的节点的具体相对位置。根据相对位置的分类，可以分为：LL、RR、LR、RL。
  • 当插入一个节点导致整个树多个节点发现不平衡时，只处理最靠近插入节点的不平衡节点，即可解决其他节点的不平衡问题，这一点通过递归来实现时是默认满足的

删除

  • 普通BST删除后，判断平衡因子，判断逻辑同插入，但是需要明确的一点是，删除操作时，某个发现不平衡的节点$T$的某侧”偏斜”孩子的平衡因子可能是0（只有删除才会有这个情况出现），此时也是需要进行旋转调整。如果它是左孩子，则LL、LR都可以（简单起见用LL）；如果它是右孩子，则RR、RL都可以（简单起见用RR）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
下图中，删除11时，8发现不平衡，但是8的“偏斜”一侧子孩子5的平衡因子是0
                8
            /       \
        5               [11]
      /  \
    1      6
此时如果进行LL调整：
                5
            /       \
        1               8
                      /
                    6
此时如果进行LR调整：
                6
            /       \
        5               8
      /
    11
虽然结果不同，但是调整后都能够得到平衡
  • 删除操作后，整个树可能会多次进行平衡调整
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
下图中删除25节点后，会分别在整棵树两侧各进行一次调整
                                20
                        /                \
                17                              30
             /      \                       /        \
        15              18              25              35
      /    \               \                              \
    14     16               19                              40
  /
13
调整后
                                17
                        /                \
                15                              20
            /       \                       /       \
        14              16              18              35
      /                                    \          /    \
    13                                      19      30      40

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
public class Node
{
    public int Id;
    public int Height;
    public Node? Left;
    public Node? Right;

    public int Factor => (Left?.Height ?? 0) - (Right?.Height ?? 0);

    public void RefreshHeight()
    {
        Height = Math.Max((Left?.Height ?? 0), (Right?.Height ?? 0)) + 1;
    }
}

public class AVLTree
{
    public Node? Root { get; private set; }

    public AVLTree() { }

    public AVLTree(int[] ids)
    {
        foreach (var id in ids)
            Insert(id);
    }

    public void Insert(int id)
    {
        Root = DoInsert(Root, id);
    }

    private static Node DoInsert(Node? node, int id)
    {
        // 新节点
        if (node == null)
            return new Node() { Id = id, Height = 1, Left = null, Right = null };
        if (id > node.Id)
            node.Right = DoInsert(node.Right, id);
        else if (id < node.Id)
            node.Left = DoInsert(node.Left, id);
        else
            return node; // 重复key不插入
        // 刷新插入后的树高
        node.RefreshHeight();
        // 判断是否要旋转
        var factor = node.Factor;
        if (factor > 1)
        {
            var leftChild = node.Left!;
            var leftChildFactor = leftChild.Factor;
            if (leftChildFactor >= 0) // 这样写，但是不可能出现等于
                return LL(node);
            else
                return LR(node);
        }
        else if (factor < -1)
        {
            var rightChild = node.Right!;
            var rightChildFactor = rightChild.Factor;
            if (rightChildFactor <= 0) // 这样写，但是不可能出现等于
                return RR(node);
            else
                return RL(node);
        }
        return node;
    }

    public Node? Find(int id)
    {
        return DoFind(Root, id);
    }

    private static Node? DoFind(Node? node, int id)
    {
        if (node == null)
            return default;
        if (id > node.Id)
            return DoFind(node.Right, id);
        else if (id < node.Id)
            return DoFind(node.Left, id);
        return node;
    }

    public void Remove(int id)
    {
        Root = DoRemove(Root, id);
    }

    private static Node? DoRemove(Node? node, int id)
    {
        if (node == null)
            return default;
        if (id > node.Id)
            node.Right = DoRemove(node.Right, id);
        else if (id < node.Id)
            node.Left = DoRemove(node.Left, id);
        else
        {
            if (node.Left == null && node.Right == null)
                node = default;
            else if (node.Left == null || node.Right == null)
                node = node.Left ?? node.Right;
            else
            {
                var rightMinNode = node.Right;
                while (rightMinNode.Left != null)
                    rightMinNode = rightMinNode.Left;
                node.Id = rightMinNode.Id;
                node.Right = DoRemove(node.Right, rightMinNode.Id);
            }
        }
        if (node == default)
            return node;
        // 刷新插入后的树高
        node.RefreshHeight();
        // 判断是否要旋转
        var factor = node.Factor;
        if (factor > 1)
        {
            var leftChild = node.Left!;
            var leftChildFactor = leftChild.Factor;
            if (leftChildFactor >= 0) // 删除时，需要判断等于0
                node = LL(node);
            else
                node = LR(node);
        }
        else if (factor < -1)
        {
            var rightChild = node.Right!;
            var rightChildFactor = rightChild.Factor;
            if (rightChildFactor <= 0) // 删除时，需要判断等于0
                node = RR(node);
            else
                node = RL(node);
        }
        return node;
    }

    private static Node LL(Node maxNode)
    {
        var midNode = maxNode.Left!;
        maxNode.Left = midNode.Right;
        midNode.Right = maxNode;

        maxNode.RefreshHeight();
        midNode.RefreshHeight();
        return midNode;
    }

    private static Node RR(Node minNode)
    {
        var midNode = minNode.Right!;
        minNode.Right = midNode.Left;
        midNode.Left = minNode;

        minNode.RefreshHeight();
        midNode.RefreshHeight();
        return midNode;
    }

    // LR旋转可以替换为对maxNode左孩子minNode执行左旋(LL)，然后再对maxNode执行右旋(RR)
    // 本方法不想分两步，直接一步将MidNode"提上来"
    private static Node LR(Node maxNode)
    {
        var minNode = maxNode.Left!;
        var midNode = minNode.Right!;
        // 可能失去孩子的两个节点分给他们可能存在的新孩子
        minNode.Right = midNode.Left;
        maxNode.Left = midNode.Right;
        // 中间节点成为新的父亲
        midNode.Left = minNode;
        midNode.Right = maxNode;
        // 先刷新两侧收养孩子的节点，最后再刷新父亲节点
        minNode.RefreshHeight();
        maxNode.RefreshHeight();
        midNode.RefreshHeight();
        return midNode;
    }

    // RL旋转可以替换为对minNode的右孩子maxNode执行右旋(RR)，然后再对minNode执行左旋(LL)
    // 本方法不想分两步，直接一步将MidNode"提上来"
    private static Node RL(Node minNode)
    {
        var maxNode = minNode.Right!;
        var midNode = maxNode.Left!;
        // 可能失去孩子的两个节点分给他们可能存在的新孩子
        minNode.Right = midNode.Left;
        maxNode.Left = midNode.Right;
        // 中间节点成为新的父亲
        midNode.Left = minNode;
        midNode.Right = maxNode;
        // 先刷新两侧收养孩子的节点，最后再刷新父亲节点
        minNode.RefreshHeight();
        maxNode.RefreshHeight();
        midNode.RefreshHeight();
        return midNode;
    }

    public void ShowLog()
    {
        StringBuilder sb = new("层序遍历：\n");
        DoShowLog(Root, sb);
        Console.WriteLine(sb);
    }

    private static void DoShowLog(Node? node, StringBuilder sb)
    {
        Queue<Node?> queue = new();
        queue.Enqueue(node);
        int curLayer = 0;
        int totalLayer = node?.Height ?? 0;
        while(queue.Count > 0)
        {
            int count = queue.Count;
            string layerOutput = "";
            ++curLayer;
            bool isFirstSiblingInCurrentLayer = true;
            for (int i=0; i< count; ++i)
            {
                var indent = (int)(Math.Pow(2, (totalLayer - curLayer)));
                if (curLayer > 1 && !isFirstSiblingInCurrentLayer)
                    indent <<= 1;

                var curNode = queue.Dequeue();
                if (curNode != null)
                {
                    layerOutput += Indent(indent - 1) + curNode.Id.ToString().PadLeft(4, ' ');
                    queue.Enqueue(curNode.Left);
                    queue.Enqueue(curNode.Right);
                }
                else if (curLayer <= totalLayer)
                {
                    layerOutput += Indent(indent - 1) + "NULL";
                    if (curLayer < totalLayer)
                    {
                        queue.Enqueue(null);
                        queue.Enqueue(null);
                    }
                }
                isFirstSiblingInCurrentLayer = false;
            }
            sb.AppendLine(layerOutput);
            sb.AppendLine();
        }
    }

    private static string Indent(int n)
    {
        return string.Concat(Enumerable.Repeat("    ", n));
    }
}

参考文献