数据结构

平衡二叉树（英文名也称为 AVL 树），是在排序二叉树的结构基础上进行优化的一种二叉树，该树的性质是任意结点的左右子树高度相差都不超过1

在平衡二叉树中，主要分为四种需要调整平衡状态的情况
（1）A结点的平衡因子 = 【A结点的左子树高度】 - 【A结点的右子树高度】 = 2，发生不平衡，且新插入的结点为左孩子（A），则右旋转该子树，并更新旋转后的结点高度。

（2）A结点的平衡因子 = 【A结点的左子树高度】 - 【A结点的右子树高度】 = -2，发生不平衡，且新插入的结点为右孩子（C），则左旋转该子树，并更新旋转后的结点高度。

（3）A结点的平衡因子 = 【A结点的左子树高度】 - 【A结点的右子树高度】 = 2，发生不平衡，且新插入的结点为右孩子（B），则先左旋转p结点，再右旋转node结点，完成平衡操作。

（4）A结点的平衡因子 = 【A结点的左子树高度】 - 【A结点的右子树高度】 = -2，发生不平衡，且新插入的结点为左孩子（B），则先右旋转p结点，再左旋转node结点，完成平衡操作。

#include
#include
#define max(a,b) ((a>b)?(a):(b))

typedef char DataType;
typedef struct AVLNode
{
    DataType data;          // 数据域
    struct AVLNode *lchild; // 指针域，指向左孩子结点
    struct AVLNode *rchild; // 指针域，指向右孩子结点
    int height;             // 表示当前结点作为根结点子树的高度
}AVLNode, *AVLTree;

// 初始化
void InitAVLTree(AVLTree *T)
{
    (*T) = NULL;   // 初始化根节点为空
    printf("二叉树已初始化!n");
}

// 获取子树高度
int getHeight(AVLNode *node)
{
    return node == NULL ? 0: node->height;
}

// 右旋转
AVLNode* Rotate_R(AVLNode *node)
{
    AVLNode *p = node->lchild;
    node->lchild = p->rchild;
    p->rchild = node;

    // 更新高度（注意顺序）
    node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
    p->height = max(getHeight(p->lchild), getHeight(p->rchild)) + 1;

    return p;
}

// 左旋转
AVLNode* Rotate_L(AVLNode *node)
{
    AVLNode *p = node->rchild;
    node->rchild = p->lchild;
    p->lchild = node;

    // 更新高度（注意顺序）
    node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
    p->height = max(getHeight(p->lchild), getHeight(p->rchild)) + 1;

    return p;
}

// 先左旋转，再右旋转
AVLNode* Rotate_LR(AVLNode *node)
{
    AVLNode *p = node->lchild;
    node->lchild = Rotate_L(p);
    return Rotate_R(node);
}

// 先右旋转，再左旋转
AVLNode* Rotate_RL(AVLNode *node)
{
    AVLNode *p = node->rchild;
    node->rchild = Rotate_R(p);
    return Rotate_L(node);
}

// 计算平衡因子
int getBalance(AVLNode *node)
{
    if (node == NULL)
    {
        return 0;
    }
    return getHeight(node->lchild) - getHeight(node->rchild);
}

// 排序二叉树的插入操作
void AVLTreeInsert(AVLTree *T, DataType x)
{
    if ((*T) == NULL)
    {
        // 如果当前二叉树结点为空, 即是插入的位置，则分配新的结点空间
        (*T) = (AVLNode *)malloc(sizeof(AVLNode));
        (*T)->data = x;
        (*T)->height = 1;
        (*T)->lchild = (*T)->rchild = NULL;
    }
    else if (x < (*T)->data)
    {
        // 递归左子树查找插入位置
        AVLTreeInsert(&(*T)->lchild, x);
    }
    else if(x > (*T)->data)
    {
        // 递归右子树查找插入位置
        AVLTreeInsert(&(*T)->rchild, x);
    }
    else
    {
        printf("插入失败!存在相同数据!n");
        return;
    }

    // 在递归插入过程中更新父结点的高度
    (*T)->height = max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;
    
    // 获取平衡因子
    int balance = getBalance((*T));
    
    printf("结点:%c, 高度 = %d, 平衡因子 = %dt",(*T)->data, (*T)->height, balance);
    
    // 根据平衡因子选择 旋转方式
    if (balance > 1 && x < (*T)->lchild->data)
    {
        printf("右旋");
        (*T) = Rotate_R((*T));
    }
    else if (balance < -1 && x > (*T)->rchild->data)
    {
        printf("左旋");
        (*T) = Rotate_L((*T));
    }
    else if (balance > 1 && x > (*T)->lchild->data)
    {
        printf("左右旋");
        (*T) = Rotate_LR((*T));
    }
    else if (balance < -1 && x < (*T)->rchild->data)
    {
        printf("右左旋");
        (*T) = Rotate_RL((*T));
    }
    printf("n");
}

// 先序遍历
void PreOrderTraverse(AVLTree T)
{
    if (T)
    {
        printf("%c ", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

int main()
{
    AVLTree T;
    InitAVLTree(&T);
    DataType x;
    while (1)
    {
        printf("输入插入数据:");
        fflush(stdin);
        scanf("%c", &x);
        if (x == '#')
        {
            break;
        }
        AVLTreeInsert(&T, x);
        printf("先序遍历:");
        PreOrderTraverse(T);
        printf("n");
    }
    system("pause");
    return 0;
}

右旋转

左旋转

先左旋转，再右旋转

先右旋转，在左旋转