AVL

AVL.cpp

#include <bits/stdc++.h>
using namespace std;
#define pass //
struct node
{
    node *lc, *rc;
    int key, color,height;
    node(){}
    node(int key):key(key){}
}*root;

void build(node *&T) {
    int v;
    scanf("%d", &v);
    if (!v) T = NULL;
    else {
        T = new node();
        T->key = v;
        build(T->lc);
        build(T->rc);
    }
}
int get_height(node *x) {
    if (!x) return 0;
    x->height = max(get_height(x->lc), (get_height(x->rc)));
}

int  update_height(node *x) {
    return max(get_height(x->lc), get_height(x->rc)) + 1;
}

int get_balance(node *x) {
    if (!x) return 0;
    return get_height(x->lc) - get_height(x->rc);
}

namespace AVL {
    node *ll_rotate(node *y) { //左左失衡 右旋
        // 失衡結點的左孩子比右孩子高2，左孩子的左子樹比右子樹高1
        // 左孩作跟，失衡 左接左孩子右子树 右沿
        node *x = y->lc;
        y->lc = x->rc;
        x->rc = y;
        x->height = update_height(x);
        y->height = update_height(y);
        return x;
    }

    node *rr_rotate(node *y) { //右右失衡 左旋
        // 失衡节点的右孩子比左孩子高2，左孩子的右子树比左子树高1
        // 右孩作跟，失衡 右接右孩左子树 左沿
        node *x = y->rc;
        y->rc = x->lc;
        x->lc = y;
        x->height = update_height(x);
        y->height = update_height(y);
        return x;
    }

    node *lr_rotate(node *y) { //左右失衡
        // 失衡结点的左子树比右子树高2，左孩子下的右子树比左子树高1
        // 先对x 左旋，再对y 右旋
        node *x = y->lc;
        y->lc = rr_rotate(x);
        return ll_rotate(y);
    }

    node *rl_rotate(node *y) { //右左失衡
        // 失衡节点的右子树比左子树高2，右孩子下的左子树比右子树高1
        // 先对x右旋，在对y左旋
        node *x = y->rc;
        y->lc = ll_rotate(x);
        return rr_rotate(y);
    }

    node *insert_node(int key, node *u) {
        if (!u) return new node(key);
        if (key < u->key)
            u->lc = insert_node(key, u->lc);
        else if (key > u->key)
            u->rc = insert_node(key, u->rc);
        else return u;

        u->height = update_height(u);
        int balance = get_balance(u);

        if (balance > 1 && get_balance(u->lc) >= 0) // 左左失衡
            return ll_rotate(u);

        if (balance < -1 && get_balance(u->rc) <= 0) // 右右失衡
            return rr_rotate(u);

        if (balance > 1 && get_balance(u->rc) < 0)
            return lr_rotate(u);

        if (balance < -1 && get_balance(u->rc) > 0)
            return rl_rotate(u);
    }

    node *insert(int key) {
        root->lc = insert_node(key, root);
    }

    node* find_node(int key, node *u) {
        if (!u) return NULL;
        if (key < u->key)
            return find_node(key, u->lc);
        else if(key > u->key)
            return find_node(key, u->rc);
        else return u;
    }
    node * find(int key) {
        return find_node(key, root);
    }
    
    node erase_node(int key, node *u)
    {
        
    }
}