Exercises AVL Tree
AVL 树练习#

An AVL tree is a type of self-balancing binary search tree. The defining characteristic of an AVL tree is its strict balance condition. For every node in the tree, the heights of its left and right subtrees can differ by at most one. This height difference is known as the balance factor.
AVL 树是一种自平衡二叉搜索树。其核心特征是严格平衡条件：对于树中的每个节点，左右子树高度差最多为 1。这个高度差称为平衡因子（balance factor）。

Balance Factor = Height(Left Subtree) - Height(Right Subtree)
平衡因子 = 左子树高度 - 右子树高度

For a tree to be a valid AVL tree, the balance factor of every node must be -1, 0, or 1.
要成为合法 AVL 树，每个节点的平衡因子都必须是 -1、0 或 1。

Balance Factor = 0: The left and right subtrees have the same height.
平衡因子 = 0：左右子树等高。
Balance Factor = 1: The left subtree is one level higher than the right.
平衡因子 = 1：左子树比右子树高一层。
Balance Factor = -1: The right subtree is one level higher than the left.
平衡因子 = -1：右子树比左子树高一层。

If an insertion or deletion operation causes any node’s balance factor to become 2 or -2, the tree is considered unbalanced and must be restructured through a process called rotation to restore the AVL property.
若插入或删除导致某节点平衡因子变为 2 或 -2，则该树视为失衡，必须通过“旋转（rotation）”重构以恢复 AVL 性质。

Download the code provided on the website, organise your folders, and get a project set up as usual. You should now see the following files in the project:
下载网站提供的代码，整理好文件夹，并按常规方式完成项目搭建。此时项目中应包含以下文件：

AVLTree.java – a class representing AVL trees of integers
AVLTree.java - 表示整数 AVL 树的类
Main.java – a class of the main program
Main.java - 主程序类

Exercise 1 – Inserting
练习 1：插入#

Following the logic of building a BST, implement the
按照构建二叉搜索树的逻辑，实现：

insert(Node n, int val)

function, which can build the tree as a regular binary search tree.
该函数用于按普通二叉搜索树方式构建树。

Reference Answer

1
private Node insert(Node n, int val) {
2
    // Standard BST insertion (no balancing here) ---
3
    // If we've reached a null spot, create and return a new node.
4
    if (n == null) {
5
        return new Node(val);
6
    }
7
    // Otherwise, recurse down the tree to find the insertion spot.
8
    if (val < n.data) {
9
        n.left = insert(n.left, val);
10
    } else if (val > n.data) {
11
        n.right = insert(n.right, val);
12
    } else {
13
    // Duplicate value: do nothing (ignore duplicates).
14
    // Could also handle counts or allow duplicates on one side if desired.
15
    }
16
    return n;
17
}

Exercise 2 – Height
练习 2：高度#

Implement the
实现：

height(Node n)

function, that can calculate the height of the tree rooted at the node.
该函数用于计算以该节点为根的子树高度。

Reference Answer

1
private int height(Node n) {
2
    // Return the height of the subtree rooted at n.
3
    // Definition used here: empty tree has height 0, leaf has height 1.
4
    if (n == null) {
5
        return 0;
6
    }
7
    int lh = height(n.left);
8
    int rh = height(n.right);
9
    return Math.max(lh, rh) + 1;
10
}

Exercise 3 – Update the balance factor
练习 3：更新平衡因子#

Implement the
实现：

updateBF(Node n)

function that can update the node’s balance factor.
该函数用于更新节点的平衡因子。

Reference Answer

1
private void updateBF(Node n) {
2
    // Update balance factors for all nodes in the subtree rooted at n.
3
    if (n == null) {
4
        return;
5
    }
6

7
    // Update children first (post-order) so their heights are available.
8
    updateBF(n.left);
9
    updateBF(n.right);
10

11
    int lh = height(n.left);
12
    int rh = height(n.right);
13
    n.bf = lh - rh; // balance factor = height(left) - height(right)
14
}

