春暖花开

递归实现平衡二叉树的插入、删除、合并和分裂

平衡二叉树

平衡二叉树是这样一棵树,要么是一棵空树,要么是满足下面条件的树:

  • 左子树和右子树的深度的绝对值只差不超过 1;
  • 左子树和右子树也是平衡二叉树。

既是二茬排序树又是平衡二叉树的树为平衡二茬排序树。下面说到的平衡二叉树表示平衡二茬排序树。

在平衡二叉树的结构定义中,比二叉树多了一个平衡因子。实现平衡二叉树的插入和删除是一件比较头疼的事情。因为每次插入或删除之后都要检查平衡是否被破坏,如果被破坏,则要进行各种左旋、右旋的平衡化。

除了插入和删除,有的时候还会涉及到将两个平衡二叉树或多个合并成一个平衡二叉树。或者将一个平衡二叉树分裂为两个平衡二叉树,其中一个中的值均小于等于 $x$,另一个的值均大于 $x$ 。对于合并,最常规的方法自然是,将其中一个二叉树中的点一个个插入到另一个平衡二叉树中。然而,这样做的时间复杂度很大,而且其中一棵二叉树被破坏。但是,如果通过递归来做,则可以在不破坏两棵树的前提下创建一棵新的平衡二叉树,并且时间复杂度比前者要优越很多。

算法

下面说一下该算法:

  1. 分别中序遍历两棵二叉树,得到两个有序序列。
  2. 将两个有序序列合并为一个有序序列。
  3. 利用该有序序列来创建一棵新的平衡二叉树。

递归部分:

终止条件:

  • 序列中只剩下一个或两个记录,一个时,直接建节点,插入记录;两个时,可建节点,将前者插入,然后再后一个作为前者的右孩子插入。

递归:

  • 当序列数大于二时,首先建立节点,将序列最中间的记录插入,然后递归,将中间节点之前的记录作为左孩子插入,中间节点后面的记录作为右孩子插入。

通过该算法构造出的二叉树一定为平衡二茬排序树:

  • 每次递归保证了左边的点小于根节点,右边的点大于根节点,因此为排序树。
  • 递归过程中保证了左右孩子的数目相等或相差一个,这样保证了左右孩子的深度绝对值只差不会超过 1 。

利用这一个思路,也可进行分裂、插入和删除:

  • 分裂:中序遍历平衡二叉树得到序列,定位出 $x$ 的位置,利用递归算法和 $x$ 以及之前的序列可构造出一棵二叉树,之后的序列同样构造出一棵二叉树。
  • 插入:先中序遍历得到序列,将需插入的值插入序列,然后再建树,只是这样相当于重新创建一棵二叉树。
  • 删除:和插入一样。

C 语言实现:

