AVL树的概念以及代码实现

中国大学MOOC-陈越、何钦铭-数据结构

跳过概念，直接看代码（不知道怎么做页内跳转，逃ε=ε=ε

• RR旋转（右单旋）

  破坏节点在发现节点的右子树的右子树上
  破坏节点：插入此节点之后开始不平衡。
  发现节点：插入节点后，离破坏节点路径最短的不平衡结点。

  
  
  RR旋转

• LL旋转（左单旋）

  LL旋转

• LR旋转

LR旋转

• RL旋转

RL旋转

代码在此

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct AVLTreeNode *AVLTree;
typedef struct AVLTreeNode *SubTree;
typedef struct AVLTreeNode
{
    int height;     /* to calculate balance factor */
    DataType data;
    AVLTree left;
    AVLTree right;
};

AVLTree CreatAVLTree(DataType node);
AVLTree InsertIntoAVL(AVLTree T, DataType node);
int GetHeight(SubTree T);
int Max(int a, int b);

SubTree LLRotate(SubTree T);
SubTree RRRotate(SubTree T);
SubTree LRRotate(SubTree T);
SubTree RLRotate(SubTree T);

int main(int argc, char const *argv[])
{
    int n, i;
    AVLTree T;
    DataType tempNode;

    scanf("%d", &n);
    scanf("%d", &tempNode);
    T = CreatAVLTree(tempNode); /* creat an empty tree */
    /* insert sequence to build a AVL tree */
    for (i = 1; i < n; i++) {
        scanf("%d", &tempNode);
        if (T) {
            T = InsertIntoAVL(T, tempNode);
        }
        else break;
        /* judge the balance of the tree after insertion by the balance factor */
        /* check from the node to root */
    }
    if (T)
        printf("%d", T->data);
    else
        printf("Input Error! You enter a same number \n");      /* it's not necessary */

    return 0;
}

AVLTree CreatAVLTree(DataType node)
{
    AVLTree T;
    T = (AVLTree)malloc(sizeof(struct AVLTreeNode));
    T->height = 1;
    T->data   = node;
    T->left   = NULL;
    T->right  = NULL;
    return T;
}

AVLTree InsertIntoAVL(AVLTree T, DataType node)
{
    if (!T)
        T = CreatAVLTree(node);
    else {
        if (node < T->data) {
            T->left = InsertIntoAVL(T->left, node);
            /* it will judge the balance factor from bottom to the top */
            if (GetHeight(T->left) - GetHeight(T->right) == 2) {
                if (node < T->left->data)
                    T = LLRotate(T);
                /* it means the node on the current subtree's left subtree 'left */
                else
                    T = LRRotate(T);
            }
        }
        else if (node > T->data) {
            T->right = InsertIntoAVL(T->right, node);
            if (GetHeight(T->right) - GetHeight(T->left) == 2) {
                if (node > T->right->data)
                    T = RRRotate(T);
                else
                    T = RLRotate(T);
            }
        }
        else    /* considering the equal situation, but in this case, it's not necessary */
            return NULL;
    }
    /* updata the height of AVLTree from the leaf node to the root after every insert */
    T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1;

    return T;

}

int GetHeight(SubTree T)
{
    if (!T)
        return 0;
    else
        return T->height;
}

int Max(int a, int b)
{
    return (a > b) ? a : b;
}

SubTree LLRotate(SubTree T)
{
    SubTree Tmp;
    Tmp = T;
    T = T->left;
    Tmp->left = T->right;
    T->right  = Tmp;
    Tmp->height = Max(GetHeight(Tmp->left), GetHeight(Tmp->right)) + 1;
    T->height   = Max(GetHeight(T->left), GetHeight(T->right)) + 1;
    return T;
}

SubTree RRRotate(SubTree T)
{
    SubTree Tmp;
    Tmp = T;
    T = T->right;
    Tmp->right = T->left;
    T->left    = Tmp;
    Tmp->height = Max(GetHeight(Tmp->left), GetHeight(Tmp->right)) + 1;
    T->height   = Max(GetHeight(T->left), GetHeight(T->right)) + 1;
    return T;
}

SubTree LRRotate(SubTree T)
{
    T->left = RRRotate(T->left);
    T = LLRotate(T);
    return T;
}

SubTree RLRotate(SubTree T)
{
    T->right = LLRotate(T->right);
    T = RRRotate(T);
    return T;
}

/*SubTree LRRotate(SubTree T)
{
    SubTree Tmp;
    Tmp = T;
    T = T->left->right;
    Tmp->left->right = T->left;
    T->left   = Tmp->left;
    Tmp->left = T->right;
    T->right  = Tmp;
    Tmp->height = Max(GetHeight(Tmp->left), GetHeight(Tmp->right)) + 1;
    T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1;
    return T;
}*/

• LR旋转可以转换成发现者的左子树 T->left 先做 RR旋转，然后发现者再做LL旋转。
  下面即为一个例子
  8为发现者，4为破坏者。
  
  LR旋转例子

• 发现者的左子树 T->left 先做 RR旋转

  
  
  T->left做LL旋转
• 发现者再做LL旋转
  
  发现者做LL旋转
  
  本文完