Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/6.平衡二叉树(AVL树).md

#pragma clang diagnostic push
#pragma ide diagnostic ignored "misc-no-recursion"

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

typedef int ElementType;

struct AVLNode {
    ElementType Data;
    int Height;
    struct AVLNode *Left;
    struct AVLNode *Right;
};

void Visit(struct AVLNode *T) {
    printf("%d ", T->Data);
}

void PreOrder(struct AVLNode *T) {
    if (T != NULL) {
        Visit(T);
        PreOrder(T->Left);
        PreOrder(T->Right);
    }
}

void PrintPreOrder(struct AVLNode *T) {
    printf("PreOrder: ");
    PreOrder(T);
    printf("\n");
}

void InOrder(struct AVLNode *T) {
    if (T != NULL) {
        InOrder(T->Left);
        Visit(T);
        InOrder(T->Right);
    }
}

void PrintInOrder(struct AVLNode *T) {
    printf("InOrder: ");
    InOrder(T);
    printf("\n");
}

void PostOrder(struct AVLNode *T) {
    if (T != NULL) {
        PostOrder(T->Left);
        PostOrder(T->Right);
        Visit(T);
    }
}

void PrintPostOrder(struct AVLNode *T) {
    printf("PostOrder: ");
    PostOrder(T);
    printf("\n");
}

int GetHeight(struct AVLNode *T) {
    if (T == NULL) {
        return 0;
    }
    return T->Height;
}

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

struct AVLNode *SingleLeftRotation(struct AVLNode *K2) {
    struct AVLNode *K1;
    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;
    //旋转完后更新K1,K2的高度
    K2->Height = Max(GetHeight(K2->Left), GetHeight(K2->Right)) + 1;
    K1->Height = Max(GetHeight(K1->Left), K2->Height) + 1;
    return K1;
}

struct AVLNode *SingleRightRotation(struct AVLNode *K1) {
    struct AVLNode *K2;
    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;
    //旋转完后更新K1,K2的高度
    K1->Height = Max(GetHeight(K1->Left), GetHeight(K1->Right)) + 1;
    K2->Height = Max(GetHeight(K2->Right), K1->Height) + 1;
    return K2;
}

struct AVLNode *DoubleLeftRotation(struct AVLNode *K2) {
    K2->Left = SingleRightRotation(K2->Left);
    return SingleLeftRotation(K2);
}

struct AVLNode *DoubleRightRotation(struct AVLNode *K1) {
    K1->Right = SingleLeftRotation(K1->Right);
    return SingleLeftRotation(K1);
}

struct AVLNode *InsertAVL(struct AVLNode *T, ElementType X) {
    if (T == NULL) {
        T = malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Height = 1;
        T->Left = T->Right = NULL;
    } else if (X < T->Data) {
        T->Left = InsertAVL(T->Left, X);
        if (GetHeight(T->Left) - GetHeight(T->Right) == 2) {
            if (X < T->Left->Data) {
                T = SingleLeftRotation(T);
            } else {
                T = DoubleLeftRotation(T);
            }
        }
    } else if (X > T->Data) {
        T->Right = InsertAVL(T->Right, X);
        if (GetHeight(T->Right) - GetHeight(T->Left) == 2) {
            if (X > T->Right->Data) {
                T = SingleRightRotation(T);
            } else {
                T = DoubleRightRotation(T);
            }
        }
    } //else (X==T->Data) {不做任何事}
    T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
    return T;
}


int main() {
    struct AVLNode *T = NULL;
    for (int i = 0; i < 10; ++i) {
        T = InsertAVL(T, i);
    }

    PrintPreOrder(T);
    PrintInOrder(T);
    PrintPostOrder(T);

    free(T);
    return 0;
}

#pragma clang diagnostic pop