MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » AVL平衡二叉树的疑点

AVL平衡二叉树的疑点

www.MyException.Cn  网友分享于:2013-03-07  浏览:3次
AVL平衡二叉树的疑问?
在严蔚敏的数据结构中,关于二叉排序树的平衡,有这么一个函数,有点看不明白,


//左树减去右树等于平衡因子
#define LH 1
#define EH 0
#define RH -1
typedef struct s_tree_t{
int data; //数据
int bf; //平衡因子
struct s_tree_t * lchild;
struct s_tree_t * rchild;
}BSTree;
void LeftBalance(BSTree &t) {
lc = t->lchild;
switch(lc->bf) {
case LH://左旋转
t->bf = lc->bf = EH;R_Rotate(t);
break;
case RH://先左后右旋转
rd = lc->rchild;
switch(rd->bf) {
case LH://(1)
t->bf = RH;
lc->bf = EH;
break;
case EH:
t->bf = lc->bf = EH;
break;
case RH://(2)
t->bf = EH;
lc->bf = LH;
break;
}
rd->bf = EH;
L_Rotate(t->lchild);
R_Rotate(t->rchild);
break;
}
}

其中(1),和(2)如果存在这个情况的话,只要rd单向左,单向右移动就可以了,为什么还用用,双向先左后右移动呢?
AVL 平衡二叉树 数据结构 算法

------解决方案--------------------
switch本身是在调节balance factor。你想问什么?
------解决方案--------------------
只有Left-Right-case和Right-Left-case才需要旋转两次

分别是 左旋-右旋 和 右旋-左旋

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有