AVL删除元素
来源：12-7 从AVL树中删除元素
tom睡着了
2018-09-04
老师您好，在平衡二叉树可以添加重复值的节点的条件下，好像不可以复用remove(node, value)方法
在这种情况下是否只能使用removeMin()，并且在removeMin()中添加维护平衡的代码？
写回答
2回答
-
是的。我的课程中的二分搜索树，平衡二叉树，都是基于set或者map的假设，其中的值（map中的键值）不允许有重复。如果有重复元素，需要额外的处理（即是multiset）：）
印象里，在讲二分搜索树的时候，也相应的给大家留了这样一个思考问题，对于我们实现的二分搜索树，如何支持可以存储相同的元素，那么相应的，在AVL和红黑树的部分，有兴趣也可以思考同样的问题：）
你已经很精准的定位了问题，你需要保证在删除8的时候，找到的8的后继，是黄色的9，而不是绿色的9：）
P.S. 其实，在实践中，MultiSet并不是很有用，因为在需要存储重复元素的情况下，我们可以转而使用普通的Map，其中每一个键对应的值，即为这个键出现的次数。所以，在Java的标准库中，根本不提供MultiSet这样的一个数据结构！：）
加油！：）
112018-09-04 -
tom睡着了
提问者
2018-09-04
谢谢老师！回复的好快！
00
相似问题