也许二杈树是很好用的，在插入和查找的时候时间复杂度一般为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 100enum  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(")");        }    }}

评论