Lec 1: AVL Tress, Splay Trees and Amortized Analysis⚓︎

#ifndef _AvlTree_H

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType X, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
AvlTree Delete(ElementType X, AvlTree T);
ElementType Retrieve(Position P);

#endif /* _AvlTree_H */

// Place in the implementation file
struct AvlNode {
    ElementType Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
} 

static int Height(Position P) {
    if (P == NULL) 
        return -1;
    else 
        return P->Height;
}

AvlTree Insert(ElementType X, AvlTree T) {
    if (T == NULL) {
        // Create and return a one-node tree
        T = (AvlTree)malloc(sizeof(struct AvlNode));
        if (T == NULL) {
            FatalError("Out of space!!!");
        } else {
            T->Element = X;
            T->Height = 0;
            T->Left = T->Right = NULL;
        }
    } else if (X < T->Element) {
        T->Left = Insert(X, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2)
            if (X < T->Left->Element)
                T = SingleRotateWithLeft(T);
            else
                T = DoubleRotateWithLeft(T);
    } else if (X > T->Element) {
        T->Right = Insert(X, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2)
            if (X > T->Right->Element)
                T = SingleRotateWithRight(T);
            else
                T = DoubleRotateWithRight(T);
    }
    // Else X is in the tree already; we'll do nothing

    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}

static Position SingleRotateWithLeft(Position K2) {
    // K2: trouble finder
    // K1: the left son of K1

    Position K1;          

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), K2->Height) + 1;

    return K1;
}

static Position SingleRotateWithRight(Position K2) {
    // K2: trouble finder
    // K1: the right son of K1

    Position K1;          

    K1 = K2->Right;
    K2->Right = K1->Left;
    K1->Left = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Right), K2->Height) + 1;

    return K1;
}

static Position DoubleRotateWithLeft(Position K3) {
    // 先右旋 touble finder 的左孩子
    K3->Left = SingleRotateWithRight(K3->Left);

    // 再左旋 trouble finder 自身
    return K3 = SingleRotateWithLeft(K3);
}

static Position DoubleRotateWithRight(Position K3) {
    // 先左旋 touble finder 的右孩子
    K3->Right = SingleRotateWithLeft(K3->Right);

    // 再右旋 trouble finder 自身
    return K3 = SingleRotateWithRight(K3);
}