正文

我所理解的二杈树032005-12-28 11:09:00

【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/goal00001111/8939.html

分享到：

有序二杈树是很好用的，在插入和查找的时候时间复杂度一般为O（logN），但如果左右子树失去平衡，也可能达到O（N）。为了防止这种现象发生，一种解决办法是是左右子树尽量保持平衡，即建立一种平衡有序树AVL树。 
 一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二杈有序树。空树的高度定义为-1。
 AVL树的结点声明；
typedef struct avlnode
{
 int height;//比普通二杈有序树多了一个高度信息
 ElemType data;
 struct bnode *lchild, *rchild;
} *AvlTree, *Position; 
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
static int Height(Position P);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);

//----------AVL树基本操作的算法实现--------------------
递归算法：
Position FindMin(AvlTree T)
{
 if(T==NULL)
  return NULL;
 else if(T->lchild == NULL)
  return T;
 else
  return FindMin(T->lchild);
}

Position FindMax(AvlTree T)
{
 if(T==NULL)
  return NULL;
 else if(T->rchild == NULL)
  return T;
 else
  return FindMax(T->rchild);
}
非递归算法：
Position FindMin(AvlTree T)
{
 if(T!=NULL)
 {
  while(T->lchild != NULL)
   T = T->lchild;
 }
 
 return T;
}

Position FindMax(AvlTree T)
{
 if(T!=NULL)
 {
  while(T->rchild != NULL)
   T = T->rchild;
 }
 
 return T;
}
//返回P点的高度
static int Height(Position P)
{
 if(P==NULL)
  return -1;
 else
  return P->height;
}
//在对一棵AVL树进行插入操作后，可能会破坏它的平衡条件，因此必须对新的AVL树进行调整，
这里用到了“单旋转”或“双旋转”的算法，分别适用于：
单左旋转（SingleRotateWithLeft）；对结点p的左孩子的左子树进行一次插入
单右旋转（SingleRotateWithRight）；对结点p的右孩子的右子树进行一次插入 
双左旋转（DoubleRotateWithLeft）；对结点p的左孩子的右子树进行一次插入
双右旋转（DoubleRotateWithRight）；对结点p的右孩子的左子树进行一次插入 
static Position SingleRotateWithLeft(Position K2)
{
 Position K1;
 
 K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转
 K2->lchild = K1->rchild;
 K1->rchild = K2;
 
 K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
 K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
 
 return K1;
}

static Position SingleRotateWithRight(Position K2)
{
 Position K1;
 
 K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转
 K2->rchild = K1->lchild;
 K1->lchild = K2;
 
 K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
 K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
 
 return K1;
}

static Position DoubleRotateWithLeft(Position K3)
{
 K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转
 
 return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转
}
static Position DoubleRotateWithRight(Position K3)
{
 K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转
 
 return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转
}

//向AVL树插入结点的操作
AvlTree Insert(float x, AvlTree T)
{
 if(T == NULL)
 {
  T = (Position)malloc(sizeof(struct avlnode));
  if(T == NULL)
  {
   puts("wrong");
   exit(1);
  }
  T->data = x; 
  T->height = 0;
  T->lchild = T->rchild = NULL;
 }
 else if(T->data == x)//不做任何插入操作
  ;
 else if(T->data > x)//把s所指结点插入到左子树中
 {
   T->lchild = Insert(x, T->lchild);
   if(Height(T->lchild) - Height(T->rchild) == 2) //若平衡被破坏
   {
   if(x < T->lchild->data)     //若x比T的左孩子小，对T单左旋转 
    T = SingleRotateWithLeft(T);
   else                         //否则，对T双左旋转  
    T = DoubleRotateWithLeft(T);
  }
 }
 else      //把s所指结点插入到右子树中
 {
   T->rchild = Insert(x, T->rchild);
   if(Height(T->rchild) - Height(T->lchild) == 2)
   {
   if(x > T->rchild->data)    //若x比T的右孩子大，对T单右旋转 
    T = SingleRotateWithRight(T);
   else                        //否则，对T双右旋转  
    T = DoubleRotateWithRight(T);
  }
 }
 T->height = Max(Height(T->lchild), Height(T->rchild)) + 1;
 
 return T;  
}
int Max(int a, int b)
{
 if(a>=b)
  return a;
 else
  return b;
}
AVL树应用示例:
/*输入一组数,存储到AVL树中,并进行输出*/
#include
#include

#define MAX 100
typedef struct avlnode
{
 int height;//比普通二杈有序树多了一个高度信息
 int data;
 struct avlnode *lchild, *rchild;
} *AvlTree, *Position; 