Exercise 4 – Basic rotation
练习 4：基础旋转#

Inserting a new node into an AVL tree may change the balance of the tree. There are four imbalanced scenarios: LL, RR, LR, and RL cases. To balance the imbalanced tree, there are two basic ways to rebalance the tree that suit different scenarios, which are called left rotation and right rotation.
向 AVL 树插入新节点后，树的平衡可能被破坏。常见四种失衡场景：LL、RR、LR、RL。为恢复平衡，需要根据场景采用两种基本旋转方式：左旋与右旋。

Implement the
实现：

rightRotate (Node n)
leftRotate(Node n)

functions that can rotate the imbalanced tree rooted at the node.
这些函数用于对以该节点为根的失衡子树执行旋转。

Reference Answer

1
private Node rightRotate(Node original) { // Right Rotate for LL case
2
    // original is the root of the unbalanced subtree (y)
3
    // x = original.left will become the new root of this subtree
4
    if (original == null || original.left == null) {
5
        return original;
6
    }
7

8
    Node x = original.left;
9
    Node t2 = x.right;
10

11
    // Perform rotation
12
    x.right = original;
13
    original.left = t2;
14

15
    // Update balance factors for the affected subtree
16
    updateBF(x);
17

18
    return x;
19
}
20

21
private Node leftRotate(Node original) { // Left Rotate for RR case
22
    // original is the root of the unbalanced subtree (x)
23
    // y = original.right will become the new root of this subtree
24
    if (original == null || original.right == null) {
25
        return original;
26
    }
27

28
    Node y = original.right;
29
    Node t2 = y.left;
30

31
    // Perform rotation
32
    y.left = original;
33
    original.right = t2;
34

35
    // Update balance factors for the affected subtree
36
    updateBF(y);
37

38
    return y;
39
}

Exercise 5 – Rebalance
练习 5：重平衡#

Implement the
实现：

rebalance (Node n)

function that can apply two basic rotation functions to rebuild the balance of the tree, depending on 4 different imbalanced scenarios.
该函数可根据 4 种失衡场景，组合使用两种基础旋转来恢复树平衡。

Reference Answer

1
private Node rebalance(Node n) {
2
    if (n == null) {
3
        return null;
4
    }
5

6
    int lh = height(n.left);
7
    int rh = height(n.right);
8
    int bf = lh - rh;
9

10
    // LL Case
11
    if (bf > 1) {
12
    // Determine whether it's LL or LR by comparing heights of left's children
13
        int llh = height(n.left.left);
14
        int lrh = height(n.left.right);
15
        if (llh >= lrh) {
16
            // LL
17
            n = rightRotate(n);
18
        } else {
19
            // LR: left then right
20
            n.left = leftRotate(n.left);
21
            n = rightRotate(n);
22
        }
23
    }
24
    // RR Case
25
    else if (bf < -1) {
26
    // Determine whether it's RR or RL by comparing heights of right's children
27
        int rrh = height(n.right.right);
28
        int rlh = height(n.right.left);
29
        if (rrh >= rlh) {
30
            // RR
31
            n = leftRotate(n);
32
        } else {
33
            // RL: right then left
34
            n.right = rightRotate(n.right);
35
            n = leftRotate(n);
36
        }
37
    }
38

39
    // Ensure balance factors updated for this subtree
40
    updateBF(n);
41
    return n;
42
}

Exercise 6 – Rebalance
练习 6：插入后重平衡#

Modify the insert function to make the tree rebalance when inserting a new node into the tree.
修改 insert 函数，使得插入新节点后树能够自动重平衡。

Update the balance factor of the node when the subtree is changed after inserting a new node.
在插入导致子树变化后，更新该节点平衡因子。
Rebalance the subtree.
对子树执行重平衡。

Reference Answer

