平衡二叉树模板

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *l, *r;
};
node *ll(node *p) //右旋
{
    node *q = p->l;
    p->l = q->r;
    q->r = p;
    p = q;
    return p;
}
node *rr(node *p) //左旋
{
    node *q = p->r;
    p->r = q->l;
    q->l = p;
    p = q;
    return p;
}
node *lr(node *p) //先左旋再右旋
{
    p->l = rr(p->l);
    return ll(p);
}
node *rl(node *p) //先右旋再左旋
{
    p->r = ll(p->r);
    return rr(p);
}
int dep(node *p) //求树的深度
{
    if (p == NULL)
        return 0;
    return max(dep(p->l), dep(p->r)) + 1;
}
int diff(node *p) //求平衡因子差值
{
    return dep(p->l) - dep(p->r);
}
node *balance(node *p) //平衡操作
{
    int k = diff(p);
    if (k > 1) //左树高
    {
        if (diff(p->l) > 0) //左左
            p = ll(p);
        else //左右
            p = lr(p);
    }
    else if (k < -1) //右树高
    {
        if (diff(p->r) < 0) //右右
            p = rr(p);
        else //右左
            p = rl(p);
    }
    return p;
}
node *build(node *p, int x) //建树
{
    if (p == NULL)
    {
        p = new node;
        p->data = x;
        p->l = NULL;
        p->r = NULL;
    }
    else
    {
        if (x < p->data)
        {
            p->l = build(p->l, x);
            p = balance(p);
        }
        else
        {
            p->r = build(p->r, x);
            p = balance(p);
        }
    }
    return p;
}
node *minnode(node *p) //查询最小值节点
{
    node *q = p;
    while (q->l)
        q = q->l;
    return q;
}
node *maxnode(node *p) //查询最大值节点
{
    node *q = p;
    while (q->r)
    {
        q = q->r;
    }
    return q;
}
node *del(node *p, int k) //删除节点
{
    if (p == NULL)
        return p;
    if (k < p->data)
        p->l = del(p->l, k);
    else if (k > p->data)
        p->r = del(p->r, k);
    else
    {
        if (p->l == NULL || p->r == NULL)
        {
            node *q = p->l ? p->l : p->r;
            if (q == NULL)
            {
                q = p;
                p = NULL;
            }
            else
                *p = *q;
            delete q;
        }
        else
        {
            node *q = minnode(p->r);
            p->data = q->data;
            p->r = del(p->r, q->data);
        }
    }
    if (p == NULL)
        return p;
    p = balance(p);
    return p;
}
node *search(node *p, int k) //二分查找
{
    if (p->data == k)
        return p;
    else if (k < p->data)
    {
        if (p->l != NULL)
            return search(p->l, k);
        else
            return NULL;
    }
    else
    {
        if (p->r != NULL)
            return search(p->r, k);
        else
            return NULL;
    }
}
void mid(node *p)   //中序遍历- 有序输出
{
    if (p)
    {
        mid(p->l);
        cout << p->data << " ";
        mid(p->r);
    }
}