这个AVL平衡代码有什么问题?
每次我使用 avlRotate 函数时,它都会从树中删除一些元素。 z是检测到不平衡的节点,y是其高度较大的子树节点,x是新插入的节点。 该函数在一次插入后立即调用。
#define RESTRUCTURE a->left = t0; a->right = t1; c->left = t2; c->right = t3; b->left = a; b->right = c;
avlTree avlRotate(avlTree z,avlTree y,avlTree x)
{
avlTree a,b,c;
avlTree t0,t1,t2,t3;
if(y==z->left && x==y->left) //single rotation
{
a=x;b=y;c=z;
t0=a->left;
t1=a->right;
t2=b->right;
t3=c->right;
RESTRUCTURE
c->height[0] = y->height[1];
}
else if(y==z->right && x==y->right) //single rotation
{
a=z;b=y;c=x;
t0=a->left;
t1=b->left;
t2=c->left;
t3=c->right;
RESTRUCTURE
a->height[1] = y->height[0];
}
else if(y==z->right && x==y->left) //double rotation
{
a=z;b=x;c=y;
t0=a->left;
t1=b->left;
t2=b->right;
t3=c->right;
RESTRUCTURE
a->height[1] = x->height[0];
c->height[0] = x->height[1];
}
else if(y==z->left && x==y->right) //double rotation
{
a=y;b=x;c=z;
t0=a->left;
t1=b->left;
t2=b->right;
t3=c->right;
RESTRUCTURE
a->height[1] = x->height[0];
c->height[0] = x->height[1];
}
printf("\nRem parts:\n");
printf("{%d %d} {%d %d} {%d %d}\n",a->part->range[0],a->part->range[1],b->part->range[0],b->part->range[1],c->part->range[0],c->part->range[1]);
printf("\n\n");
b->height[0] = ( (a->height[0] > a->height[1]) ? (a->height[0])+1 : (a->height[1])+1 );
b->height[1] = ( (c->height[0] > c->height[1]) ? (c->height[0])+1 : (c->height[1])+1 );
a->balFactor = a->height[0] - a->height[1];
b->balFactor = b->height[0] - b->height[1];
c->balFactor = c->height[0] - c->height[1];
return(b);
}
调用该函数:
if(a->balFactor > 1 || a->balFactor < -1)
{
printf("imbalance fside=%d pside=%d\n",*finalSide,*prevSide);
if(*finalSide == 0)
{yLike = a->left;}
else
{yLike = a->right;}
if(*prevSide == 0)
{xLike = yLike->left;}
else
{xLike = yLike->right;}
printf("passing to rotate %u %u %u\n",a,yLike,xLike);
printf("{%d %d} {%d %d} {%d %d}\n",a->part->range[0],a->part->range[1],yLike->part->range[0],yLike->part->range[1],xLike->part->range[0],xLike->part->range[1]);
a = avlRotate(a,yLike,xLike);
avlInOrderTraversal(a,0);
printf("{%d %d} {%d %d} {%d %d}\n",a->left->part->range[0],a->left->part->range[1],a->part->range[0],a->part->range[1],a->right->part->range[0],a->right->part->range[1]);
}
在插入函数中
输出:
a->height[0]=1 a->height[1]=0
BALANCE FACTOR = 1
16 to 18
51 to 53
a->height[0]=0 a->height[1]=1
BALANCE FACTOR = -1
a->height[0]=2 a->height[1]=0
BALANCE FACTOR = 2
imbalance fside=0 pside=1
passing to rotate 147992552 147992584 147992616
{51 53} {16 18} {41 41}
Rem parts:
{16 18} {41 41} {51 53}
51 to 53
a->height[0]=0 a->height[1]=1
BALANCE FACTOR = -1
51 to 53
60 to 61
a->height[0]=1 a->height[1]=1
BALANCE FACTOR = 0
4 to 6
51 to 53
60 to 61
此函数是否有明显错误?
注意:每个节点存储一个范围,例如。 3 到 5
。
Everytime I use this my avlRotate function, it drops some elements from the tree.
z is the node in which imbalance was detected, y is its subtree node having the greater height, x is the newly inserted node.
This function is called immediately after a single insertion.
#define RESTRUCTURE a->left = t0; a->right = t1; c->left = t2; c->right = t3; b->left = a; b->right = c;
avlTree avlRotate(avlTree z,avlTree y,avlTree x)
{
avlTree a,b,c;
avlTree t0,t1,t2,t3;
if(y==z->left && x==y->left) //single rotation
{
a=x;b=y;c=z;
t0=a->left;
t1=a->right;
t2=b->right;
t3=c->right;
RESTRUCTURE
c->height[0] = y->height[1];
}
else if(y==z->right && x==y->right) //single rotation
{
a=z;b=y;c=x;
t0=a->left;
t1=b->left;
t2=c->left;
t3=c->right;
RESTRUCTURE
a->height[1] = y->height[0];
}
else if(y==z->right && x==y->left) //double rotation
{
a=z;b=x;c=y;
t0=a->left;
t1=b->left;
t2=b->right;
t3=c->right;
RESTRUCTURE
a->height[1] = x->height[0];
c->height[0] = x->height[1];
}
else if(y==z->left && x==y->right) //double rotation
{
a=y;b=x;c=z;
t0=a->left;
t1=b->left;
t2=b->right;
t3=c->right;
RESTRUCTURE
a->height[1] = x->height[0];
c->height[0] = x->height[1];
}
printf("\nRem parts:\n");
printf("{%d %d} {%d %d} {%d %d}\n",a->part->range[0],a->part->range[1],b->part->range[0],b->part->range[1],c->part->range[0],c->part->range[1]);
printf("\n\n");
b->height[0] = ( (a->height[0] > a->height[1]) ? (a->height[0])+1 : (a->height[1])+1 );
b->height[1] = ( (c->height[0] > c->height[1]) ? (c->height[0])+1 : (c->height[1])+1 );
a->balFactor = a->height[0] - a->height[1];
b->balFactor = b->height[0] - b->height[1];
c->balFactor = c->height[0] - c->height[1];
return(b);
}
The function is called with:
if(a->balFactor > 1 || a->balFactor < -1)
{
printf("imbalance fside=%d pside=%d\n",*finalSide,*prevSide);
if(*finalSide == 0)
{yLike = a->left;}
else
{yLike = a->right;}
if(*prevSide == 0)
{xLike = yLike->left;}
else
{xLike = yLike->right;}
printf("passing to rotate %u %u %u\n",a,yLike,xLike);
printf("{%d %d} {%d %d} {%d %d}\n",a->part->range[0],a->part->range[1],yLike->part->range[0],yLike->part->range[1],xLike->part->range[0],xLike->part->range[1]);
a = avlRotate(a,yLike,xLike);
avlInOrderTraversal(a,0);
printf("{%d %d} {%d %d} {%d %d}\n",a->left->part->range[0],a->left->part->range[1],a->part->range[0],a->part->range[1],a->right->part->range[0],a->right->part->range[1]);
}
in the insert function.
Output:
a->height[0]=1 a->height[1]=0
BALANCE FACTOR = 1
16 to 18
51 to 53
a->height[0]=0 a->height[1]=1
BALANCE FACTOR = -1
a->height[0]=2 a->height[1]=0
BALANCE FACTOR = 2
imbalance fside=0 pside=1
passing to rotate 147992552 147992584 147992616
{51 53} {16 18} {41 41}
Rem parts:
{16 18} {41 41} {51 53}
51 to 53
a->height[0]=0 a->height[1]=1
BALANCE FACTOR = -1
51 to 53
60 to 61
a->height[0]=1 a->height[1]=1
BALANCE FACTOR = 0
4 to 6
51 to 53
60 to 61
Is something obviously incorrect with this function?
Note: Each node stores a range, for eg. 3 to 5
.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
编写一个函数来转储你的树。对于每个节点,显示它认为的左、右、上和左/右子树深度。
在轮换之前和之后倾倒树木。
这就是我写我的文章时所做的。
你将在树中遇到微妙的错误 - 在每个问题上求助于 SO 会让你一事无成。当您爬树时,您还需要一个转储函数来调试重新平衡 - 有许多独特的重新平衡案例用于添加和删除,您需要验证它们。所有这些都需要树转储。
Write a function to dump your tree. For each node, display what it thinks its left, right, up and left/right subtree depths are.
Dump the tree before a rotation and then afterwards.
That's what I did when I wrote mine.
You -are- going to have subtle bugs in the tree - recourse to SO on each problem will get you nowhere fast. You are also going to need a dump function to debug rebalancing as you climb the tree - there are a number of unique rebalancing cases for add and delete which you need to verify. All of this requires a tree dump.
网络上有许多关于 AVL 树的资源,其中一些是:
继续空白泽维尔的进一步回答,我建议< strong>将程序的转储输出与动画结果进行比较。
There are numerous resources on AVL tree in the web, a chosen few are:
Continuing Blank Xavier's answer further, I would suggest to compare the dump output of your program with the animation results.