1
private Node insert(Node n, int val) {
2
    // Standard BST insertion (no balancing here) ---
3
    // If we've reached a null spot, create and return a new node.
4
    if (n == null) {
5
        return new Node(val);
6
    }
7

8
    // Otherwise, recurse down the tree to find the insertion spot.
9
    if (val < n.data) {
10
        n.left = insert(n.left, val);
11
    } else if (val > n.data) {
12
        n.right = insert(n.right, val);
13
    } else {
14
        // Duplicate value: do nothing (ignore duplicates).
15
        return n;
16
    }
17

18
    // Update this node's balance factor after insertion into a subtree
19
    n.bf = height(n.left) - height(n.right);
20

21
    // Rebalance this subtree if needed and return the (possibly new) root
22
    return rebalance(n);
23
}

Exercise 7 – Execution
练习 7：运行与验证#

Completing the AVLTree class, we can then build an AVL tree in the main program.
完成 AVLTree 类后，就可以在主程序中构建 AVL 树。

Build an integer AVL tree using the data set {10, 20, 30, 40, 50, 25} in sequence.
按顺序使用数据集 {10, 20, 30, 40, 50, 25} 构建整数 AVL 树。
Using the preorder and inOrder functions provided to traverse the tree built, to observe the sequence of nodes and the corresponding balance factor of each node.
使用提供的 preorder 和 inOrder 函数遍历该树，观察节点序列及各节点平衡因子。
Build an integer AVL tree using the data set {10, 20, 30, 40, 50, 25, 35} in sequence.
按顺序使用数据集 {10, 20, 30, 40, 50, 25, 35} 再构建一棵整数 AVL 树。
Using the preorder and inOrder functions provided to traverse the tree built, to observe the sequence of nodes and the corresponding balance factor of each node.
同样使用 preorder 和 inOrder 遍历，观察节点序列及对应平衡因子。
To sketch the two trees out respectively, to compare and check whether the results are good or not.
分别画出两棵树，进行对比并检查结果是否合理。

Reference Answer (Full Version)#

