在 C 中插入 AVL 树
Inserting AVL tree in C
我正在实现一个 AVL 树及其旋转等操作。
最后,当我尝试插入一个数组时,结果似乎
不同。谁能告诉我哪里出了问题!谢谢!
#include <stdio.h>
#include <stdlib.h>
#define LH +1
#define RH -1
#define EQ 0
typedef int BOOL;
typedef struct node
{
int bf;
struct node *left;
struct node *right;
int val;
}treeNode;
void L_Rotate(treeNode **T)
{
treeNode *p = (*T)->right;
(*T)->right = p->left;
p->left=*T;
*T=p;
}
void R_Rotate(treeNode **T)
{
treeNode *p=(*T)->left;
(*T)->left=p->right;
p->right=*T;
*T=p;
}
void Left_Balance(treeNode **T)
{
treeNode *p=(*T)->left;
treeNode *q;
switch(p->bf)
{
case LH:
p->bf=(*T)->bf=EQ;
R_Rotate(T);
break;
case RH:
q = p->right;
switch(q->bf)
{
case LH:
(*T)->bf=RH;
p->bf=EQ;
break;
case EQ:
(*T)->bf=q->bf=EQ;
break;
case RH:
p->bf=LH;
(*T)=EQ;
break;
}
q->bf=EQ;
L_Rotate(&p);
R_Rotate(T);
}
}
void Right_Balance(treeNode **T)
{
treeNode *p=(*T)->right;
treeNode *q;
switch(p->bf)
{
case RH:
(*T)->bf=p->bf=EQ;
L_Rotate(T);
break;
case LH:
q=p->left;
switch(q->bf)
{
case LH:
(*T)->bf=EQ;
p->bf=RH;
break;
case RH:
(*T)->bf=LH;
p->bf=EQ;
break;
}
q->bf=EQ;
R_Rotate(&p);
L_Rotate(T);
}
}
int insertAVL (treeNode **T,int key, BOOL *taller)
{
if(!*T)
{
*T=malloc(sizeof(treeNode));
if(!*T) return 0;
(*T)->left=(*T)->right=NULL;
(*T)->bf=EQ;
*taller = 1;
(*T)->val=key;
}
else
{
if(key==(*T)->val)
{
*taller= 0;
return 0;
}
else if(key<(*T)->val)
{
if(!insertAVL(&(*T)->left,key,taller)) return 0;
if(*taller)
{
switch((*T)->bf)
{
case LH:
Left_Balance(T);
*taller=0;
break;
case RH:
(*T)->bf=EQ;
*taller =0;
break;
case EQ:
(*T)->bf=LH;
*taller =1;
break;
}
}
}
else
{
if(!insertAVL(&(*T)->right,key,taller)) return 0;
if(*taller)
{
switch((*T)->bf)
{
case LH:
(*T)->bf=EQ;
*taller=0;
break;
case EQ:
(*T)->bf=RH;
*taller=1;
break;
case RH:
Right_Balance(T);
*taller =0;
break;
}
}
}
}
return 1;
}
void preOrder(treeNode *T)
{
if(!T)
{
return;
}
printf("%d\n",T->val);
preOrder(T->left);
preOrder(T->right);
}
int main() {
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
treeNode *T=NULL;
BOOL taller;
for(i=0;i<10;i++)
{
insertAVL(&T,a[i],&taller);
preOrder(T);
printf("-------\n");
}
return 0;
}
我每次插入树后遍历这棵树,结果
正确,直到我将9插入树。
当你修改树(或子树)时,你传入一个指向头指针的指针,这样改变就会反映在原来的link,全局头或者left/right link个节点。在我看来,这是一个很好的做法。
当你平衡树时,你做同样的事情,但有一个陷阱:
treeNode *p = (*T)->left;
// ... some stuff ...
L_Rotate(&p);
R_Rotate(T);
这里,p
是 (*T)->left
的本地副本。您最终修改了一个局部变量(它会立即超出范围),但不是父节点中的实际 link;节点是 "eaten".
您也可以将 p
设为 treeNode **
,或者假设您不更改指针本身,将旋转代码更改为:
L_Rotate(&(*T)->left);
R_Rotate(T);
另一个轮换也是如此。
我还注意到您的平衡 left/right 函数不对称,右平衡代码遗漏了 EQ 的情况。我做了一些尝试来添加它并重写 Right_Balance
以与 Left_Balance
对称,但这没有解决任何问题。问题不(只)在这里
如果我管理 AVL 没有错,你必须考虑每个单元格的 高度 来决定插入新值后如何平衡。
在你的情况下没有 height 但 bf 能够获得 3 个值 LH/RH/EQ,在某种程度上 bf 相当于 1 到 3 范围内的高度。但是在插入 10 之后,值为 4 的单元格实际上具有 4 的高度,你无法管理它,对我来说这个这就是为什么在 10 之后不能正确插入 9 的原因。
我正在实现一个 AVL 树及其旋转等操作。
最后,当我尝试插入一个数组时,结果似乎
不同。谁能告诉我哪里出了问题!谢谢!
#include <stdio.h>
#include <stdlib.h>
#define LH +1
#define RH -1
#define EQ 0
typedef int BOOL;
typedef struct node
{
int bf;
struct node *left;
struct node *right;
int val;
}treeNode;
void L_Rotate(treeNode **T)
{
treeNode *p = (*T)->right;
(*T)->right = p->left;
p->left=*T;
*T=p;
}
void R_Rotate(treeNode **T)
{
treeNode *p=(*T)->left;
(*T)->left=p->right;
p->right=*T;
*T=p;
}
void Left_Balance(treeNode **T)
{
treeNode *p=(*T)->left;
treeNode *q;
switch(p->bf)
{
case LH:
p->bf=(*T)->bf=EQ;
R_Rotate(T);
break;
case RH:
q = p->right;
switch(q->bf)
{
case LH:
(*T)->bf=RH;
p->bf=EQ;
break;
case EQ:
(*T)->bf=q->bf=EQ;
break;
case RH:
p->bf=LH;
(*T)=EQ;
break;
}
q->bf=EQ;
L_Rotate(&p);
R_Rotate(T);
}
}
void Right_Balance(treeNode **T)
{
treeNode *p=(*T)->right;
treeNode *q;
switch(p->bf)
{
case RH:
(*T)->bf=p->bf=EQ;
L_Rotate(T);
break;
case LH:
q=p->left;
switch(q->bf)
{
case LH:
(*T)->bf=EQ;
p->bf=RH;
break;
case RH:
(*T)->bf=LH;
p->bf=EQ;
break;
}
q->bf=EQ;
R_Rotate(&p);
L_Rotate(T);
}
}
int insertAVL (treeNode **T,int key, BOOL *taller)
{
if(!*T)
{
*T=malloc(sizeof(treeNode));
if(!*T) return 0;
(*T)->left=(*T)->right=NULL;
(*T)->bf=EQ;
*taller = 1;
(*T)->val=key;
}
else
{
if(key==(*T)->val)
{
*taller= 0;
return 0;
}
else if(key<(*T)->val)
{
if(!insertAVL(&(*T)->left,key,taller)) return 0;
if(*taller)
{
switch((*T)->bf)
{
case LH:
Left_Balance(T);
*taller=0;
break;
case RH:
(*T)->bf=EQ;
*taller =0;
break;
case EQ:
(*T)->bf=LH;
*taller =1;
break;
}
}
}
else
{
if(!insertAVL(&(*T)->right,key,taller)) return 0;
if(*taller)
{
switch((*T)->bf)
{
case LH:
(*T)->bf=EQ;
*taller=0;
break;
case EQ:
(*T)->bf=RH;
*taller=1;
break;
case RH:
Right_Balance(T);
*taller =0;
break;
}
}
}
}
return 1;
}
void preOrder(treeNode *T)
{
if(!T)
{
return;
}
printf("%d\n",T->val);
preOrder(T->left);
preOrder(T->right);
}
int main() {
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
treeNode *T=NULL;
BOOL taller;
for(i=0;i<10;i++)
{
insertAVL(&T,a[i],&taller);
preOrder(T);
printf("-------\n");
}
return 0;
}
我每次插入树后遍历这棵树,结果
正确,直到我将9插入树。
当你修改树(或子树)时,你传入一个指向头指针的指针,这样改变就会反映在原来的link,全局头或者left/right link个节点。在我看来,这是一个很好的做法。
当你平衡树时,你做同样的事情,但有一个陷阱:
treeNode *p = (*T)->left;
// ... some stuff ...
L_Rotate(&p);
R_Rotate(T);
这里,p
是 (*T)->left
的本地副本。您最终修改了一个局部变量(它会立即超出范围),但不是父节点中的实际 link;节点是 "eaten".
您也可以将 p
设为 treeNode **
,或者假设您不更改指针本身,将旋转代码更改为:
L_Rotate(&(*T)->left);
R_Rotate(T);
另一个轮换也是如此。
我还注意到您的平衡 left/right 函数不对称,右平衡代码遗漏了 EQ 的情况。我做了一些尝试来添加它并重写 Right_Balance
以与 Left_Balance
对称,但这没有解决任何问题。问题不(只)在这里
如果我管理 AVL 没有错,你必须考虑每个单元格的 高度 来决定插入新值后如何平衡。
在你的情况下没有 height 但 bf 能够获得 3 个值 LH/RH/EQ,在某种程度上 bf 相当于 1 到 3 范围内的高度。但是在插入 10 之后,值为 4 的单元格实际上具有 4 的高度,你无法管理它,对我来说这个这就是为什么在 10 之后不能正确插入 9 的原因。