AVL删除元素

Question

老师您好，在平衡二叉树可以添加重复值的节点的条件下，好像不可以复用remove(node, value)方法

在这种情况下是否只能使用removeMin()，并且在removeMin()中添加维护平衡的代码？

Answer 1

liuyubobobo 2018-09-04 18:00:23

是的。我的课程中的二分搜索树，平衡二叉树，都是基于set或者map的假设，其中的值（map中的键值）不允许有重复。如果有重复元素，需要额外的处理（即是multiset）：）

印象里，在讲二分搜索树的时候，也相应的给大家留了这样一个思考问题，对于我们实现的二分搜索树，如何支持可以存储相同的元素，那么相应的，在AVL和红黑树的部分，有兴趣也可以思考同样的问题：）

你已经很精准的定位了问题，你需要保证在删除8的时候，找到的8的后继，是黄色的9，而不是绿色的9：）

P.S. 其实，在实践中，MultiSet并不是很有用，因为在需要存储重复元素的情况下，我们可以转而使用普通的Map，其中每一个键对应的值，即为这个键出现的次数。所以，在Java的标准库中，根本不提供MultiSet这样的一个数据结构！：）

加油！：）

• 提问者 tom睡着了 #1

  谢谢老师！回复的好快！

Answer 2

提问者 tom睡着了 2018-09-04 18:02:01

谢谢老师！回复的好快！