平衡二叉树

平衡二叉树

平衡二叉树的定义

  • 对于任意一个节点，其左子树和右子树的高度差的绝对值不超过1。
  • 其左子树和右子树都是平衡二叉树。
  • 换句话说，平衡二叉树是一棵高度平衡的二叉搜索树，保证了树的左右子树的高度差不超过1，从而提供了较快的搜索、插入和删除操作的平均时间复杂度。
  • 在平衡二叉树中，每个节点都有一个平衡因子（Balance Factor），它表示该节点的左子树高度减去右子树高度的值。当平衡因子的绝对值超过1时，表示树失去了平衡，需要进行平衡调整操作，以保持树的平衡性。

平衡二叉树的插入

  • 二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入(或删除)一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A再对以N为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。
  • 每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。

调整最小不平衡子树

  • LL –> 在A的左孩子的左子树中插入导致不平衡
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 右旋操作
    AVLNode* rightRotate(AVLNode* A) {
        AVLNode* B = A->left;
        AVLNode* T2 = B->right;

        // 执行旋转
        B->right = A;
        A->left = T2;

        // 更新节点的高度
        A->height = max(getHeight(A->left), getHeight(A->right)) + 1;
        B->height = max(getHeight(B->left), getHeight(B->right)) + 1;

        return B;  // 返回新的根节点
    }
  • RR –> 在A的右孩子的右子树中插入导致不平衡
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 左旋操作
    AVLNode* leftRotate(AVLNode* A) {
        AVLNode* B = A->right;
        AVLNode* T2 = B->left;

        // 执行旋转
        B->left = A;
        A->right = T2;

        // 更新节点的高度
        A->height = max(getHeight(A->left), getHeight(A->right)) + 1;
        B->height = max(getHeight(B->left), getHeight(B->right)) + 1;

        return B;  // 返回新的根节点
    }
  • LR –> 在A的左孩子的右子树中插入导致不平衡


  • RL –> 在A的右孩子的左子树中插入导致不平衡


调整最小不平衡树

查找效率分析

总结

完整代码

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
#include <stdio.h>
#include <stdlib.h>

// 平衡二叉树节点的定义
typedef struct AVLNode {
    int key;
    int height;  // 节点的高度
    struct AVLNode* left;
    struct AVLNode* right;
} AVLNode;

// 获取节点的高度
int getHeight(AVLNode* node) {
    if (node == NULL)
        return 0;
    return node->height;
}

// 获取两个数中的较大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 创建新的节点
AVLNode* createNode(int key) {
    AVLNode* newNode = (AVLNode*)malloc(sizeof(AVLNode));
    newNode->key = key;
    newNode->height = 1;  // 新节点的高度初始化为1
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 右旋操作
AVLNode* rightRotate(AVLNode* A) {
    AVLNode* B = A->left;
    AVLNode* T2 = B->right;

    // 执行旋转
    B->right = A;
    A->left = T2;

    // 更新节点的高度
    A->height = max(getHeight(A->left), getHeight(A->right)) + 1;
    B->height = max(getHeight(B->left), getHeight(B->right)) + 1;

    return B;  // 返回新的根节点
}

// 左旋操作
AVLNode* leftRotate(AVLNode* A) {
    AVLNode* B = A->right;
    AVLNode* T2 = B->left;

    // 执行旋转
    B->left = A;
    A->right = T2;

    // 更新节点的高度
    A->height = max(getHeight(A->left), getHeight(A->right)) + 1;
    B->height = max(getHeight(B->left), getHeight(B->right)) + 1;

    return B;  // 返回新的根节点
}

// 获取节点的平衡因子
int getBalanceFactor(AVLNode* node) {
    if (node == NULL)
        return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// 插入节点到平衡二叉树
AVLNode* insertNode(AVLNode* root, int key) {
    if (root == NULL)
        return createNode(key);

    // 执行二叉搜索树的插入操作
    if (key < root->key)
        root->left = insertNode(root->left, key);
    else if (key > root->key)
        root->right = insertNode(root->right, key);
    else  // 如果遇到相同的节点，则不进行插入
        return root;

    // 更新节点的高度
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));

    // 获取节点的平衡因子
    int balanceFactor = getBalanceFactor(root);

    // 执行平衡调整操作
    // 左左情况，执行右旋
    if (balanceFactor > 1 && key < root->left->key)
        return rightRotate(root);

    // 右右情况，执行左旋
    if (balanceFactor < -1 && key > root->right->key)
        return leftRotate(root);

    // 左右情况，执行左旋后右旋
    if (balanceFactor > 1 && key > root->left->key) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // 右左情况，执行右旋后左旋
    if (balanceFactor < -1 && key < root->right->key) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;  // 返回调整后的根节点
}

