C语言实现AVL树插入操作: 图解与代码示例

C语言实现AVL树插入操作

AVL树作为一种自平衡二叉搜索树，在进行插入操作时，需要保证树的平衡性以维持其高效的搜索效率。

1. AVL树插入操作的步骤

1. 查找插入位置: 与普通二叉搜索树相同，首先需要找到新节点的插入位置。
2. 插入新节点: 在找到插入位置后，将新节点插入到树中。
3. 更新节点高度: 从插入节点的父节点开始，递归地向上更新每个节点的高度。
4. 检查平衡性: 从插入节点的父节点开始，递归地向上检查每个节点的平衡因子（左右子树高度差）。
5. 进行旋转操作: 如果发现某个节点的平衡因子大于1或小于-1，则需要进行旋转操作以恢复树的平衡性。

2. 代码实现

以下是使用C语言实现AVL树插入操作的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct AVLNode *PtrToAVLNode;
struct AVLNode{
    int Key;
    PtrToAVLNode Left;
    PtrToAVLNode Right;
    int Height;
};
typedef PtrToAVLNode AVLTree;

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

int GetHeight(AVLTree T) {
    if (T == NULL)
        return -1;
    else
        return T->Height;
}

AVLTree SingleRotateWithLeft(AVLTree A) {
    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Left), A->Height) + 1;
    return B;
}

AVLTree SingleRotateWithRight(AVLTree A) {
    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(A->Height, GetHeight(B->Right)) + 1;
    return B;
}

AVLTree DoubleRotateWithLeft(AVLTree A) {
    A->Left = SingleRotateWithRight(A->Left);
    return SingleRotateWithLeft(A);
}

AVLTree DoubleRotateWithRight(AVLTree A) {
    A->Right = SingleRotateWithLeft(A->Right);
    return SingleRotateWithRight(A);
}

AVLTree Insert(AVLTree T, int Key) {
    if (T == NULL) {
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Key = Key;
        T->Left = T->Right = NULL;
        T->Height = 0;
    }
    else if (Key < T->Key) {
        T->Left = Insert(T->Left, Key);
        if (GetHeight(T->Left) - GetHeight(T->Right) == 2) {
            if (Key < T->Left->Key)
                T = SingleRotateWithLeft(T);
            else
                T = DoubleRotateWithLeft(T);
        }
    }
    else if (Key > T->Key) {
        T->Right = Insert(T->Right, Key);
        if (GetHeight(T->Right) - GetHeight(T->Left) == 2) {
            if (Key > T->Right->Key)
                T = SingleRotateWithRight(T);
            else
                T = DoubleRotateWithRight(T);
        }
    }
    T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
    return T;
}

// 后序遍历打印AVL树
void PostOrderPrint(AVLTree T) {
    if (T != NULL) {
        PostOrderPrint(T->Left);
        PostOrderPrint(T->Right);
        printf('%d ', T->Key);
    }
}

// 中序遍历打印AVL树
void InOrderPrint(AVLTree T) {
    if (T != NULL) {
        InOrderPrint(T->Left);
        printf('%d ', T->Key);
        InOrderPrint(T->Right);
    }
}

int main() {
    int N, Key, i;
    AVLTree T = NULL;

    scanf('%d', &N);
    for (i = 0; i < N; i++) {
        scanf('%d', &Key);
        T = Insert(T, Key);
    }
    PostOrderPrint(T);
    printf('
');
    InOrderPrint(T);
    printf('
');

    return 0;
}

3. 示例程序

假设要插入以下数字序列：30, 20, 10, 40, 50, 25

程序运行后，会输出以下结果：

后序遍历: 10 25 20 50 40 30 中序遍历: 10 20 25 30 40 50

4. 总结

本文介绍了使用C语言实现AVL树插入操作的方法，并提供了详细的代码示例和程序运行结果。通过学习本文，相信读者能够更好地理解AVL树的插入操作，并掌握其代码实现方法。