3.2 平衡二叉树
3.2.1 定义
-
平衡二叉树，简称平衡树（AVL树）
树上任一结点的左右子树高度差不超过1。
结点的平衡因子=左子树高-右子树高
3.2.2 插入操作
-
插入结点后，可能造成不平衡
要调整最小不平衡子树，使其恢复平衡。
调整最小不平衡树A的方法：
1.LL：在A的左孩子的左子树中插入导致不平衡；
2.RR：在A的右孩子的右子树中插入导致不平衡；
3.LR：在A的左孩子的右子树中插入导致不平衡；
4.RL：在A的右孩子的左子树中插入导致不平衡。
A.调整最小不平衡子树 LL
-
LL插入后：
由于在结点A的左孩子（L）的左子树（L）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。
-
平衡旋转的目标：
1.恢复平衡；
2.保持二叉排序树特性：
左子树结点值<根结点值<右子树结点值
BL<B<HR<A<AR
-
LL平衡旋转（右单旋转）：
1.将A的左孩子B向右上旋转代替A成为根结点；
2.将A结点向右下旋转成为B的右子树的根结点；
3.而B的原右子树作为A结点的左子树。
-
右旋代码思路
实现f向右下旋转，p向右上旋转：
其中，gf是f他爹。
1.
f->lchild=p->rchild;2.
p->rchild=f;3.
gf->lchild/rchild=p;
B.调整最小不平衡子树 RR
-
RR插入后：
由于在结点A的右孩子（R）的右子树（R）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。
-
RR平衡旋转（左单旋转）步骤：
1.将A的右孩子B向左上旋转代替A成为根结点；
2.将A结点向左下旋转成为B的左子树的根结点；
3.将B的原左子树作为A结点的右子树。
-
左旋代码思路
实现f向左下旋转，p向左上旋转：
其中gf是f他爹。
1.
f->rchild=p->lchild;2.
p->lchild=f;3.
gf->lchild/rchild=p;
C.调整最小不平衡子树 LR
-
LR插入后：
由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋再右旋。
-
LR平衡旋转（先左后右双旋转）步骤：
1.左旋：先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置；
2.右旋：将C结点向右上旋转提升到A结点的位置。
D.调整最小不平衡树 RL
-
RL插入后
由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋后左旋转。
-
RL平衡旋转（先右后左双旋转）步骤：
1.右旋：将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置；
2.左旋：将C结点向左上旋转提升到A结点的位置。
-
旋转练习
1.将新结点插入到相应位置；
2.找到最近的不平衡结点；
3.根据插入结点的位置旋转。
3.2.3 查找操作
-
效率分析
若树高为h，最坏情况下一个关键字对比h次，所以查找的时间复杂度不可能超过 O ( h ) O(h) O(h)。
-
最少结点数
假设以 n h n_h nh表示深度为h的平衡树中含有的最少结点数，
则有 n 0 = 0 , n 1 = 1 , n 2 = 2 n_0=0,n_1=1,n_2=2 n0=0,n1=1,n2=2
n h = n h − 1 + n h − 2 + 1 n_h=n_{h-1}+n_{h-2}+1 nh=nh−1+nh−2+1
- 应用：对有9个结点的平衡二叉树，树高最大为4。（因为 n 4 = 7 , n 5 = 12 , 而 n 4 < 9 < n 5 n_4=7,n_5=12,而n_4<9<n_5 n4=7,n5=12,而n4<9<n5）
-
含有n个结点的平衡二叉树
最大深度： O ( l o g 2 n ) O(log_2n) O(log2n)
平均查找长度： O ( l o g 2 n ) O(log_2n) O(log2n)
3.2.4 删除操作
-
删除和插入操作相同，也要保持二叉排序树的特性不变。
-
删除操作的步骤
1.删除结点（方法同二叉排序树）；
若删除结点是叶子结点，直接删。
若删除结点只有一个子树，用子树顶替删除位置。
若删除结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除。
2.一路向上找到最小不平衡子树；
3.找到最小不平衡子树下，个头最高的儿子和孙子；
如这里最高的儿子是80，最高的孙子是90：
4.根据孙子的位置，调整平衡（LL/RR/LR/RL）；
孙子在LL：儿子右单旋
孙子在RR：儿子左单旋
孙子在LR：孙子先左旋，再右旋
孙子在RL：孙子先右旋，再左旋
5.如果不平衡向上传导，继续第二步。
对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）
如：
*完整代码 平衡二叉树
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node* left;
struct Node* right;
int height;
} Node;
// 计算节点的高度
int height(Node* node) {
if (node == NULL)
return 0;
return node->height;
}
// 返回两个整数中较大的一个
int max(int a, int b) {
return (a > b) ? a : b;
}
// 创建一个新节点
Node* newNode(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
// 右旋转子树
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
// 左旋转子树
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
// 获取节点的平衡因子
int getBalance(Node* node) {
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
// 插入节点
Node* insert(Node* node, int key) {
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // 如果键值已经存在，则不插入
return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// 如果节点不平衡，根据不同情况进行旋转
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 查找最小值节点
Node* minValueNode(Node* node) {
Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
// 删除节点
Node* deleteNode(Node* 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)) {
Node* temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->left), height(root->right));
int balance = getBalance(root);
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// 查找节点
Node* search(Node* root, int key) {
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
// 中序遍历二叉树
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
// 主函数
int main() {
Node* root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("Inorder traversal of the constructed AVL tree:\n");
inorder(root);
printf("\n");
Node* foundNode = search(root, 30);
if (foundNode != NULL)
printf("Node with key 30 found!\n");
else
printf("Node with key 30 not found.\n");
root = deleteNode(root, 30);
printf("Inorder traversal after deletion of 30:\n");
inorder(root);
printf("\n");
foundNode = search(root, 30);
if (foundNode != NULL)
printf("Node with key 30 found!\n");
else
printf("Node with key 30 not found.\n");
return 0;
}
![YOLOv8_seg训练流程-原理解析[实例分割理论篇]](https://img-blog.csdnimg.cn/direct/190c9b22014c4bf79297b32a327507b0.png)
