也许二杈树是很好用的,在插入和查找的时候时间复杂度一般为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树,它的结构中不包含高度特征,但包含一个平衡因子bf,用来判断结点的平衡性,若左孩子比右孩子高,则bf==1;否则,bf==-1;若左右相等则bf==0。
    AVL树的结点声明;
enum  BALANCE{LH = 1, EH = 0, RH = -1};
typedef struct avlnode
{
    BALANCE bf;//比普通二杈有序树多了一个平衡因子信息
    ElemType data;
    struct avlnode *lchild, *rchild;
} *AvlTree, *Position;
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);

//----------AVL树基本操作的算法实现--------------------

//在对一棵AVL树进行插入操作后,可能会破坏它的平衡条件,因此必须对新的AVL树进行调整,
这里用到了“单旋转”或“双旋转”的算法,分别适用于:
单左旋转(SingleRotateWithLeft);对结点p的左孩子的左子树进行一次插入
单右旋转(SingleRotateWithRight);对结点p的右孩子的右子树进行一次插入
双左旋转(DoubleRotateWithLeft);对结点p的左孩子的右子树进行一次插入
双右旋转(DoubleRotateWithRight);对结点p的右孩子的左子树进行一次插入
Position SingleRotateWithLeft(Position K2)
{
    Position K1;

    K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转
    K2->lchild = K1->rchild;
    K1->rchild = K2;

    return K1;
}

Position SingleRotateWithRight(Position K2)
{
    Position K1;

    K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转
    K2->rchild = K1->lchild;
    K1->lchild = K2;

    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之间进行一次单右旋转
}

AvlTree LeftBalance(AvlTree T) //左平衡处理
{
      AvlTree lT = T->lchild;
      switch (lT->bf) //检查左树的平衡度,并做相应处理
      {
            case LH :   T = SingleRotateWithLeft(T); //若新结点插入在T的左孩子的左子树上,对T单左旋转
                        T->bf = lT->bf = EH;   //重新设置平衡度
                        break;
            case RH :   AvlTree rT = lT->rchild;//若新结点插入在T的左孩子的右子树上,对T双左旋转,并重新设置平衡度
                        switch (rT->bf)
                        {
                              case LH :   T->bf = RH;
                                          lT->bf = EH;
                                          break;
                              case EH :   T->bf = lT->bf = EH; //我感觉这种情况应该不会出现
                                          break;
                              case RH :   T->bf = EH;
                                          lT->bf = LH;
                                          break
                        }
                        rT->bf = EH;
                        T = DoubleRotateWithLeft(T);
                        break;
      }
      return T;
}

AvlTree RightBalance(AvlTree T) //右平衡处理
{
      AvlTree rT = T->rchild;
      switch (rT->bf) //检查右树的平衡度,并做相应处理
      {
            case LH :   T = SingleRotateWithRight(T); //若新结点插入在T的右孩子的右子树上,对T单右旋转
                        T->bf = rT->bf = EH;   //重新设置平衡度
                        break;
            case RH :   AvlTree lT = rT->lchild;//若新结点插入在T的右孩子的左子树上,对T双右旋转,并重新设置平衡度
                        switch (lT->bf)
                        {
                              case LH :   T->bf = EH;
                                          rT->bf = RH;
                                          break;
                              case EH :   T->bf = rT->bf = EH; //我感觉这种情况应该不会出现
                                          break;
                              case RH :   T->bf = LH;
                                          rT->bf = EH;
                                          break
                        }
                        lT->bf = EH;
                        T = DoubleRotateWithRight(T);
                        break;
      }
      return T;
}

//向AVL树插入结点的操作
AvlTree Insert(ElemType x, AvlTree T, bool & taller)
{
    if(T == NULL)
    {
        T = (Position)malloc(sizeof(struct avlnode));
        if(T == NULL)
        {
            puts("wrong");
            exit(1);
        }
        T->data = x;
        T->lchild = T->rchild = NULL;
        T->bf = EH;
        taller = true; //插入新结点,树“长高”,置taller为真值
    }
    else if(T->data == x)//不做任何插入操作
        taller = false; //树未长高,置taller为假值
    else if(T->data > x)//把x插入到左子树中
    {
          T->lchild = Insert(x, T->lchild, taller);
          if (taller)//已经插入左子树,且树“长高”,需要检查平衡度,并做相应处理
          {
                  switch(T->bf)
                  {
                        case LH :   T = LeftBalance(T);//原本左树高于右树,需做左平衡处理,树高不变
                                    taller = false;
                                    break;
                        case EH :   T->bf = LH;//原本左右等高,现在左高于右,且树“长高”
                                    taller = true;
                                    break;
                        case RH :   T->bf = EH; //原本右树高于左树,现在左右等高,树高不变
                                    taller = false;
                                    break;
                  }
            }
    }
    else      //把x插入到右子树中,仿照处理左树的方法处理
    {
            T->rchild = Insert(x, T->rchild, taller);
          if (taller)
          {
                  switch(T->bf)
                  {
                        case LH :   T->bf = EH;
                                    taller = false;
                                    break;
                        case EH :   T->bf = RH;
                                    taller = true;
                                    break;
                        case RH :   T = RightBalance(T);
                                    taller = false;
                                    break;
                  }
            }
    }

    return T;
}
AVL树应用示例:
 /*输入一组数,存储到AVL树中,并进行输出*/
#include <iostream>
using namespace std;

#define MAX 100
enum  BALANCE{LH = 1, EH = 0, RH = -1};
typedef struct avlnode
{
    BALANCE bf;//比普通二杈有序树多了一个平衡因子信息
    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, bool & taller); //把数据存储到AVL树中
