C-数据结构-平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种二叉树，其中任意节点的两棵子树的高度差不超过 1。也可以说是一棵空树或者左右子树高度差不超过 1 的二叉树。

特点和性质

1. 高度平衡：平衡二叉树是一种高度平衡的二叉树，任意节点的左右子树高度差不超过 1。
2. 高度复杂度：由于平衡性质，平衡二叉树的高度复杂度为 O(log n)，其中 n 是树中节点的数量。
3. 插入和删除操作效率高：由于平衡性质，插入和删除操作的平均时间复杂度也是 O(log n)。
4. 查找操作效率高：在平衡二叉树中查找元素的时间复杂度也是 O(log n)。
5. 常见实现：AVL 树和红黑树是常见的平衡二叉树实现。

平衡因子

在平衡二叉树中，每个节点的平衡因子是其左子树高度和右子树高度之差。平衡因子的取值范围通常为 {-1, 0, 1}，表示左右子树的高度差为 -1、0 或 1。

平衡操作

当向平衡二叉树中插入或删除节点时，可能会破坏树的平衡性质，此时需要通过旋转操作来恢复平衡。常见的旋转操作包括左旋和右旋，以及它们的组合操作。

应用

平衡二叉树广泛用于需要高效的插入、删除和查找操作的场景，例如数据库索引、缓存实现等。

‘’’
下面代码实现了二叉树的平衡
以及删除 查找 4种遍历 draw
‘’’

main.c

#include<stdio.h>
#include<stdlib.h>

#include<queue.h>	//已经被封装成动态库

#define NAMESIZE	32

struct score_st
{
	int id;
	char name[NAMESIZE];
	int math;
	int chinese;
};

struct node_st
{
	struct score_st data;
	struct node_st *l,*r;
};

static struct node_st *tree = NULL;//把tree提升到全局变量,当前文件

static void print_s(struct score_st *d)
{
	printf("%d %s %d %d\n",d->id,d->name,d->math,d->chinese);
}


int insert(struct node_st **root,struct score_st *data)
{
	struct node_st *node;
	if(*root == NULL)
	{
		node = malloc(sizeof(*node));
		if(node == NULL)
			return -1;
		node->data = *data;
		node->l = NULL;
		node->r = NULL;
		*root = node;
		return 0;
	}
	if(data->id <= (*root)->data.id)
		return insert(&(*root)->l,data);
	else
		return insert(&(*root)->r,data);
}
struct score_st *find(struct node_st *root,int id)
{
	if(root == NULL)
		return NULL;
	if(id == root->data.id)
		return &root->data;
	if(id < root->data.id)
		return find(root->l,id);
	else
		return find(root->r,id);
}
void draw_(struct node_st *root,int level)
{
	int i;
	if(root == NULL)
		return ;
	draw_(root->r,level+1);
	for(i = 0;i<level;i++)
		printf("    ");
	print_s(&root->data);
	draw_(root->l,level+1);
}
void draw(struct node_st *root)
{
	draw_(root,0);
	printf("\n\n");
	//getchar();//相当于暂停
}

static int get_num(struct node_st *root)
{
	if(root == NULL)
		return 0;
	return get_num(root->l) +1 +get_num(root->r);

}

static struct node_st *find_min(struct node_st *root)
{
	if(root->l == NULL)
		return root;
	return find_min(root->l);
}

static void turn_left(struct node_st **root)
{
	struct node_st *cur = *root;
	*root = cur->r;
	cur->r = NULL;
	
	find_min(*root)->l = cur;
	//draw(tree);//测试语句
}

static struct node_st *find_max(struct node_st *root)
{
	if(root->r == NULL)
		return root;
	return find_max(root->l);
}

static void turn_right(struct node_st **root)
{
	struct node_st *cur = *root;
	*root = cur->l;
	cur->l = NULL;
	
	find_max(*root)->r = cur;
	//draw(tree);//测试语句
}

void balance(struct node_st **root)//函数实现 先把伪代码写出来 ，梳理清楚整个的逻辑关系
{
	int sub;
	if(*root == NULL)
		return ;
	while(1)
	{
		sub = get_num((*root)->l) -get_num((*root)->r);
		if(sub >= -1 && sub <=1)
			break;
		if(sub < -1)
			turn_left(root);
		else
			turn_right(root);
	}
	balance(&(*root)->l);
	balance(&(*root)->r);
}

void detele(struct node_st **root,int id)//删除一个节点 左边顶上来
{
	struct node_st **node = root;
	struct node_st *cur = NULL;
	while(*node != NULL && (*node)->data.id != id)
	{
		if(id < ((*node)->data.id))
			&node = (*node)->l;
		else
			&node = (*node)->r;
	}
	if(*node == NULL)
		return ;
	cur = *node;
	if(cur->l == NULL)
		*node = cur->r;
	else
	{
		*node = cur->l;
		find_max(cur->l)->r = cur->r;
	}
	free(cur);
}

#if 0
void travel(struct node_st *root)//先序遍历 根 左 右  中序遍历 左 根 右 后序遍历 后序遍历 左 右 根
{
	if(root == NULL)
		return ;
	print_s(&root->data);//travel(root->l);  	 //travel(root->l);
	travel(root->l);	//print_s(&root->data);  //travel(root->r);
	travel(root->r);	//travel(root->r);		 //print_s(&root->data)
}
#else

void travel(struct node_st *root)//借助之前封装好的queue库 
{
	int ret;
	QUEUE *qu;
	struct node_st *cur;
	
	qu = queue_create(sizeof(struct node_st *));
	if(qu == NULL)
		return ;
		
	queue_en(qu,&root);
	/*if error*/
	
	while(1)
	{
		ret = queue_de(qu,&cur);
		if(ret == -1)
			break;
		print_s(&cur->data);
		if(cur->l !=NULL)
			queue_en(qu,&cur->l);
		if(cur->r !=NULL)
			queue_en(qu,&cur->r);
	}

	queue_deatroy(qu);
}

#endif

int main()
{
	int arr[] = {1,2,3,7,6,5,9,8,4};
	int i;
	struct score_st tmp,*datap;
	struct node_st *tree = NULL;
	
	for(i = 0;i<sizeof(arr)/sizeof(*arr);i++)
	{
		tmp.id = arr[i];
		snprintf(tmp.name,NAMESIZE,"stu%d",arr[i]);
		tmp.math = rand()%100;
		tmp.chinese = rand()%100;
		
		insert(&tree,&tmp);
	}
	draw(tree);
	balance(&tree);
	draw(tree);
	travel(tree);


#if 0	
	int tmpid = 5;
	delete(&tree,tmpid);
	draw(tree);
#endif


#if 0
//测试语句
	int tmpid = 2;
	datap = find(tree,tmpid);
	if(datap == NULL)
		printf("can not find the id %d\n",tmpid);
	else
		print_s(datap);
#endif
	exit(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
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

gcc main.c -lqueue -lllist -o main
./main
1
2

补充说明

对于 这样的函数参数 struct node_st **root

您的理解基本上是正确的，但是有一个小的修正。让我详细解释一下：

• *root 是指向 struct node_st * 类型的指针。它存储了一个指向 struct node_st 类型的指针的地址。
• 因此，**root 是一个 struct node_st 类型的结构体，因为它解引用了 *root，得到了一个指向 struct node_st 类型的指针，然后再次解引用这个指针，得到了 struct node_st 类型的实际结构体。

因此，root 是一个指向指针的指针，可以用来修改指针指向的内容，从而改变原始指针的值。这在函数中经常用于修改指针的指向，例如在函数中分配内存并将其地址存储在指针中。