如果插入二叉搜索树的元素在插入之前就已经有序，那么插入后的二叉搜索树会退化为链表。在这种情况下，所有操作的时间复杂度将从 \(O(log_2n)\) 劣化为 \(O(n)\) 。因此产生了平衡二叉树，能够实现在插入、删除时保持树的平衡，避免树退化为链表。平衡二叉树全称为：平衡二叉搜索树(Balanced Binary Search Tree).

特点：

  1. 自平衡：在插入或删除节点时，AVL树会通过旋转操作（如左旋、右旋、左右旋、右左旋）来保持树的平衡。

  2. 如果一个树是AVL树，那么它的左右子树都是AVL树。

  3. 树中任意一个节点的平衡因子绝对值不超过1。

    平衡因子：默认每个节点的平衡因子=左子树高度-右子树高度。（或者右子树高度-左子树高度）

实现

基本节点：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct AVLNode {
    int data;
    int height{1}; // 节点高度：表示从当前节点到距离他最远的叶子节点的距离+1（叶子节点高度为1，空节点高度为0）
    AVLNode *left;
    AVLNode *right;
    AVLNode *parent; // 当前节点的双亲节点
    AVLNode(int data) : data(data), left(nullptr), right(nullptr) {}
    AVLNode(int data, AVLNode *left, AVLNode *right, AVLNode *parent) : AVLNode(data) {
        this->parent = parent;
        height = 1;
    };
} Node;

插入

递归插入
逻辑

  • 调用递归函数，传入要插入的树的根节点root和要插入的值data。因为此处AVLNode还用到了parent指针，所以还需要传入parent指针，方便新建节点时指定其parent指针的值。

  • 如果root==nullptr说明是叶子节点。在该位置新建节点。存储要插入的值data,指定height为1(叶子节点高度为1)，同时指定parent指针为传入的parent参数。递归结束。

    因为此处新增了叶子节点，叶子节点高度指定为1，所以可以直接结束递归，不需要更新root(叶子节点)的高度。至于root->parent的高度，会在上层递归中更新。

  • 判断要插入的值data和当前树的根节点root->data的大小关系。

    • data < root->data：递归插入到左子树root->left。插入到root->left后，需要判断root是否失衡。此处因为知晓插入到了root->left子树，所以只存在两种失衡情况：
      • 新增节点插入到了root->left->left子树上，符合LL情况，执行右旋。
      • 新增节点插入到了root->left->right子树上，符合LR情况，执行左右双旋。
    • data > root->data：递归插入到右子树root->right。插入到root->right后，需要判断root是否失衡。此处因为知晓插入到了root->right子树，所以只存在两种失衡情况：
      • 新增节点插入到了root->right->right子树上，符合RR情况，执行左旋。
      • 新增节点插入到了root->right->left子树上，符合RL情况，执行右左双旋。
    • data == root->data：提示要插入的值已经存在。插入失败。

  • 插入并且旋转完成后，更新root节点的高度。（因为新增节点肯定插入了root->left或者root->right子树，可能导致root的高度发生变化）。递归结束。

代码实现
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
// 插入(递归实现)
Node *insert_recursion(Node *root, Node *parent, int data) {
    if (root == nullptr) {
        // 新插入一个节点。新插入的节点一定是叶子节点，所以该节点的高度为1（类内初始化）
        return new Node(data, nullptr, nullptr, parent);
    } else if (root->data > data) {
        root->left = insert_recursion(root->left, root, data);
        // 插入后判断root是否失衡。因为插入的是root->left，所以只需要考虑root左边过高的情况
        if (abs(get_balance(root)) == 2) { // root节点失衡
            if (root->left != nullptr && data < root->left->data) {
                // 执行右单旋操作。
                root = right_rotate(root);
            } else {
                // 执行左右旋操作。
                root = left_right_rotate(root);
            }
        }
    } else if (root->data < data) {
        root->right = insert_recursion(root->right, root, data);
        // 判断root是否失衡
        if (abs(get_balance(root)) == 2) {
            if (root->right != nullptr && data > root->right->data) {
                // 执行左单旋。
                root = left_rotate(root);
            } else {
                // 执行右左旋。
                root = right_left_rotate(root);
            }
        }
    } else {
        printf("ERROR! data already exist.\n");
    }
    // 无论插入情况如何，都要在插入后更新root节点的节点高度
    update_height(root);
    return root;
}
非递归插入

