二叉平衡树——插入操作（C++)

作者：知新_RL | 2024-08-01 14:36:55

踩

二叉平衡树——插入操作（C++)

二叉平衡树

二叉平衡树的前置理论知识，这篇博客已经总结得比较完善了数据结构之——平衡二叉树（内容详解）。在此不做赘述，本文基于C++实现，提供二叉平衡树的构造（插入）代码，基于C++实现。

二叉平衡树的结构定义

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *fa = nullptr; // 存储父节点
    int depth = 1; // 存储深度
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
1
2
3
4
5
6
7
8
9
10

这里设计的结构对比二叉树增加了：

$f a$ 指针：指向当前节点的父节点，设立的原因是实现后文的 $LL$ 等旋转的时候快速获取父节点。
$d e pt h$ ：指的是以当前节点为根节点的子树的高度，设立的原因是为了计算平衡因子=左子树和右子树的高度的差值。

插入代码及解释

int get_depth(TreeNode* root) { return root == nullptr ? 0 : root->depth; }

void update_depth(TreeNode*& root) { root->depth = max(get_depth(root->left), get_depth(root->right)) + 1; }

void insert(TreeNode*& root, int v){
    // 向 root 根插入元素 v
    if (root == nullptr) {
        root = new TreeNode(v);
        return ;
    }
    if (root->left == nullptr && root->right == nullptr) {
        if (root->val == v) return ;
        (root->val <  v ?  root->right : root->left) = new TreeNode(v);
        (root->val <  v ?  root->right : root->left)->fa = root;
        root->depth = 2;
        return ;
    }
    if (root->val < v) {
        insert(root->right, v);
        root->right->fa = root;
    }else if (root->val > v) {
        insert(root->left, v);
        root->left->fa = root;
    }
    // 检查平衡因子
    int left_depth = root->left ? root->left->depth : 0, right_depth = root->right ? root->right->depth : 0;
    if (abs(left_depth - right_depth) > 1) { // 调整树型
        TreeNode* tmpFa = root->fa ? root->fa : new TreeNode(-INT_MAX, root, nullptr);
        bool flag = tmpFa->left == root;
        if (root->left && root->val > v) { // 插入到左子树
            if (v < root->left->val) { // LL 平衡旋转
                TreeNode* B_Node = root->left, *B_Node_r = B_Node->right;
                B_Node->right = B_Node->fa, B_Node->right->fa = B_Node;
                B_Node->right->left = B_Node_r;
                if (B_Node_r) B_Node->right->left->fa = B_Node->right;
                (flag ? tmpFa->left : tmpFa->right) = B_Node;
                update_depth(root), update_depth(B_Node);// 更新高度
            } else { // LR平衡旋转
                TreeNode* B_Node = root->left, *C_Node = B_Node->right;
                TreeNode* C_Node_l = C_Node->left, *C_Node_r = C_Node->right;
                C_Node->left = B_Node, C_Node->left->fa = C_Node;
                C_Node->right = root, C_Node->right->fa = C_Node;
                B_Node->right = C_Node_l;
                if (C_Node_l) B_Node->right->fa = B_Node;
                root->left = C_Node_r;
                if (C_Node_r) root->left->fa = root;
                (flag ? tmpFa->left : tmpFa->right) = C_Node;
                update_depth(root), update_depth(B_Node), update_depth(C_Node);// 更新高度
            }
        } else { // 插入到右子树
            if (v > root->right->val) { // RR 平衡旋转
                TreeNode* B_Node = root->right, *B_Node_l = B_Node->left;
                B_Node->left = B_Node->fa, B_Node->left->fa = B_Node;
                B_Node->left->right = B_Node_l;
                if (B_Node_l) B_Node->left->right->fa = B_Node->left;
                (flag ? tmpFa->left : tmpFa->right) = B_Node;
                update_depth(root), update_depth(B_Node); // 更新高度
            } else { // RL 平衡旋转
                TreeNode* B_Node = root->right, *C_Node = B_Node->left;
                TreeNode* C_Node_l = C_Node->left, *C_Node_r = C_Node->right;
                C_Node->left = root, C_Node->left->fa = C_Node;
                C_Node->right = B_Node, C_Node->right->fa = C_Node;
                B_Node->left = C_Node_r;
                if (C_Node_r) B_Node->left->fa = B_Node;
                root->right = C_Node_l;
                if (C_Node_l) root->right->fa = root;
                (flag ? tmpFa->left : tmpFa->right) = C_Node;
                update_depth(root), update_depth(B_Node), update_depth(C_Node);// 更新高度
            }
        }
        (flag ? tmpFa->left : tmpFa->right)->fa = tmpFa;
        if (tmpFa->val == -INT_MAX) root = (flag ? tmpFa->left : tmpFa->right);
    }
    update_depth(root);
    return ;
}
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

看懂代码的前提还是需要看懂相关的旋转理论，其实本质上代码就是对旋转的过程进行了实现。
需要注意的是：

旋转的过程中，需要及时更新父节点的情况。
旋转的过程中，有的节点的高度是会发生改变的，因而需要及时进行更新。

代码测试

