带节点删除操作的BST后序遍历时间复杂度咨询

我想咨询在**非平衡二叉搜索树（BST）**中，执行后序遍历同时删除所有data为空字符串节点的时间复杂度。举个例子：一个存储单词及其释义的字典BST，需要删除所有释义为空的节点，树可能处于非平衡状态。

我的实现代码如下：

void delete_nodes(Node*& node) {
    if (node == nullptr) {
        return;
    }

    delete_nodes(node->left);
    delete_nodes(node->right);

    if (node->data == "") {
        // 待删除节点有0或1个子节点
        if (node->left == nullptr) {
            Node* temp = node->right;
            delete node;
            node = temp;
        } else if (node->right == nullptr) {
            Node* temp = node->left;
            delete node;
            node = temp;
        } else {
            // 待删除节点有2个子节点
            // 交换当前节点与右子树最左节点的值
            Node* temp = node->right;
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            node->data = temp->data;

            // 将右子树最左节点的data设为空字符串
            temp->data = "";

            // 删除右子树最左节点
            delete_nodes(node->right);
        }
    }
}

时间复杂度分析 #

核心遍历开销 #

后序遍历本身会访问每个节点恰好一次，这部分的时间复杂度是O(n)，其中n是树的节点总数。

删除操作的额外开销 #

删除操作的开销取决于待删除节点的子节点数量：

• 0/1个子节点的情况：删除操作是O(1)的常数时间，只需要调整指针并释放节点内存，不会额外遍历其他节点。
• 2个子节点的情况：这里会有两步额外操作：
  1. 查找右子树的最左节点：最坏情况下（右子树是链状结构），这一步需要遍历O(h)个节点，h是当前节点右子树的高度。
  2. 再次递归调用delete_nodes(node->right)：这会重复遍历右子树的所有节点——因为之前后序遍历已经访问过这个右子树了，现在相当于二次遍历，这是代码里的性能瓶颈。

分场景的时间复杂度 #

1. 最好情况：树是平衡的，且待删除节点大多是0/1子节点，此时额外开销可以忽略，总时间复杂度接近O(n)。
2. 平均情况：如果是随机构建的BST（平均高度O(logn)），即使有较多待删除节点，每次查找最左节点的平均开销是O(logn)，加上二次遍历的影响，总时间复杂度为O(nlogn)。
3. 最坏情况：树是完全不平衡的链状结构，且每个待删除节点都有2个子节点（比如每个节点的右子树都是长链），此时每个待删除节点都会触发一次右子树的二次遍历，总时间复杂度会达到O(n²)。

优化建议 #

代码里的二次遍历是可以避免的：找到右子树的最左节点后，不需要将其data设为空再递归删除，而是可以直接调整指针删除该节点，这样就能避免重复遍历右子树，把最坏时间复杂度降到O(n)。

内容的提问来源于stack exchange，提问作者Lama Ainabousi