待补充

删除

递归删除
逻辑

  • 调用删除函数。传入根节点指针root和要删除的值data。

  • 如果root==nullptr，说明没有找到data，删除失败。递归结束。

  • 如果root!=nullptr，比较root->data和data的大小关系。

    • root->data == data，找到了要删除的节点。判断节点情况：

      • root是叶子节点：将root节点从树中删除。然后delete root.

      • root只有左子树，没有右子树：

        • 判断root是否是整个AVL树的根节点(root->parent==nullptr)：如果不是，则在执行下面一段。否则跳过下面一段。

          • 判断root是root->parent的左子树还是右子树：
          • 左子树：执行root->parent->left = root->left从树中删除root节点，然后更新root->parent节点的高度。
          • 右子树：执行root->parent->right = root->left从树中删除root节点，然后更新root->parent节点的高度。

        • 更新root->left的父节点指针parent。然后delete root.

          此处删除了root，但对root->left的平衡性没有影响。只是将root->left整体向上提高一层，取代root的位置。（因为root->right==nullptr）.

          反倒是root->parent的平衡性可能受到影响，但是**root->parent的平衡性会在递归返回时被调整**。

      • root只有右子树，没有左子树：

        与上方逻辑类似

      • root的左右子树都存在：

        找到右子树中最小的值，覆盖root->data，然后再将右子树中最小的值(minData)删去：递归调用删除函数，传入root->right和minData。

    • data < root->data：

      • 要删除的data在root的左子树上。递归调用删除函数，传入左子树指针root->left和data。
      • 递归删除完成后，更新root的高度，
      • 然后平衡root节点（因为root的左子树删除了一个节点，高度可能发生变化，可能会影响root所在子树的平衡性）

    • root->data < data，要删除的data在root的右子树上。

      • 递归调用删除函数，传入右子树指针root->right和data。
      • 递归删除完成后，更新root的高度，
      • 然后平衡root节点（因为root的右子树删除了一个节点，高度可能发生变化，可能会影响root所在子树的平衡性）
代码实现
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
// 删除(递归实现)
Node *delete_recursion(Node *root, int data) {
    if (root != nullptr) {
        if (root->data == data) { // 找到要删除的节点
            printf("delete: %d\n", data);
            if (root->right == nullptr && root->left != nullptr) { // root只有左孩子，没有右孩子
                if (root->parent != nullptr) { // 考虑root是否是整个树的根节点
                    if (root->data > root->parent->data) { // root是root->parent的右孩子
                        root->parent->right = root->left;
                    } else { // root是root->parent的左孩子
                        root->parent->left = root->left;
                    }
                    update_height(root->parent); // 因为删除了root节点，所以要更新root->parent节点的高度
                }
                root->left->parent = root->parent; // 更新父节点指针
                // 执行平衡操作? 似乎多余? root->left本来就是平衡的，只是取代了root，对root->left的平衡性没有影响。
                // root->left = balance(root->left);
                Node *temp = root->left;
                delete root;
                root = temp; // root节点从树中删除，root->left取代root
            } else if (root->left == nullptr && root->right != nullptr) { // root只有右孩子，没有左孩子
                if (root->parent != nullptr) {
                    if (root->data > root->parent->data) {
                        root->parent->right = root->right;
                    } else {
                        root->parent->left = root->right;
                    }
                    update_height(root->parent);
                }
                root->right->parent = root->parent;
                // root->right = balance(root->right);
                Node *temp = root->right;
                delete root;
                root = temp;
            } else if (root->left != nullptr && root->right != nullptr) { // 左右孩子都有
                Node *temp = root->right;
                while (temp->left != nullptr) { // 找到root的右子树中的最小节点
                    temp = temp->left;
                }
                int val = temp->data;
                root->right = delete_recursion(root->right, val);
                root->data = val;
                update_height(root); // root的右子树发生了变动，更新root的高度
                root = balance(root);
            } else { // root是叶子节点
                if (root->parent != nullptr) { // root存在父节点
                    if (root->parent->data < root->data) { // root是其父亲节点的右孩子
                        root->parent->right = nullptr; // 删去root节点
                    } else { // root是其父亲节点的左孩子
                        root->parent->left = nullptr;
                    }
                    update_height(root->parent);
                }
                delete root;
                root = nullptr;
            }

        } else if (data < root->data) {
            root->left = delete_recursion(root->left, data);
            update_height(root);
            root = balance(root);
        } else {
            root->right = delete_recursion(root->right, data);
            update_height(root);
            root = balance(root);
        }
    } else {
        printf("Key to be deleted could not be found.\n");
    }

    return root;
}