// 查找节点在平衡二叉树中
AVLNode* searchNode(AVLNode* root, int key) {
    if (root == NULL || root->key == key)
        return root;

    if (key < root->key)
        return searchNode(root->left, key);
    else
        return searchNode(root->right, key);
}

// 查找最小值节点
AVLNode* findMinNode(AVLNode* root) {
    if (root == NULL)
        return NULL;
    if (root->left == NULL)
        return root;
    return findMinNode(root->left);
}

// 删除节点从平衡二叉树中
AVLNode* deleteNode(AVLNode* root, int key) {
    if (root == NULL)
        return root;

    // 执行二叉搜索树的删除操作
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        // 节点为叶子节点或只有一个子节点的情况
        if (root->left == NULL || root->right == NULL) {
            AVLNode* temp = root->left ? root->left : root->right;

            // 没有子节点的情况
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else  // 只有一个子节点的情况
                *root = *temp;

            free(temp);
        } else {
            // 节点有两个子节点的情况，找到右子树中的最小节点
            AVLNode* minNode = findMinNode(root->right);

            // 用找到的最小节点的值替换要删除的节点的值
            root->key = minNode->key;

            // 递归删除右子树中的最小节点
            root->right = deleteNode(root->right, minNode->key);
        }
    }

    // 如果树只有一个节点或为空，则直接返回
    if (root == NULL)
        return root;

    // 更新节点的高度
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));

    // 获取节点的平衡因子
    int balanceFactor = getBalanceFactor(root);

    // 执行平衡调整操作
    // 左左情况，执行右旋
    if (balanceFactor > 1 && getBalanceFactor(root->left) >= 0)
        return rightRotate(root);

    // 左右情况，执行左旋后右旋
    if (balanceFactor > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // 右右情况，执行左旋
    if (balanceFactor < -1 && getBalanceFactor(root->right) <= 0)
        return leftRotate(root);

    // 右左情况，执行右旋后左旋
    if (balanceFactor < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;  // 返回调整后的根节点
}

// 中序遍历平衡二叉树
void inorderTraversal(AVLNode* root) {
    if (root == NULL)
        return;
    inorderTraversal(root->left);
    printf("%d ", root->key);
    inorderTraversal(root->right);
}

int main() {
    AVLNode* root = NULL;

    // 插入节点
    root = insertNode(root, 9);
    root = insertNode(root, 5);
    root = insertNode(root, 10);
    root = insertNode(root, 3);
    root = insertNode(root, 6);
    root = insertNode(root, 12);

    printf("中序遍历结果：");
    inorderTraversal(root);
    printf("\n");

    // 删除节点
    root = deleteNode(root, 6);
    root = deleteNode(root, 10);

    printf("中序遍历结果：");
    inorderTraversal(root);
    printf("\n");

    return 0;
}
数据结构 > 第七章 > 树形查找
平衡二叉树
https://lzyjx.github.io.git/2023/05/18/平衡二叉树/
作者
六只羊
发布于
2023年5月18日
许可协议