用C++实现（平衡）二叉排序树的各种算法

以下是使用C++实现平衡二叉排序树AVL树的各种算法：

#include <iostream>
using namespace std;

// AVL树节点定义
struct Node {
    int val; // 节点值
    int height; // 节点高度
    Node* left; // 左子节点指针
    Node* right; // 右子节点指针
    Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};

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

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

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

// 左旋
void leftRotate(Node*& node) {
    Node* temp = node->right;
    node->right = temp->left;
    temp->left = node;
    updateHeight(node);
    updateHeight(temp);
    node = temp;
}

// 右旋
void rightRotate(Node*& node) {
    Node* temp = node->left;
    node->left = temp->right;
    temp->right = node;
    updateHeight(node);
    updateHeight(temp);
    node = temp;
}

// 平衡操作
void balance(Node*& node) {
    int bf = getBalanceFactor(node);
    if (bf > 1) {
        int lbf = getBalanceFactor(node->left);
        if (lbf >= 0) {
            rightRotate(node);
        } else {
            leftRotate(node->left);
            rightRotate(node);
        }
    } else if (bf < -1) {
        int rbf = getBalanceFactor(node->right);
        if (rbf <= 0) {
            leftRotate(node);
        } else {
            rightRotate(node->right);
            leftRotate(node);
        }
    }
}

// AVL树插入操作
void insert(Node*& node, int val) {
    if (!node) {
        node = new Node(val);
        return;
    }
    if (val < node->val) {
        insert(node->left, val);
    } else if (val > node->val) {
        insert(node->right, val);
    } else {
        return;
    }
    updateHeight(node);
    balance(node);
}

// AVL树删除操作
void remove(Node*& node, int val) {
    if (!node) {
        return;
    }
    if (val < node->val) {
        remove(node->left, val);
    } else if (val > node->val) {
        remove(node->right, val);
    } else {
        if (node->left && node->right) {
            Node* temp = node->right;
            while (temp->left) {
                temp = temp->left;
            }
            node->val = temp->val;
            remove(node->right, temp->val);
        } else {
            Node* temp = node;
            if (node->left) {
                node = node->left;
            } else if (node->right) {
                node = node->right;
            } else {
                node = nullptr;
            }
            delete temp;
        }
    }
    if (!node) {
        return;
    }
    updateHeight(node);
    balance(node);
}

// 中序遍历
void inorderTraversal(Node* node) {
    if (!node) {
        return;
    }
    inorderTraversal(node->left);
    cout << node->val << " ";
    inorderTraversal(node->right);
}

// AVL树测试
int main() {
    Node* root = nullptr;
    insert(root, 5);
    insert(root, 3);
    insert(root, 7);
    insert(root, 2);
    insert(root, 4);
    insert(root, 6);
    insert(root, 8);
    inorderTraversal(root);
    cout << endl;
    remove(root, 5);
    inorderTraversal(root);
    cout << endl;
    return 0;
}

以上代码演示了AVL树的插入、删除、中序遍历操作，其他平衡二叉排序树算法的实现方式类似，只需根据平衡条件和平衡操作进行相应的修改。