// 平衡root节点
Node *balance(Node *root) {
    int balance_factor = get_balance(root);
    if (abs(balance_factor) == 2) {
        if (balance_factor < 0) { // root节点的右子树高度 > 左子树高度
            if (get_balance(root->right) == 1) { // root->right的左子树高度 > 右子树高度，root节点符合RL失衡，执行左右双旋
                root = right_left_rotate(root);
            } else { // root->right的右子树高度 > 左子树高度，root节点符合RR失衡，执行左单旋
                root = left_rotate(root);
            }
        } else { // root节点的右子树高度 < 左子树高度
            if (get_balance(root->left) == 1) { // root->left的左子树高度 > 右子树高度，root节点符合LL失衡，执行右单旋
                root = right_rotate(root);
            } else { // root->right的右子树高度 > 左子树高度，root节点符合LR失衡，执行右左双旋
                root = left_right_rotate(root);
            }
        }
    }
    return root;
}
非递归删除

待补充

查询

递归查询
逻辑
  • 调用递归查询函数，传入树的根节点root和要查询的值data。
  • 如果root==nullptr，说明递归到了叶子节点下的空节点，或者整个树为空，即：没有找到目标值。返回false，递归结束。
    • 如果root->data==data，找到目标值，返回true，递归结束。
    • 如果root->data > data，递归左子树。返回左子树的递归结果。
    • 如果root->data < data，递归右子树。返回右子树的递归结果。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
// 查询(递归实现)
bool search(const Node *root, const int &data) {
    if (root == nullptr) {
        return false;
    }
    if (root->data == data) {
        return true;
    } else if (data < root->data) {
        return search(root->left, data);
    } else {
        return search(root->right, data);
    }
}
非递归查询

待补充

核心算法：旋转操作

左旋

左旋

C++实现：

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
/**
 * @brief root节点失衡，对root和root->right进行左旋操作。
 * @param root 失衡节点
 */
Node *left_rotate(Node *root) {
    Node *childR = root->right;
    Node *childRL = childR->left;

    root->right = childRL;
    childR->left = root;

    if (childRL != nullptr) {
        childRL->parent = root;
    }
    childR->parent = root->parent;
    root->parent = childR;
    if (childR->parent != nullptr) {
        if (childR->data < childR->parent->data) {
            childR->parent->left = childR;
        } else {
            childR->parent->right = childR;
        }
    }

    root = childR;
    update_height(root->left);
    update_height(root->right);
    update_height(root);
    update_height(root->parent);

    return root;
}
右旋

右旋

C++实现：

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
/**
 * @brief root节点失衡，对root和root->left执行右旋操作。
 * @param root 失衡节点
 */