int main(){
    vector<int> nums{15, 3, 7, 10, 9, 8};
    TreeNode* root = nullptr;
    for (int num : nums) {
        insert(root, num);
    }
    cout << "preOrder: ";
    preOrder(root);
    cout << endl;
    cout << "inOrder: ";
    inOrder(root);
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试的结果如下：

preOrder: 9, 7, 3, 8, 10, 15
inOrder: 3, 7, 8, 9, 10, 15
1
2

完整代码：

#include<bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *fa = nullptr; // 存储父节点
    int depth = 1; // 存储深度
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int get_depth(TreeNode* root) { return root == nullptr ? 0 : root->depth; }

void update_depth(TreeNode*& root) { root->depth = max(get_depth(root->left), get_depth(root->right)) + 1; }

void insert(TreeNode*& root, int v){
    // 向 root 根插入元素 v
    if (root == nullptr) {
        root = new TreeNode(v);
        return ;
    }
    if (root->left == nullptr && root->right == nullptr) {
        if (root->val == v) return ;
        (root->val <  v ?  root->right : root->left) = new TreeNode(v);
        (root->val <  v ?  root->right : root->left)->fa = root;
        root->depth = 2;
        return ;
    }
    if (root->val < v) {
        insert(root->right, v);
        root->right->fa = root;
    }else if (root->val > v) {
        insert(root->left, v);
        root->left->fa = root;
    }
    // 检查平衡因子
    int left_depth = root->left ? root->left->depth : 0, right_depth = root->right ? root->right->depth : 0;
    if (abs(left_depth - right_depth) > 1) { // 调整树型
        TreeNode* tmpFa = root->fa ? root->fa : new TreeNode(-INT_MAX, root, nullptr);
        bool flag = tmpFa->left == root;
        if (root->left && root->val > v) { // 插入到左子树
            if (v < root->left->val) { // LL 平衡旋转
                TreeNode* B_Node = root->left, *B_Node_r = B_Node->right;
                B_Node->right = B_Node->fa, B_Node->right->fa = B_Node;
                B_Node->right->left = B_Node_r;
                if (B_Node_r) B_Node->right->left->fa = B_Node->right;
                (flag ? tmpFa->left : tmpFa->right) = B_Node;
                update_depth(root), update_depth(B_Node);// 更新高度
            } else { // LR平衡旋转
                TreeNode* B_Node = root->left, *C_Node = B_Node->right;
                TreeNode* C_Node_l = C_Node->left, *C_Node_r = C_Node->right;
                C_Node->left = B_Node, C_Node->left->fa = C_Node;
                C_Node->right = root, C_Node->right->fa = C_Node;
                B_Node->right = C_Node_l;
                if (C_Node_l) B_Node->right->fa = B_Node;
                root->left = C_Node_r;
                if (C_Node_r) root->left->fa = root;
                (flag ? tmpFa->left : tmpFa->right) = C_Node;
                update_depth(root), update_depth(B_Node), update_depth(C_Node);// 更新高度
            }
        } else { // 插入到右子树
            if (v > root->right->val) { // RR 平衡旋转
                TreeNode* B_Node = root->right, *B_Node_l = B_Node->left;
                B_Node->left = B_Node->fa, B_Node->left->fa = B_Node;
                B_Node->left->right = B_Node_l;
                if (B_Node_l) B_Node->left->right->fa = B_Node->left;
                (flag ? tmpFa->left : tmpFa->right) = B_Node;
                update_depth(root), update_depth(B_Node); // 更新高度
            } else { // RL 平衡旋转
                TreeNode* B_Node = root->right, *C_Node = B_Node->left;
                TreeNode* C_Node_l = C_Node->left, *C_Node_r = C_Node->right;
                C_Node->left = root, C_Node->left->fa = C_Node;
                C_Node->right = B_Node, C_Node->right->fa = C_Node;
                B_Node->left = C_Node_r;
                if (C_Node_r) B_Node->left->fa = B_Node;
                root->right = C_Node_l;
                if (C_Node_l) root->right->fa = root;
                (flag ? tmpFa->left : tmpFa->right) = C_Node;
                update_depth(root), update_depth(B_Node), update_depth(C_Node);// 更新高度
            }
        }
        (flag ? tmpFa->left : tmpFa->right)->fa = tmpFa;
        if (tmpFa->val == -INT_MAX) root = (flag ? tmpFa->left : tmpFa->right);
    }
    update_depth(root);
    return ;
}

void preOrder(TreeNode* root){
    if (root == nullptr) return;
    cout << root->val << ", ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root){
    if (root == nullptr) return;
    inOrder(root->left);
    cout << root->val << ", ";
    inOrder(root->right);
}

int main(){
    vector<int> nums{15, 3, 7, 10, 9, 8};
    TreeNode* root = nullptr;
    for (int num : nums) {
        insert(root, num);
    }
    cout << "preOrder: ";
    preOrder(root);
    cout << endl;
    cout << "inOrder: ";
    inOrder(root);
    cout << endl;
    return 0;
}
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

从以上测试结果来看，代码应当没有很大的问题，可放心食用~
创作不易，欢迎点赞，感谢~~

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/914531