1
public class AVLTree {
2
    private Node root;
3

4
    private static class Node {
5
        int data;
6
        int bf;
7
        Node left;
8
        Node right;
9

10
        Node(int d) {
11
            data = d;
12
            left = null;
13
            right = null;
14
            bf = 0;
15
        }
16
    }
17

18
    public AVLTree() {
19
        root = null;
20
    }
21

22
    public Node getRoot() {
23
        return root;
24
    }
25

26
    private int height(Node n) {
27
        // Return the height of the subtree rooted at n.
28
        // Definition used here: empty tree has height 0, leaf has height 1.
29
        if (n == null) {
30
            return 0;
31
        }
32
        int lh = height(n.left);
33
        int rh = height(n.right);
34
        return Math.max(lh, rh) + 1;
35
    }
36

37
    private void updateBF(Node n) {
38
        // Update balance factors for all nodes in the subtree rooted at n.
39
        if (n == null) {
40
            return;
41
        }
42

43
        // Update children first (post-order) so their heights are available.
44
        updateBF(n.left);
45
        updateBF(n.right);
46

47
        int lh = height(n.left);
48
        int rh = height(n.right);
49
        n.bf = lh - rh; // balance factor = height(left) - height(right)
50
    }
51

52
    // Rotation implements
53
    // Right Rotate for LL case
54
    private Node rightRotate(Node original) {
55
        // original is the root of the unbalanced subtree (y)
56
        // x = original.left will become the new root of this subtree
57
        if (original == null || original.left == null) {
58
            return original;
59
        }
60

61
        Node x = original.left;
62
        Node t2 = x.right;
63

64
        // Perform rotation
65
        x.right = original;
66
        original.left = t2;
67

68
        // Update balance factors for the affected subtree
69
        updateBF(x);
70

71
        return x;
72
    }
73

74
    // Left Rotate for RR case
75
    private Node leftRotate(Node original) {
76
        // original is the root of the unbalanced subtree (x)
77
        // y = original.right will become the new root of this subtree
78
        if (original == null || original.right == null) {
79
            return original;
80
        }
81

82
        Node y = original.right;
83
        Node t2 = y.left;
84

85
        // Perform rotation
86
        y.left = original;
87
        original.right = t2;
88

89
        // Update balance factors for the affected subtree
90
        updateBF(y);
91

92
        return y;
93
    }
94

95
    private Node rebalance(Node n) {
96
        if (n == null) {
97
            return null;
98
        }
99

100
        int lh = height(n.left);
101
        int rh = height(n.right);
102
        int bf = lh - rh;
103

104
        // LL Case
105
        if (bf > 1) {
106
            // Determine whether it's LL or LR by comparing heights of left's children
107
            int llh = height(n.left.left);
108
            int lrh = height(n.left.right);
109
            if (llh >= lrh) {
110
                // LL
111
                n = rightRotate(n);
112
            } else {
113
                // LR: left then right
114
                n.left = leftRotate(n.left);
115
                n = rightRotate(n);
116
            }
117
        }
118
        // RR Case
119
        else if (bf < -1) {
120
            // Determine whether it's RR or RL by comparing heights of right's children
121
            int rrh = height(n.right.right);
122
            int rlh = height(n.right.left);
123
            if (rrh >= rlh) {
124
                // RR
125
                n = leftRotate(n);
126
            } else {
127
                // RL: right then left
128
                n.right = rightRotate(n.right);
129
                n = leftRotate(n);
130
            }
131
        }
132

133
        // Ensure balance factors updated for this subtree
134
        updateBF(n);
135
        return n;
136
    }
137

138
    private Node insert(Node n, int val) {
139

140
        // Standard BST insertion (no balancing here) ---
141
        // If we've reached a null spot, create and return a new node.
142
        if (n == null) {
143
            return new Node(val);
144
        }
145

146
        // Otherwise, recurse down the tree to find the insertion spot.
147
        if (val < n.data) {
148
            n.left = insert(n.left, val);
149
        } else if (val > n.data) {
150
            n.right = insert(n.right, val);
151
        } else {
152
            // Duplicate value: do nothing (ignore duplicates).
153
            return n;
154
        }
155

156
        // Update this node's balance factor after insertion into a subtree
157
        n.bf = height(n.left) - height(n.right);
158

159
        // Rebalance this subtree if needed and return the (possibly new) root
160
        return rebalance(n);
161
    }
162

163
    public void insert(int val) {
164
        root = insert(root, val);
165
    }
166

167
    //pre-order traversal
168
    public void preOrder(Node n) {
169
        if (n != null) {
170
            System.out.println("Node " + n.data + "(bf is " + n.bf + ")");
171
            preOrder(n.left);
172
            preOrder(n.right);
173
        }
174
    }
175

176
    //in-order traversal
177
    public void inOrder(Node n) {
178
        if (n != null) {
179
            inOrder(n.left);
180
            System.out.println("Node " + n.data + "(bf is " + n.bf + ")");
181
            inOrder(n.right);
182
        }
183
    }
184

185
    // Pretty-print the tree structure (rotated, root in the middle)
186
    public void printTree() {
187
        printTree(root, "", true);
188
    }
189

190
    private void printTree(Node node, String prefix, boolean isLeft) {
191
        if (node == null) return;
192

193
        if (node.right != null) {
194
            printTree(node.right, prefix + (isLeft ? "│   " : "    "), false);
195
        }
196

197
        System.out.println(prefix + (isLeft ? "└── " : "┌── ") + node.data + "(bf is " + node.bf + ")");
198

199
        if (node.left != null) {
200
            printTree(node.left, prefix + (isLeft ? "    " : "│   "), true);
201
        }
202
    }
203

204
    // Top-down layout printing (nodes roughly positioned according to inorder index)
205
    public void printTopDown() {
206
        if (root == null) {
207
            System.out.println("<empty>");
208
            return;
209
        }
210

211
        java.util.Map<Node, Integer> pos = new java.util.HashMap<>();
212
        java.util.Map<Node, Integer> depth = new java.util.HashMap<>();
213
        int[] counter = new int[]{0};
214
        int[] maxDepth = new int[]{0};
215

216
        // inorder traversal to assign horizontal positions
217
        assignPos(root, 0, pos, depth, counter, maxDepth);
218

219
        int maxPos = counter[0] - 1;
220

221
        // determine max width of any node's string to handle multi-digit numbers
222
        int maxNumWidth = 0;
223
        java.util.Map<Node, String> strMap = new java.util.HashMap<>();
224
        for (Node n : pos.keySet()) {
225
            String s = String.valueOf(n.data);
226
            strMap.put(n, s);
227
            if (s.length() > maxNumWidth) maxNumWidth = s.length();
228
        }
229

230
        int colWidth = Math.max(3, maxNumWidth + 2); // space per column
231
        int cols = Math.max(1, maxPos + 1) * colWidth + 1;
232

233
        int h = maxDepth[0] + 1;
234
        // precompute horizontal start positions for each node (centered within its column)
235
        java.util.Map<Node, Integer> startPos = new java.util.HashMap<>();
236
        for (java.util.Map.Entry<Node, Integer> e : pos.entrySet()) {
237
            int p = e.getValue();
238
            int base = p * colWidth;
239
            String s = strMap.get(e.getKey());
240
            int start = base + (colWidth - s.length()) / 2;
241
            startPos.put(e.getKey(), start);
242
        }
243

244
        for (int d = 0; d < h; d++) {
245
            char[] line = new char[cols];
246
            java.util.Arrays.fill(line, ' ');
247
            // place node values centered in their columns
248
            for (java.util.Map.Entry<Node, Integer> e : pos.entrySet()) {
249
                Node n = e.getKey();
250
                if (depth.get(n) == d) {
251
                    int p = startPos.get(n);
252
                    String s = strMap.get(n);
253
                    for (int i = 0; i < s.length() && p + i < cols; i++) line[p + i] = s.charAt(i);
254
                }
255
            }
256
            // draw connectors on the same row as parent node using ┌── and ──┐ style
257
            for (java.util.Map.Entry<Node, Integer> e : pos.entrySet()) {
258
                Node n = e.getKey();
259
                if (depth.get(n) == d) {
260
                    int pStart = startPos.get(n);
261
                    String s = strMap.get(n);
262
                    int pCenter = pStart + s.length() / 2;
263

264
                    // place connectors just outside the parent's printed string to avoid overwriting digits
265
                    int pLeft = pStart;
266
                    int pRight = pStart + s.length() - 1;
267

268
                    if (n.left != null) {
269
                        int cStart = startPos.get(n.left);
270
                        String cs = strMap.get(n.left);
271
                        int cCenter = cStart + cs.length() / 2;
272
                        int end = pStart - 1; // stop before parent
273
                        int from = Math.min(cCenter, end);
274
                        int to = Math.max(cCenter, end);
275
                        for (int k = from; k <= to && k >= 0 && k < cols; k++) {
276
                            if (line[k] == ' ') line[k] = '─';
277
                        }
278
                        if (cCenter >= 0 && cCenter < cols) line[cCenter] = '┌';
279
                    }
280

281
                    if (n.right != null) {
282
                        int cStart = startPos.get(n.right);
283
                        String cs = strMap.get(n.right);
284
                        int cCenter = cStart + cs.length() / 2;
285
                        int start = pStart + s.length(); // start after parent
286
                        int from = Math.min(start, cCenter);
287
                        int to = Math.max(start, cCenter);
288
                        for (int k = from; k <= to && k >= 0 && k < cols; k++) {
289
                            if (line[k] == ' ') line[k] = '─';
290
                        }
291
                        if (cCenter >= 0 && cCenter < cols) line[cCenter] = '┐';
292
                    }
293
                }
294
            }
295
            System.out.println(new String(line).replaceAll("\s+$", ""));
296
        }
297
    }
298

299
    private void assignPos(Node n, int d, java.util.Map<Node, Integer> pos, java.util.Map<Node, Integer> depth, int[] counter, int[] maxDepth) {
300
        if (n == null) return;
301
        assignPos(n.left, d + 1, pos, depth, counter, maxDepth);
302
        pos.put(n, counter[0]++);
303
        depth.put(n, d);
304
        if (d > maxDepth[0]) maxDepth[0] = d;
305
        assignPos(n.right, d + 1, pos, depth, counter, maxDepth);
306
    }
307
}