Node *right_rotate(Node *root) {
    Node *childL = root->left;
    Node *childLR = childL->right;

    /**
     * 如果只使用了height属性，没有使用parent属性，则只需要 下面两行语句 和 root=Lchild 以及 四个update_height()即可完成旋转。
     * 如果使用了parent则需要加入剩余的代码。
     */
    root->left = childLR;
    childL->right = root;

    if (childLR != nullptr) {
        // 说明原root->left->right非空，需要更新它的父节点指针。
        childLR->parent = root;
    }
    childL->parent = root->parent;
    root->parent = childL;
    if (childL->parent != nullptr) {
        if (root->data < childL->parent->data) {
            // 原root节点挂载在root->parent的左边，旋转后将新树也挂载在左边
            childL->parent->left = childL;
        } else {
            // 否则挂载到右边
            childL->parent->right = childL;
        }
    }

    root = childL;
    update_height(root->left);
    update_height(root->right);
    update_height(root);
    update_height(root->parent); // 注意此处需要更新root->parent的高度，因为root->parent的其中一个子树(也就是root)高度改变，所以会影响root->parent的高度

    return root;
}
左右双旋

先左旋，再右旋

左右双旋

C++实现：

1
2
3
4
5
6
7
8
9
/**
 * @brief 左右旋
 */
Node *left_right_rotate(Node *root) {
    // 先对root->left和root->left->right进行左单旋
    root->left = left_rotate(root->left);
    // 在对root和root->left进行右单旋
    return right_rotate(root);
}
右左双旋

先右旋，再左旋

右左双旋

C++实现：

1
2
3
4
5
6
7
8
9
/**
 * @brief 右左旋
 */
Node *right_left_rotate(Node *root) {
    // 先对root->right和root->right->left进行右单旋
    root->right = right_rotate(root->right);
    // 再对root和root->right进行左单旋
    return left_rotate(root);
}

完整代码实现：

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
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
#include <iostream>
#include <queue>
#include <iomanip>
#include <cstring>
using namespace std;

class AVLTree {
public:
    typedef struct AVLNode {
        int data;
        int height{1}; // 节点高度：表示从当前节点到距离他最远的叶子节点的距离+1（叶子节点高度为1，空节点高度为0）
        AVLNode *left;
        AVLNode *right;
        AVLNode *parent; // 当前节点的双亲节点
        AVLNode(int data) : data(data), left(nullptr), right(nullptr) {}
        AVLNode(int data, AVLNode *left, AVLNode *right, AVLNode *parent) : AVLNode(data) {
            this->parent = parent;
            height = 1;
        };
    } Node;

    AVLTree() : root(nullptr) {}

    AVLTree(int data) {
        root = new Node(data);
    }

    ~AVLTree() {
        delete_tree(root);
    }

    void insert_node(int data) {
        root = insert_recursion(root, nullptr, data); // 直接调用递归函数进行插入

        /**
         * 待补充: 非递归的插入方法
         */
    }

    void delete_node(int data) {
        root = delete_recursion(root, data); // 调用递归的删除方法

        /**
         * 待补充: 非递归的删除方法
         */
    }

    bool search(int data) {
        return search(root, data); // 调用递归的查询方法

        /**
         * 待补充: 非递归的查询方法
         */
    }

    Node *get_root() {
        return this->root;
    }

private:
    Node *root;

    // 插入(递归实现)
    Node *insert_recursion(Node *root, Node *parent, int data) {
        if (root == nullptr) {
            // 新插入一个节点。新插入的节点一定是叶子节点，所以该节点的高度为1（类内初始化）
            return new Node(data, nullptr, nullptr, parent);
        } else if (root->data > data) {
            root->left = insert_recursion(root->left, root, data);
            // 插入后判断root是否失衡。因为插入的是root->left，所以只需要考虑root左边过高的情况
            if (abs(get_balance(root)) == 2) { // root节点失衡
                if (root->left != nullptr && data < root->left->data) {
                    // 执行右单旋操作。
                    root = right_rotate(root);
                } else {
                    // 执行左右旋操作。
                    root = left_right_rotate(root);
                }
            }
        } else if (root->data < data) {
            root->right = insert_recursion(root->right, root, data);
            // 判断root是否失衡
            if (abs(get_balance(root)) == 2) {
                if (root->right != nullptr && data > root->right->data) {
                    // 执行左单旋。
                    root = left_rotate(root);
                } else {
                    // 执行右左旋。
                    root = right_left_rotate(root);
                }
            }
        } else {
            printf("ERROR! data already exist.\n");
        }
        // 无论插入情况如何，都要在插入后更新root节点的节点高度
        update_height(root);
        return root;
    }

