关于6-12中的一个疑问

来源：6-12 删除二分搜索树的任意元素

WhatsUpBitch

2018-05-03

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

写回答

3回答

liuyubobobo

2018-05-04

已采纳

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

yushou

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

2018-06-09

共2条回复

WhatsUpBitch

提问者

2018-05-04

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

WhatsUpBitch

提问者

2018-05-03

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

liuyubobobo

继续加油！：）

2018-05-04

共1条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 1

回答 2

回答 2

回答 1

回答 1