二叉搜索树删除而不复制

Question

在编写简单的二叉搜索树数据结构（非自平衡）时，大多数资源在删除具有两个子节点的节点时给出的建议是将数据从左子节点之一复制到要删除的节点。这是不好的做法吗？某种指针操作不会提供更快的结果吗？有没有可以推广这个的 BST 旋转算法？

Answer 1

是的，您不想复制该节点，您只想“移动”它（即更改指针）以将其放入您要删除的节点的位置。如果你不想保持平衡，那么你实际上不需要进行任何类型的旋转 - 你只需选择左子树中最右边的节点（或右子树中最左边的节点） -树）。您从当前位置删除它，然后将其插入到需要删除的节点的位置（所有这些都严格通过操作指针）。

Answer 2

复制数据的复杂度为 O(1)，而操作指针时可能为 O(N)：源节点（左子树中最右边的节点或右子树中最左边的节点）可能有一个孩子和它下面的一棵子树。与单个节点插入不同，在这种情况下需要合并子树。为了避免复制开销，应该存储指向对象的指针，而不是 BST 中的对象。

Answer 3

我认为这段代码可能很有洞察力并且很有帮助

代码首先递归搜索具有目标值的节点。

一旦找到要删除的节点，它会处理三种情况：无子节点、1个子节点和2个子节点。

  TreeNode *_deleteNode(TreeNode *root, int target) {
    if (!root)
      return nullptr;

    // first search about the target node by recursion
    if (target > root->val)
      root->right = _deleteNode(root->right, target);
    else if (target < root->val)
      root->left = _deleteNode(root->left, target);
    else {
    // if the current node == target, then 100% we gonna delete a node
      TreeNode *tmp{root};
      if (!root->left && !root->right) // target is leaf
        root = nullptr;
      else if (!root->left) // Only has right child
        root = root->right;
      else if (!root->right) // Only has left child
        root = root->left;
      else { // Has two childre
             // Get parent successor
        TreeNode *parentSuc{root}, *successor{root->right};

        while (successor && successor->left)
          parentSuc = successor, successor = successor->left;

        if (parentSuc == root) // if successor is directly my right child
          successor->left = root->left;

        else { // Then successor must be on my left as a parent
          if (!successor->left && !successor->right)
            parentSuc->left = nullptr;
          else
            parentSuc->left = successor->right;
          successor->left = root->left, successor->right = root->right;
        }
        root = successor;
      }
      if (tmp)
        delete tmp, tmp = nullptr;
    }
    return root;