    // 删除(递归实现)
    Node *delete_recursion(Node *root, int data) {
        if (root != nullptr) {
            if (root->data == data) { // 找到要删除的节点
                printf("delete: %d\n", data);
                if (root->right == nullptr && root->left != nullptr) { // root只有左孩子，没有右孩子
                    if (root->parent != nullptr) { // 考虑root是否是整个树的根节点
                        if (root->data > root->parent->data) { // root是root->parent的右孩子
                            root->parent->right = root->left;
                        } else { // root是root->parent的左孩子
                            root->parent->left = root->left;
                        }
                        update_height(root->parent); // 因为删除了root节点，所以要更新root->parent节点的高度
                    }
                    root->left->parent = root->parent; // 更新父节点指针
                    // 执行平衡操作? 似乎多余? root->left本来就是平衡的，只是取代了root，对root->left的平衡性没有影响。
                    // root->left = balance(root->left);
                    Node *temp = root->left;
                    delete root;
                    root = temp; // root节点从树中删除，root->left取代root
                } else if (root->left == nullptr && root->right != nullptr) { // root只有右孩子，没有左孩子
                    if (root->parent != nullptr) {
                        if (root->data > root->parent->data) {
                            root->parent->right = root->right;
                        } else {
                            root->parent->left = root->right;
                        }
                        update_height(root->parent);
                    }
                    root->right->parent = root->parent;
                    // root->right = balance(root->right);
                    Node *temp = root->right;
                    delete root;
                    root = temp;
                } else if (root->left != nullptr && root->right != nullptr) { // 左右孩子都有
                    Node *temp = root->right;
                    while (temp->left != nullptr) { // 找到root的右子树中的最小节点
                        temp = temp->left;
                    }
                    int val = temp->data;
                    root->right = delete_recursion(root->right, val);
                    root->data = val;
                    update_height(root); // root的右子树发生了变动，更新root的高度
                    root = balance(root);
                } else { // root是叶子节点
                    if (root->parent != nullptr) { // root存在父节点
                        if (root->parent->data < root->data) { // root是其父亲节点的右孩子
                            root->parent->right = nullptr; // 删去root节点
                        } else { // root是其父亲节点的左孩子
                            root->parent->left = nullptr;
                        }
                        update_height(root->parent);
                    }
                    delete root;
                    root = nullptr;
                }

            } else if (data < root->data) {
                root->left = delete_recursion(root->left, data);
                update_height(root);
                root = balance(root);
            } else {
                root->right = delete_recursion(root->right, data);
                update_height(root);
                root = balance(root);
            }
        } else {
            printf("Key to be deleted could not be found.\n");
        }

        return root;
    }

    // 查询(递归实现)
    bool search(const Node *root, const int &data) {
        if (root == nullptr) {
            return false;
        }
        if (root->data == data) {
            return true;
        } else if (data < root->data) {
            return search(root->left, data);
        } else {
            return search(root->right, data);
        }
    }

    // 获取节点高度
    int node_height(Node *node) {
        if (node == nullptr) {
            return 0;
        }
        return node->height;
    }

    // 更新节点高度
    void update_height(Node *root) {
        if (root != nullptr) {
            // update height
            root->height = std::max(node_height(root->left), node_height(root->right)) + 1;
        }
    }

    /**
     * @brief 获取node节点的平衡因子。
     * @param node 要获取平衡因子的节点
     * @return  - 如果node是非叶子节点，平衡因子 = 左子树高度 - 右子树高度;
     *
     *          - 如果node是叶子节点，平衡因子 = 1
     *
     *          - 如果node是空节点，平衡因子 = 0
     */
    int get_balance(Node *node) {
        if (node == nullptr) {
            return 0;
        }
        return node_height(node->left) - node_height(node->right);
    }