1
public class Main {
2
    public static void main(String[] args) {
3
        AVLTree test = new AVLTree();
4
        test.insert(10);
5
        test.insert(20);
6
        test.insert(30);
7
        test.insert(40);
8
        test.insert(50);
9
        test.insert(25);
10

11
        System.out.println("following is pre-order traversal");
12
        test.preOrder(test.getRoot());
13
        System.out.println("following is in-order traversal");
14
        test.inOrder(test.getRoot());
15

16
    }
17
}

1
public class TestAVL {
2
    public static void main(String[] args) {
3
        // Dataset 1: {10, 20, 30, 40, 50, 25}
4
        AVLTree t1 = new AVLTree();
5
        int[] vals1 = {10, 20, 30, 40, 50, 25};
6
        for (int v : vals1) t1.insert(v);
7
        System.out.println("Dataset 1: {10,20,30,40,50,25}");
8
        System.out.println("In-order:");
9
        t1.inOrder(t1.getRoot());
10
        System.out.println("Pre-order:");
11
        t1.preOrder(t1.getRoot());
12
        System.out.println("Tree structure:");
13
        t1.printTree();
14
        System.out.println("Top-down layout:");
15
        t1.printTopDown();
16

17
        System.out.println();
18
        // Dataset 2: {10, 20, 30, 40, 50, 25, 35}
19
        AVLTree t2 = new AVLTree();
20
        int[] vals2 = {10, 20, 30, 40, 50, 25, 35};
21
        for (int v : vals2) t2.insert(v);
22
        System.out.println("Dataset 2: {10,20,30,40,50,25,35}");
23
        System.out.println("In-order:");
24
        t2.inOrder(t2.getRoot());
25
        System.out.println("Pre-order:");
26
        t2.preOrder(t2.getRoot());
27
        System.out.println("Tree structure:");
28
        t2.printTree();
29
        System.out.println("Top-down layout:");
30
        t2.printTopDown();
31
    }
32
}

