用C++写平衡树模板代码

平衡树也称为自平衡二叉搜索树，实现起来比较复杂，需要用到旋转操作来保持树的平衡，如左旋、右旋、双旋等。

下面是一份平衡树的模板代码，主要包括插入、删除、查找操作，以及各种旋转操作实现。

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

// 平衡树节点结构体
typedef struct TreeNode {
    int val, height;        // val：节点权值，height：节点高度
    struct TreeNode *left, *right;  // 左右子节点指针
} TreeNode;

// 获取节点高度
int getHeight(TreeNode *node) {
    return node ? node->height : 0;
}

// 获取节点平衡因子
int getBalanceFactor(TreeNode *node) {
    return getHeight(node->left) - getHeight(node->right);
}

// 更新节点高度
void updateHeight(TreeNode *node) {
    node->height = 1 + fmax(getHeight(node->left), getHeight(node->right));
}

// 左旋操作
TreeNode *leftRotate(TreeNode *node) {
    TreeNode *right = node->right;
    node->right = right->left;
    right->left = node;
    updateHeight(node);
    updateHeight(right);
    return right;
}

// 右旋操作
TreeNode *rightRotate(TreeNode *node) {
    TreeNode *left = node->left;
    node->left = left->right;
    left->right = node;
    updateHeight(node);
    updateHeight(left);
    return left;
}

// 平衡操作（使以node为根的树平衡，返回新根节点）
TreeNode *balance(TreeNode *node) {
    // 更新节点高度
    updateHeight(node);

    // 计算平衡因子
    int balanceFactor = getBalanceFactor(node);

    // 如果平衡因子为2，说明左子树比右子树高
    if (balanceFactor > 1) {
        if (getBalanceFactor(node->left) < 0) {  // 如果左子树的右子树比左子树高
            node->left = leftRotate(node->left);    // 先左旋左子节点
        }
        return rightRotate(node);
    }

    // 如果平衡因子为-2，说明右子树比左子树高
    else if (balanceFactor < -1) {
        if (getBalanceFactor(node->right) > 0) {  // 如果右子树的左子树比右子树高
            node->right = rightRotate(node->right); // 先右旋右子节点
        }
        return leftRotate(node);
    }

    // 否则说明当前子树已经平衡，直接返回
    return node;
}

// 插入操作（p为当前子树的根节点，val为要插入的节点权值）
TreeNode *insert(TreeNode *p, int val) {
    if (!p) {   // 如果是空节点，说明找到了要插入的位置，新建一个节点
        p = (TreeNode *) malloc(sizeof(TreeNode));
        p->val = val;
        p->height = 1;
        p->left = p->right = NULL;
    } else if (val < p->val) {  // 如果要插入的值小于节点值，向左子树递归
        p->left = insert(p->left, val);
    } else {    // 否则向右子树递归
        p->right = insert(p->right, val);
    }
    return balance(p);  // 插入成功后，再进行平衡操作
}

// 寻找以p为根的树中权值为val的节点
TreeNode *find(TreeNode *p, int val) {
    if (!p) {                   // 如果搜索到空节点，说明未找到
        return NULL;
    } else if (val < p->val) {  // 如果要查找的值小于节点值，向左子树递归
        return find(p->left, val);
    } else if (val > p->val) {  // 如果要查找的值大于节点值，向右子树递归
        return find(p->right, val);
    } else {                    // 否则就是要查找的节点
        return p;
    }
}

// 查找以p为根的树中的最小节点
TreeNode *findMin(TreeNode *p) {
    while (p->left) {       // 不停向左子节点遍历，直到为空
        p = p->left;
    }
    return p;
}

// 删除操作（p为当前子树的根节点，val为要删除的节点权值）
TreeNode *delete(TreeNode *p, int val) {
    if (!p) {                   // 如果搜索到空节点，说明未找到，直接返回
        return NULL;
    } else if (val < p->val) {  // 如果要删除的值小于节点值，向左子树递归
        p->left = delete(p->left, val);
    } else if (val > p->val) {  // 如果要删除的值大于节点值，向右子树递归
        p->right = delete(p->right, val);
    } else {                    // 否则就是要删除的节点
        if (!p->left && !p->right) {      // 如果是叶子节点，直接删除
            free(p);
            return NULL;
        } else if (p->left && !p->right) {    // 如果只有左子节点（或没有子节点），指向左子节点
            TreeNode *left = p->left;
            free(p);
            return left;
        } else if (!p->left && p->right) {    // 如果只有右子节点，指向右子节点
            TreeNode *right = p->right;
            free(p);
            return right;
        } else {                            // 如果有左、右子节点，用右子节点的最小值代替当前节点，然后再删除右子节点最小值
            TreeNode *minRight = findMin(p->right);
            p->val = minRight->val;
            p->right = delete(p->right, p->val);
        }
    }
    return balance(p);  // 删除成功后，再进行平衡操作
}

// 深度优先遍历（先序遍历）
void dfs(TreeNode *p) {
    if (!p) return;
    printf("%d ", p->val);
    dfs(p->left);
    dfs(p->right);
}

// 主函数
int main() {
    TreeNode *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = delete(root, 30);
    root = delete(root, 20);
    root = insert(root, 25);
    dfs(root);
    return 0;
}

上述代码给出了平衡树节点结构体、获取节点高度、获取节点平衡因子、更新节点高度、左旋、右旋、平衡操作、插入、查找、查找最小节点和删除等常用函数实现。同时，还给出了一个简单的测试代码，用于对平衡树进行测试和验证。

使用平衡树可以大大提高数据插入、删除、查找等操作的效率，所以是实际应用中很常用的数据结构之一。