当节点有两个子节点时在BST中删除

Question

我正在尝试删除BST中有两个子节点的节点.例如,

     |
    12
   /  \
  5    15
 / \     \
2   6    20

我想删除包含info = 12的节点.我需要帮助才能执行此操作.

Answer 1

您需要获得其左子树的最右边的子项,或者其右子树的最左子项(在您的示例中为6或15),并将其中一个移动到该位置,然后您可以删除您想要的节点.

如果您正在做任何事情来跟踪子树中的节点数,您通常希望从较大的子树中选择节点,因此当您移动它时,树将至少与开始时一样平衡. .例如,在这种情况下,最好得到6比15以帮助保持平衡 - 但如果你只有一个普通的,不平衡的BST,你可能没有这些信息很容易获得.