int Input(int a[]);//输入数据到数组,未排序
void Print(const int a[], int len); //输出未排序的原始数据
AvlTree Sort(AvlTree A, const int a[], int len); //对数据进行排序
AvlTree Insert(int x, AvlTree T); //把数据存储到AVL树中
Position SingleRotateWithLeft(Position K2); //单左旋转
Position SingleRotateWithRight(Position K2); //单右旋转
Position DoubleRotateWithLeft(Position K3);//双左旋转
Position DoubleRotateWithRight(Position K3);//双右旋转
int Height(Position P); //返回P点的高度
int Max(int a, int b);//返回a,b中的最大值
void inorder(const AvlTree bt); //中序遍历AVL树
void PrintBT(AvlTree bt); //输出二杈树

int main(void)
{
 int a[MAX]={0};
 int len;
 AvlTree A=NULL;
       
 len = Input(a);
 Print(a, len);
 printf("\n");
 A = Sort(A, a, len);
 PrintBT(A);
 printf("\n");
 inorder(A);
 system("pause");
  return 0;
}
int Input(int a[])
{
 int i=0;
 
 do
 {
  a[i++] = rand()%1000;//输入随机数
 } while(i return i;
}
void Print(const int a[], int len)
{
 int i;
 
 for(i=0; i  printf("%d\t", a[i]);
}
AvlTree Sort(AvlTree A, const int a[], int len)
{
 int i;
 
 for(i=0; i  A = Insert(a[i], A);
 return A;
}
void inorder(const AvlTree bt)
{
 AvlTree p=bt, stack[MAX];//p表示当前结点，栈stack[]用来存储结点
 int top=-1;
 
 do
 {
  while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
  {
   stack[++top] = p;
   p = p->lchild;
  }            
  if(top >= 0) //所有左孩子处理完毕后
  {
   p = stack[top--];//栈顶元素出栈
   printf("%d\t", p->data); //输出该结点
   p = p->rchild; //处理其右孩子结点
  }
 } while((p != NULL)||(top >= 0));
}
//返回P点的高度
int Height(Position P)
{
 if(P==NULL)
  return -1;
 else
  return P->height;
}
AvlTree Insert(int x, AvlTree T)
{
 if(T == NULL)
 {
  T = (Position)malloc(sizeof(struct avlnode));
  if(T == NULL)
  {
   puts("wrong");
   exit(1);
  }
  T->data = x; 
  T->height = 0;
  T->lchild = T->rchild = NULL;
 }
 else if(T->data >= x)//把s所指结点插入到左子树中
 {
   T->lchild = Insert(x, T->lchild);
   if(Height(T->lchild) - Height(T->rchild) == 2) //若平衡被破坏
   {
   if(x <= T->lchild->data)     //若x比T的左孩子小，对T单左旋转 
    T = SingleRotateWithLeft(T);
   else                         //否则，对T双左旋转  
    T = DoubleRotateWithLeft(T);
  }
 }
 else      //把s所指结点插入到右子树中
 {
   T->rchild = Insert(x, T->rchild);
   if(Height(T->rchild) - Height(T->lchild) == 2)
   {
   if(x > T->rchild->data)    //若x比T的右孩子大，对T单右旋转 
    T = SingleRotateWithRight(T);
   else                        //否则，对T双右旋转  
    T = DoubleRotateWithRight(T);
  }
 }
 T->height = Max(Height(T->lchild), Height(T->rchild)) + 1;
 
 return T;  
}
int Max(int a, int b)
{
 if(a>=b)
  return a;
 else
  return b;
}
Position SingleRotateWithLeft(Position K2)
{
 Position K1;
 
 K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转
 K2->lchild = K1->rchild;
 K1->rchild = K2;
 
 K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
 K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
 
 return K1;
}

Position SingleRotateWithRight(Position K2)
{
 Position K1;
 
 K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转
 K2->rchild = K1->lchild;
 K1->lchild = K2;
 
 K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
 K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
 
 return K1;
}

Position DoubleRotateWithLeft(Position K3)
{
 K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转
 
 return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转
}
Position DoubleRotateWithRight(Position K3)
{
 K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转
 
 return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转
}

void PrintBT(AvlTree bt)
{
 if(bt != NULL)
 {
  printf("%d", bt->data);
  if(bt->lchild!=NULL || bt->rchild!=NULL)
  {
   printf("(");
   PrintBT(bt->lchild);
   if(bt->rchild!=NULL)
    printf(",");
   PrintBT(bt->rchild); 
   printf(")");
  }
 }
}

阅读(3091) | 评论(0)


版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！

评论

暂无评论
您需要登录后才能评论，请 登录 或者 注册