data-structures - 从具有重复项的 BST 中删除具有左右子树的节点

Question

DSA 书描述了从二叉搜索树中删除节点的这种情况：

“4. 要删除的值同时具有左子树和右子树，在这种情况下，我们提升左子树中的最大值。”

假设我们有以下内容（我试图让它看起来像一棵树）：

      7
  6       8
5   6       8

如果我们删除根 (7)，它说我们应该把 6 放到它的位置。现在看起来像这样（只是感觉不对）：

      6
  6       8
5           8

现在 6 是 6 的左节点。但它不应该，对（左边的值应该更小）？所以，我想我的问题是：有这样的情况可以吗？如果这种情况是可以接受的，那有什么名字吗？或者我们应该选择其他一些节点来代替被删除的节点？

Answer 1

您是否假设所有“相等”的值都在正确的子树中？如果是这样，您总是可以用它的右子树中的最小值替换节点。如果他们可以在任何一方，那么你没有问题。