AVL平衡二叉树的插入与删除
程序员文章站
2022-06-07 08:22:14
...
什么是平衡二叉树
首先我们需要知道什么是平衡二叉树：
平衡二叉树又称为AVL树，它具有以下的性质：
1.它是一颗空树或它的左右两个子树的高度差绝对值不超过1；
2.左右子数都是一颗平衡二叉树；
我们今天的增加与删除是在二叉搜索树的情况下进行
那么什么是二叉搜索树呢？
若二叉搜索树的左子树不空，则左子树上的所有节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右两边也为二
叉搜索树。
旋转
在遇到平衡二叉树的增加与删除时，如果插入与删除后破坏了二叉树的平衡性，
则需要进行旋转。
下面我们分别讨论旋转的四种情况：
1.左旋（ll_rotation)
相关代码
60 static AVLNode* ll_rotation(AVLTree k2){
61 AVLNode *k1=k2->left;
62 k2->left=k1->right;
63 k1->right=k2;
64
65 return k1;
66 }
k2为根节点2.右旋（rr_rotation)
相关代码:
70 static AVLNode* rr_rotation(AVLTree k1){
71 AVLNode *k2=k1->right;
72 k1->right = k2->left;
73 k2->left = k1;
74
75 return k2;
76 }
k1为根节点3.先右旋在左旋（lr_rotation)
相关代码：
79 static AVLNode* lr_rotation(AVLTree k3){
80 k3->left = rr_rotation(k3->left);
81 return ll_rotation(k3);
82 }
k3为根节点
4.先左旋再右旋（rl_rotation)
相关代码
84 static AVLNode* rl_rotation(AVLTree k1){
85 k1->right = ll_rotation(k1->right);
86 return rr_rotation(k1);
87 }
平衡二叉树插入
52 static AVLNode* create_avlnode(int key){
53 AVLNode *node = malloc(sizeof(AVLNode));
54 node->key=key;
55 node->left=NULL;
56 node->right = NULL;
57 node->height = 1;
58 return node;
59 }//创建新的节点
89 int avltree_insert(AVLTree *ptree,int key){
90 if(*ptree == NULL){
91 *ptree = create_avlnode(key);
92 return 0;//创建成功
93 }
94 int ret = 0;
95 if(key<(*ptree)->key){//左插，ll 或 lr旋转
96 ret = avltree_insert(&(*ptree)->left,key);//判断插入的成功与失败
97 if(ret == 0){//只有插成功
98 if(HEIGHT((*ptree)->left)-HEIGHT((*ptree)->right) == 2){//在左边插入时失衡，一定是左子树的高度减去右子树的高度
等于2时才是失衡，如果没有等于二就不用进行后面的操作
99 int lh = HEIGHT((*ptree)->left->left);//删除节点左子树的左侧高度
100 int rh = HEIGHT((*ptree)->left->right);//删除节点左子树的右侧高度
101 if(lh>rh){//左子树的左侧高则大于右侧高度则ll旋转，否则lr旋转
102 *ptree = ll_rotation(*ptree);
103 }else{
104 *ptree = lr_rotation(*ptree);
105 }
106 }//其他情况下说明<=1，不用做调整，还是平衡
107 (*ptree)->height = MAX(HEIGHT((*ptree)->left),HEIGHT((*ptree)->right)) +1;//更新插入后的高度，加的一为自己
本身的高度为1
108 }
109 return ret; //递归时返回成功还是失败
110 }else if(key>(*ptree)->key){//删除的值在右子树的情况，与上面同理
111 ret = avltree_insert(&(*ptree)->right,key);
112 if(ret == 0){
113 if(HEIGHT((*ptree)->right)-HEIGHT((*ptree)->left) == 2){
114 int lh = HEIGHT((*ptree)->right->left);
115 int rh = HEIGHT((*ptree)->right->right);
116 if(rh>lh){
117 *ptree = rr_rotation(*ptree);
118 }else{
119 *ptree = rl_rotation(*ptree);
120 }
121 }
122 (*ptree)->height = MAX(HEIGHT((*ptree)->left),HEIGHT((*ptree)->right))+1;
123 }
124 return ret;
125 }else{//有相同的元素
126 return -1;
127 }
128 }
平衡二叉树删除
177 int avltree_delete(AVLTree *ptree,int key){
178 if(*ptree == NULL){ //如果要删除的节点不存在，就返回-1
179 return -1;
180 }
181 int ret = 0;
182 if((*ptree)->key == key){ //如果找到了要删除的节点
183 AVLNode *node = *ptree; //记录要删除的节点*ptree
184 if(node->right && node->left){ //如果要被删除的节点的左右节点都存在
185 int hl = HEIGHT(node->left); //被删除节点左儿子的高度
186 int hr = HEIGHT(node->right); //被删除节点的右儿子的高度
187 if(hl > hr){//左边高，左边的最大值放到node里面,把最大值的节点删除
188 AVLNode* max = node->left; //用来储存左儿子的最右的节点
189 while(max->right){ //找到最右的节点
190 max = max->right;
191 }
192 node->key = max->key; //把这个最大值节点覆盖要被删除的节点
193 ret = avltree_delete(&(node->left),max->key); //删除左儿子这个树
里的最大值
194 (*ptree)->height = MAX(HEIGHT((*ptree)->left),HEIGHT((*ptree)->rig ht)) + 1; //更新该被
删除（其实删除的不是他，是左儿子的最大值的几诶单）的节点的高度
195 }else{ //右边高 右边的最小值放到node里面,然后把这个最小值删除
196 AVLNode *min = node->right; //记录右儿子的最左节点
197 while(min->left){ //找到右儿子的最左节点
198 min = min->left;
199 }
200 node->key = min->key; //用这个最左节点覆盖要被删除的节点
201 ret = avltree_delete(&(node->right),min->key); //删除右儿子这个树
里的最小值
202 (*ptree)->height = MAX(HEIGHT((*ptree)->left),HEIGHT((*ptree)->rig ht)) + 1;//更新这个
(要被删除)(其实删除的不是他，是右儿子的最小值)的节点的高度
203 }
204 }else if(!node->right && !node->left){ //如果要被删除的节点的左右儿子都不
存在,那么直接删除该节点
205 free(*ptree);
206 *ptree = NULL;
207 }else{ //如果要被删除的节点的左右儿子只存在其中一个 直接把左儿子或者右儿
子提上来，并且释放掉此节点
208 AVLNode *node = *ptree;
209 *ptree = (*ptree)->left!=NULL?(*ptree)->left:(*ptree)->right;
210 free(node);
211 }
212 return 0;
213 }else if(key < (*ptree)->key){ //如果要被删除的节点在左边
214 ret = avltree_delete(&(*ptree)->left,key); //那就去左边删除此节点
215 if(ret == 0){ //如果删除成功 那就判断此树是否还平衡 左边被删除掉一个结
点，肯定是右边变高
216 if(HEIGHT((*ptree)->right)-HEIGHT((*ptree)->left) == 2){ //如果不平
衡则需要rr旋转或者rl旋转
217 int hl = HEIGHT((*ptree)->right->left); // 右儿子这棵树的左边的高
度
218 int hr = HEIGHT((*ptree)->right->right); //右儿子这棵树的右边的
高度
219 if(hl>hr){ //如果左边高
220 *ptree = rl_rotation(*ptree); //那就需要rl旋转
221 }else{ //如果右边高
222 *ptree = rr_rotation(*ptree); //那就需要rr旋转
223 }
224 }
225 (*ptree)->height = MAX(HEIGHT((*ptree)->left),HEIGHT((*ptree)->right)) +1; //更新这个节点的高度
226 }
227 return ret; //返回删除结果
228 }else{ //要被删除的节点在右边
229 ret = avltree_delete(&(*ptree)->right,key);
230 if(ret == 0){
231 if(HEIGHT((*ptree)->left)-HEIGHT((*ptree)->right) == 2){
232 int hl = HEIGHT((*ptree)->left->left);
233 int hr = HEIGHT((*ptree)->left->right);
234 if(hl>hr){
235 *ptree = ll_rotation(*ptree);
236 }else{
237 *ptree = lr_rotation(*ptree);
238 }
239 }
240 (*ptree)->height = MAX(HEIGHT((*ptree)->left),HEIGHT((*ptree)->right)) +1;
241 }
242 return ret;
243 }
244 }
上一篇： 数据生成器