平衡二叉排序树删除节点

### 平衡二叉排序树中的节点删除

在平衡二叉排序树（AVL树或红黑树等）中执行节点删除操作时，不仅需要移除指定的节点，还需要保持树的高度平衡属性。对于普通的二叉排序树而言，删除过程涉及三种情况：

1. **目标节点无子节点**
2. **目标节点仅有一个子节点**
3. **目标节点有两个子节点**

当涉及到平衡二叉排序树时，在完成上述任一情形的操作之后可能破坏了原有的平衡条件，则需通过旋转等方式恢复其性质。

#### 删除操作的具体实现

下面给出一段基于C++语言描述的简单示例代码来展示如何在一个假设为自定义类型的`BSTNode*`指针所指向的数据结构上实施删除逻辑，并尝试维持该树作为一棵高度平衡的二叉搜索树[^1]。

// 定义二叉树结点
struct BSTNode {
    int data;
    BSTNode *left, *right;

    BSTNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 查找最小值辅助函数
BSTNode* minValueNode(BSTNode* node){
    BSTNode* current = node;
    
    /* 循环向下直到最左边 */
    while (current && current->left != nullptr)
        current = current->left;

    return current;
}

// 执行删除操作并返回新的根节点
BSTNode* deleteNode(BSTNode* root, int key){
    // 基本情况
    if (!root) return root;

    // 如果键小于当前节点数据则进入左子树继续寻找
    if (key < root->data)
        root->left = deleteNode(root->left, key);

    // 同理处理右子树的情况
    else if (key > root->data)
        root->right = deleteNode(root->right, key);

    // 当找到要删除的目标节点时...
    else {

        // 节点拥有两个孩子或者只有一个孩子的情形
        if ((root->left == nullptr)||(root->right == nullptr)) {
            BSTNode* temp = root->left ? root->left : root->right;

            // 若没有子节点则是叶子节点直接释放内存即可
            if(temp == nullptr){
                temp = root;
                root = nullptr;
            }
            else { // 只有单侧存在子节点的情况下复制过来再清理原位置资源
                *root = *temp;
            }

            free(temp);
        }else{
            // 两侧都有子节点的时候用后继替代被删者的位置
            BSTNode* temp = minValueNode(root->right); 

            // 将后续者的数值赋给待删除节点
            root->data = temp->data;

            // 接着去右边把那个用来替换的小家伙干掉
            root->right = deleteNode(root->right , temp->data);
        }
    }

    // 更新height以及判断是否失衡进而调整(此处省略具体细节)

    return root;
}

这段代码实现了基本的删除功能，但对于真正的平衡二叉排序树来说，每次修改后的重新平衡步骤是非常重要的部分，这通常会涉及到额外的状态维护和复杂的算法设计，比如AVL树里的LL/RR/LR/RL四种旋转方式或是红黑树特有的颜色翻转机制等等[^2]。