关于6-12中的一个疑问

Question

老师，删除二分搜索树的任意元素时，当待删除节点左右子树都不为空时，为什么要找到比待删除节点大的最小节点，而不是左右两边都找，然后比较一下这两个节点哪个距离待删除节点更近，再选择那个更近的节点来操作呢?为什么直接选择比它大的最接近它的节点呢？

Answer 1

liuyubobobo 2018-05-04 09:09:20

在我们的实现中，没有可比性。如果维护每个子树的高度，可以选择从子树高度高的那边删。但严格意义上，这个优化并不能完全保证让树的高度降低。二分搜索树最好的优化，依然是添加机制使其自维护为平衡二叉树。这个课程后续介绍的无论是AVL树还是红黑树，都拥有这种维护自平衡的机制：）

• yushou #1

  那老师的意思是删除左子树的最大节点和删除右子树的最小节点都可以是吗?

• yushou #2

  不好意思,问题时后面没看-_-!!!!

Answer 2

提问者 WhatsUpBitch 2018-05-04 00:22:38

老师，使用前驱或者后继节点在删除元素之后的效果是一样的，是不是说用这两个节点中的哪一个都是一样的，不能说前驱节点更好或者说后继节点更好，这两个节点是没有可比性的？

Answer 3

提问者 WhatsUpBitch 2018-05-03 23:58:02

老师，不用回答我这个问题了，我没看到这节的最后面。。。。看到最后面才发现从左子树找也可以的。。。

• liuyubobobo #1

  继续加油！：）