平衡树模板

平衡树

在平衡树中，我们的根节点的左右子树的差，我们称之为平衡因子，当平衡因子等于1，0或-1时，此时的树是平衡的，我们不用管。当树是非平衡态的我们需要通过旋转来使树达到平衡态（非平衡态有LL,LR,RL,RR型）

模板

#include <bits/stdc++.h>
using namespace std;

struct node {
    int data;
    int height;
    node* lc;
    node* rc;

    node(int data, int height) {
        this->data = data;
        this->height = height; 
    }

};

void L(node* &root);

void R(node* &root);

void update(node* root);

int getHeight(node* root);

int getBF(node* root);

node* find(node* root, int data);

node* insert(node* &root, int data);

int main() {

}

void L(node* &root) {
    node* t = root->rc;
    t->lc = root;
    root->rc = t->lc;
    update(t);
    update(root);
}

void R(node* &root) {
    node* t = root->lc;
    t->rc = root;
    root->lc = t->rc;
    update(t);
    update(root);
}

void update(node* root) {
    root->data = max(root->lc->data, root->rc->data) + 1;
}

int getHeight(node* root) {
    if (root == NULL) return 0;
    return root->height; 
}

int getBF(node* root) {
    return getHeight(root->lc) - getHeight(root->rc);
}

node* find(node* root, int data) {
    if (root == NULL) {
        printf("Failed To Find\n");
        return NULL;
    }
    if (root->data == data) return root;
    if (root->data > data) return find(root->lc, data);
    if (root->data < data) return find(root->rc, data);
}

node* insert(node* &root, int data) {
    if (root == NULL) {
        root = new node(data,1);
        return root;
    }
    if (root->data == data) return root;
    if (root->data > data) {
        insert(root->lc, data);
        update(root);
        if (getBF(root) == 2) {
            if (getBF(root->lc) == 1) R(root);
            else if (getBF(root->lc) == -1) L(root->lc),R(root);
        }   
    } else {
        insert(root->lc, data);
        update(root);
        if (getBF(root) == -2) {
            if (getBF(root->rc) == -1) L(root);
            else if (getBF(root->rc) == 1) R(root->rc),L(root);
        }
    }
}