音乐

音乐

Exercises AVL Tree
AVL 树练习#

Exercise 1 – Inserting
练习 1：插入#

Exercise 2 – Height
练习 2：高度#

Exercise 3 – Update the balance factor
练习 3：更新平衡因子#

Exercise 4 – Basic rotation
练习 4：基础旋转#

Exercise 5 – Rebalance
练习 5：重平衡#

Exercise 6 – Rebalance
练习 6：插入后重平衡#

Exercise 7 – Execution
练习 7：运行与验证#

Reference Answer (Full Version)#

支持与分享

评论区

音乐

目录

音乐

音乐

Exercises AVL Tree

Exercises AVL Tree AVL 树练习#

Exercise 1 – Inserting 练习 1：插入#

Exercise 2 – Height 练习 2：高度#

Exercise 3 – Update the balance factor 练习 3：更新平衡因子#

Exercise 4 – Basic rotation 练习 4：基础旋转#

Exercise 5 – Rebalance 练习 5：重平衡#

Exercise 6 – Rebalance 练习 6：插入后重平衡#

Exercise 7 – Execution 练习 7：运行与验证#

Reference Answer (Full Version)#

支持与分享

评论区

音乐

目录

Exercises AVL Tree
AVL 树练习#

Exercise 1 – Inserting
练习 1：插入#

Exercise 2 – Height
练习 2：高度#

Exercise 3 – Update the balance factor
练习 3：更新平衡因子#

Exercise 4 – Basic rotation
练习 4：基础旋转#

Exercise 5 – Rebalance
练习 5：重平衡#

Exercise 6 – Rebalance
练习 6：插入后重平衡#

Exercise 7 – Execution
练习 7：运行与验证#