Position SingleRotateWithLeft(Position K2); //单左旋转
Position SingleRotateWithRight(Position K2); //单右旋转
Position DoubleRotateWithLeft(Position K3);//双左旋转
Position DoubleRotateWithRight(Position K3);//双右旋转
AvlTree LeftBalance(AvlTree T);// 左平衡处理
AvlTree RightBalance(AvlTree T); //右平衡处理
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<MAX);
    return i;
}
void Print(const int a[], int len)
{
    int i;

    for(i=0; i<len; i++)
        printf("%d\t", a[i]);
}
AvlTree Sort(AvlTree A, const int a[], int len)
{
    int i;
    bool taller = false;

    for(i=0; i<len; i++)
         A = Insert(a[i], A, taller);
    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));
}

//向AVL树插入结点的操作
AvlTree Insert(int x, AvlTree T, bool & taller)
{
    if(T == NULL)
    {
        T = (Position)malloc(sizeof(struct avlnode));
        if(T == NULL)
        {
            puts("wrong");
            exit(1);
        }
        T->data = x;
        T->lchild = T->rchild = NULL;
        T->bf = EH;
        taller = true; //插入新结点,树“长高”,置taller为真值
    }
    else if(T->data == x)//不做任何插入操作
        taller = false; //树未长高,置taller为假值
    else if(T->data > x)//把x插入到左子树中
    {
          T->lchild = Insert(x, T->lchild, taller);
          if (taller)//已经插入左子树,且树“长高”,需要检查平衡度,并做相应处理
          {
                  switch(T->bf)
                  {
                        case LH :   T = LeftBalance(T);//原本左树高于右树,需做左平衡处理,树高不变
                                    taller = false;
                                    break;
                        case EH :   T->bf = LH;//原本左右等高,现在左高于右,且树“长高”
                                    taller = true;
                                    break;
                        case RH :   T->bf = EH; //原本右树高于左树,现在左右等高,树高不变
                                    taller = false;
                                    break;
                  }
            }
    }
    else      //把x插入到右子树中,仿照处理左树的方法处理
    {
            T->rchild = Insert(x, T->rchild, taller);
          if (taller)
          {
                  switch(T->bf)
                  {
                        case LH :   T->bf = EH;
                                    taller = false;
                                    break;
                        case EH :   T->bf = RH;
                                    taller = true;
                                    break;
                        case RH :   T = RightBalance(T);
                                    taller = false;
                                    break;
                  }
            }
    }

    return T;
}

Position SingleRotateWithLeft(Position K2)
{
    Position K1;

    K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转
    K2->lchild = K1->rchild;
    K1->rchild = K2;

    return K1;
}

Position SingleRotateWithRight(Position K2)
{
    Position K1;

    K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转
    K2->rchild = K1->lchild;
    K1->lchild = K2;

    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之间进行一次单右旋转
}

AvlTree LeftBalance(AvlTree T) //左平衡处理
{
      AvlTree lT = T->lchild;
      switch (lT->bf) //检查左树的平衡度,并做相应处理
      {
            case LH :   T = SingleRotateWithLeft(T); //若新结点插入在T的左孩子的左子树上,对T单左旋转
                        T->bf = lT->bf = EH;   //重新设置平衡度
                        break;
            case RH :   AvlTree rT = lT->rchild;//若新结点插入在T的左孩子的右子树上,对T双左旋转,并重新设置平衡度
                        switch (rT->bf)
                        {
                              case LH :   T->bf = RH;
                                          lT->bf = EH;
                                          break;
                              case EH :   T->bf = lT->bf = EH; //我感觉这种情况应该不会出现
                                          break;
                              case RH :   T->bf = EH;
                                          lT->bf = LH;
                                          break;
                        }
                        rT->bf = EH;
                        T = DoubleRotateWithLeft(T);
                        break;
      }
      return T;
}

AvlTree RightBalance(AvlTree T) //右平衡处理
{
      AvlTree rT = T->rchild;
      switch (rT->bf) //检查右树的平衡度,并做相应处理
      {
            case RH :   T = SingleRotateWithRight(T); //若新结点插入在T的右孩子的右子树上,对T单右旋转
                        T->bf = rT->bf = EH;   //重新设置平衡度
                        break;
            case LH :   AvlTree lT = rT->lchild;//若新结点插入在T的右孩子的左子树上,对T双右旋转,并重新设置平衡度
                        switch (lT->bf)
                        {
                              case LH :   T->bf = EH;
                                          rT->bf = RH;
                                          break;
                              case EH :   T->bf = rT->bf = EH; //我感觉这种情况应该不会出现
                                          break;
                              case RH :   T->bf = LH;
                                          rT->bf = EH;
                                          break;
                        }
                        lT->bf = EH;
                        T = DoubleRotateWithRight(T);
                        break;
      }
      return T;
}

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(")");
        }
    }
}
Posted on 2006-06-04 16:53 梦想飞扬 阅读(1400) 评论(4)  编辑 收藏 引用

Feedback

# re: 平衡有序树AVL树之两种思路  回复  更多评论   

2006-06-05 19:27 by TH
你一定是一个算法高手. 呵呵,收集你很多文章 .
关注

# re: 平衡有序树AVL树之两种思路  回复  更多评论   

2007-07-30 16:07 by ll
没看到有delete的实现。

# re: 平衡有序树AVL树之两种思路  回复  更多评论   

2007-07-31 15:27 by ??
找到离插入点最近的不平衡节点,然后修改该点到插入点的路径(不包括这两点)上的balance factor,再作4种rotation处理,比之递归、弹栈都要高效。

# re: 平衡有序树AVL树之两种思路  回复  更多评论   

2008-01-20 22:10 by 关注
不错!!

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理