    /**
     * @brief root节点失衡，对root和root->left执行右旋操作。
     * @param root 失衡节点
     */
    Node *right_rotate(Node *root) {
        Node *childL = root->left;
        Node *childLR = childL->right;

        /**
         * 如果只使用了height属性，没有使用parent属性，则只需要 下面两行语句 和 root=Lchild 以及 四个update_height()即可完成旋转。
         * 如果使用了parent则需要加入剩余的代码。
         */
        root->left = childLR;
        childL->right = root;

        if (childLR != nullptr) {
            // 说明原root->left->right非空，需要更新它的父节点指针。
            childLR->parent = root;
        }
        childL->parent = root->parent;
        root->parent = childL;
        if (childL->parent != nullptr) {
            if (root->data < childL->parent->data) {
                // 原root节点挂载在root->parent的左边，旋转后将新树也挂载在左边
                childL->parent->left = childL;
            } else {
                // 否则挂载到右边
                childL->parent->right = childL;
            }
        }

        root = childL;
        update_height(root->left);
        update_height(root->right);
        update_height(root);
        update_height(root->parent); // 注意此处需要更新root->parent的高度，因为root->parent的其中一个子树(也就是root)高度改变，所以会影响root->parent的高度

        return root;
    }

    /**
     * @brief root节点失衡，对root和root->right进行左旋操作。
     * @param root 失衡节点
     */
    Node *left_rotate(Node *root) {
        Node *childR = root->right;
        Node *childRL = childR->left;

        root->right = childRL;
        childR->left = root;

        if (childRL != nullptr) {
            childRL->parent = root;
        }
        childR->parent = root->parent;
        root->parent = childR;
        if (childR->parent != nullptr) {
            if (childR->data < childR->parent->data) {
                childR->parent->left = childR;
            } else {
                childR->parent->right = childR;
            }
        }

        root = childR;
        update_height(root->left);
        update_height(root->right);
        update_height(root);
        update_height(root->parent);

        return root;
    }

    /**
     * @brief 左右旋
     */
    Node *left_right_rotate(Node *root) {
        // 先对root->left和root->left->right进行左单旋
        root->left = left_rotate(root->left);
        // 在对root和root->left进行右单旋
        return right_rotate(root);
    }

    /**
     * @brief 右左旋
     */
    Node *right_left_rotate(Node *root) {
        // 先对root->right和root->right->left进行右单旋
        root->right = right_rotate(root->right);
        // 再对root和root->right进行左单旋
        return left_rotate(root);
    }

    // 平衡root节点
    Node *balance(Node *root) {
        int balance_factor = get_balance(root);
        if (abs(balance_factor) == 2) {
            if (balance_factor < 0) { // root节点的右子树高度 > 左子树高度
                if (get_balance(root->right) == 1) { // root->right的左子树高度 > 右子树高度，root节点符合RL失衡，执行左右双旋
                    root = right_left_rotate(root);
                } else { // root->right的右子树高度 > 左子树高度，root节点符合RR失衡，执行左单旋
                    root = left_rotate(root);
                }
            } else { // root节点的右子树高度 < 左子树高度
                if (get_balance(root->left) == 1) { // root->left的左子树高度 > 右子树高度，root节点符合LL失衡，执行右单旋
                    root = right_rotate(root);
                } else { // root->right的右子树高度 > 左子树高度，root节点符合LR失衡，执行右左双旋
                    root = left_right_rotate(root);
                }
            }
        }
        return root;
    }

    void delete_tree(AVLTree::Node *root) {
        if (root == nullptr) {
            return;
        }
        delete_tree(root->left);
        delete_tree(root->right);
        printf("released node: %d\n", root->data);
        delete root;
    }
};

void printInOrder(AVLTree::Node *root) {
    if (root == nullptr) {
        return;
    }
    printInOrder(root->left);
    printf("%d ", root->data);
    printInOrder(root->right);
}

int main() {
    AVLTree avl;

    int *arr = new int[12]{10, 20, 45, 30, 12, 40, 50, 25, 14, 52, 75, 19};

    for (int i = 0; i < 12; ++i) {
        avl.insert_node(arr[i]);
    }

    for (int i = 0; i < 12; ++i) {
        if (avl.search(arr[i])) {
            printf("find: %d\n", arr[i]);
            avl.delete_node(arr[i]);
        }
    }

    delete[] arr;

    return 0;
}