二叉搜索树（BST）的删除与插入：哪一操作速度更快？

Great question! Let's dive into how BST deletion works, then compare its performance to insertion to validate your hypothesis.

BST deletion has three distinct cases you need to handle, depending on the node being removed:

• Case 1: Deleting a leaf node (no children)
  This is the simplest scenario. Just remove the node from the tree—since it has no children, there's no need to rearrange anything. For example, if you're deleting a node with key 5 that has no left/right children, you just set its parent's left/right pointer (whichever pointed to 5) to null.

• Case 2: Deleting a node with exactly one child
  Here, you "bypass" the node being deleted. Take the child of the target node and link it directly to the target's parent. If the target was the left child of its parent, you set the parent's left pointer to the target's child; same logic applies for the right side. No extra restructuring needed beyond this single pointer update.

• Case 3: Deleting a node with two children
  This is the complex part—you need to find a replacement for the deleted node to maintain BST properties. There are two standard approaches:

  1. In-order predecessor: The largest node in the left subtree of the target. Replace the target's key with this predecessor's key, then delete the predecessor node (which will fall into either Case 1 or Case 2, since it can't have a right child).
  2. In-order successor: The smallest node in the right subtree of the target. Similarly, replace the target's key with the successor's key, then delete the successor node (again, it will be a leaf or have one child).

After replacing the key, you have to clean up by removing the predecessor/successor, which adds extra steps compared to the first two cases.

Let's start with theoretical time complexity first:

• Both insertion and deletion have an average-case time complexity of O(log n) (for a balanced BST) and worst-case O(n) (for a skewed BST, like a linked list).

But your hypothesis is correct when it comes to real-world performance: deletion is almost always slower than insertion, even when the time complexity classes are the same. Here's why:

• Insertion only requires traversing the tree to find the correct position and adding a new leaf node—no restructuring beyond a single pointer update.
• Deletion, even in the best case (leaf node), is similar to insertion, but in the worst case (node with two children), you have to:
  1. Traverse to find the target node (same as insertion)
  2. Traverse again to find the in-order predecessor/successor
  3. Update the target node's key
  4. Delete the predecessor/successor (which is an extra operation)

These extra steps add constant overhead that insertion doesn't have. Even in balanced BSTs like AVL or Red-Black trees, deletion requires more rotation operations to rebalance the tree compared to insertion, which further slows it down.

So while the asymptotic time complexity is the same, the actual runtime of deletion is higher because of the extra work needed to maintain BST properties after removing a node.

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