下面是合并和分裂的 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
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
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define MMAX 200
typedef struct BiTreeNode{
int number;
int data;
struct BiTreeNode *lchild;
struct BiTreeNode *rchild;
}BiTreeNode, *BiTree;
void join(BiTree *T, int key[], int first, int last); //use a sorted array key[] to create a balanced tree
void split(BiTree T, BiTree *T1, BiTree *T2, int x); //split a balanced tree into two balanced tree
int inorder(BiTree T, int key[], int *last, int restore); //inorder traverse a balanced tree to get the record list
int preorder(BiTree T); //preorder traverse a tree
int get_index_x(int key[], int last, int x, int *index_x); //get the index of x in array key
void merge_array(int key[], int key1[], int key2[], int len1, int len2, int *last); //merge two sorted array into one sorted array
void merge_tree(BiTree *T, BiTree T1, BiTree T2); //merge two balanced tree into one balanced tree
void merge_tree(BiTree *T, BiTree T1, BiTree T2){
int key[MMAX], key1[MAX], key2[MAX];
int len1, len2, last;
//get lists
inorder(T1, key1, &len1, 0);
inorder(T2, key2, &len2, 0);
//merge lists
merge_array(key, key1, key2, len1, len2, &last);
join(T, key, 0, last); //create tree
}//merge_tree
void merge_array(int key[], int key1[], int key2[], int len1, int len2, int *last){
int i, j, k ;
key[0] = (key1[0] < key2[0])?key1[0]:key2[0];//get the first value
for(i = 0, j = 0, k = 1; i <= len1 && j <= len2; ){ //merge lists
if (key1[i] < key2[j] ){
if (key1[i] != key[k-1])
key[k++] = key1[i++];
else
i ++;
}
else {
if (key2[j] != key[k-1])
key[k++] = key2[j++];
else
j ++;
}
}
if (i <= len1){ //merge remain record of key1[]
while ( i <= len1 ) {
key[k++] = key1[i++];
}
}
else if(j <= len2 ){ //merge remain record of key2[]
while ( j <= len2 ) {
key[k++] = key2[j++];
}
}
else ;
*last = k - 1; //get lenth-1
}//merge_array
void join(BiTree *T, int key[], int first, int last){ //create balanced tree using sorted array
if(first == last){//left one record
*T = (BiTree) malloc (sizeof(BiTreeNode));
(*T)->data = key[first];
(*T)->lchild = (*T)->rchild = NULL;
}
else if(first == last - 1){//left two record
*T = (BiTree) malloc (sizeof(BiTreeNode));
(*T)->data = key[first];
(*T)->rchild = (BiTree) malloc (sizeof(BiTreeNode));
(*T)->rchild->data = key[last];
(*T)->lchild = (*T)->rchild->lchild = (*T)->rchild->rchild = NULL;
}
else{ //insert middle record
int middle = (first + last) / 2;
*T = (BiTree) malloc (sizeof(BiTreeNode));
(*T)->data = key[middle];
//recursive call the join function
join(&((*T)->lchild), key, first, middle - 1);
join(&((*T)->rchild), key, middle + 1, last);
}
} //join
void split(BiTree T, BiTree *T1, BiTree *T2, int x){ //split one balanced tree T into two balanced tree T1 and T2
int key[MAX];
int last, index_x;
inorder(T, key, &last, 0);//get sorted list array
int get_x = get_index_x(key, last, x, &index_x);//get the index of x in array key
if (get_x){
//call join funcion to create balanced tree
join(T1, key, 0, index_x);
join(T2, key, index_x + 1, last);
}
else{ //all record > x or <= x, don't need split;
*T1 = T;
*T2 = NULL;
}
} //split
int get_index_x(int key[], int last, int x, int *index_x){
int i, j;
for ( i = 0; i <= last; i++ ) {
j = i + 1;
if( key[i] <= x && key[j] > x && j <= last ){
*index_x = i;
return 1;
}
}
return 0;
}//get_index
int inorder(BiTree T, int key[], int *last, int restore){
static int i = 0;
if (!restore)
i = 0;//when everytime call the function in main function, restore i to zero
if(!T)
return 1;
else{
if (inorder(T->lchild, key, last, ++ restore)){
key[i++] = T->data;//get array list
if (inorder(T->rchild, key, last, ++ restore)){
*last = i - 1;// get the length-1 of list
return 1;
}
}
return 0;
}
}//inorder
int preorder(BiTree T){
if(!T){
return 1;
}
else{
printf( "%d ", T->data );
if(preorder(T->lchild))
if(preorder(T->rchild))
return 1;
return 0;
}
return 0;
}//preorder
int main( int argc, char **argv ) {
int key[16];
for ( int i = 1; i <= 16; i++ ) {
key[i-1] = 4*i - 3;
}
BiTree T;
join(&T, key, 0, 15);
preorder(T);
printf( "\n\n" );
int num[40];
for ( int i = 0; i < 40; i++ ) {
num[i] = 2*i + 1;
}
BiTree T0, T1, T2;
join(&T0, num, 0, 39);
preorder(T0);
printf( "\n\n" );
int x;
printf( "Input x: " );
scanf("%d", &x);
split(T0, &T1, &T2, x);
preorder(T1);
printf( "\n" );
preorder(T2);
printf( "\n\n" );
int key1[10], key2[20];
for(int i = 0; i < 10; i ++)
key1[i] = 3*i;
for ( int i = 0; i < 20; i++ ) {
key2[i] = 2*i;
}
BiTree t, t1, t2;
join(&t1, key1, 0, 9);
preorder(t1);
printf( "\n" );
join(&t2, key2, 0, 19);
preorder(t2);
printf( "\n\n" );
merge_tree(&t, t1, t2);
preorder(t);
printf( "\n" );
return 0;
}
0%