关于BST和AVL存储重复元素的问题
来源：12-5 左旋转和右旋转的实现
慕哥8233928
2020-01-29
BOBO老师，有两个问题望不吝赐教，感谢：
第一个问题：关于二叉搜索树，如果要支持存储重复的元素，是不是只要定义个一个规则，例如左子树的值都小于当前节点，右子树的值都大于等于当前节点(也就是说重复的元素向右子树添加)，然后在插入元素的时候按照这个准则就可以了？如果存储重复的元素，我用纸笔简单画了一下，是不是对于floor和ceil的实现与没有重复元素的场景是一致的？
第二个问题：如果支持重复元素的话，AVL树的旋转操作该如何处理呢？比如我依然按照左子树的值都小于当前节点，右子树的值都大于等于当前节点(也就是说重复的元素向右子树添加)，如果为了维持平衡进行旋转，貌似就无法满足二叉搜索树的条件了，这个没太想好是怎样处理？
写回答
1回答
-
1
对。但其实更简单的方式是，在节点中添加一个值：count，记录这个节点代表的元素在整棵树中存储了多少个。当然，这样做以后，删除的逻辑也需要改变一下，删除首先是对应节点的 count 值 --，如果为 0，再删除该节点。我通常都会这样处理重复元素：）
2
我上面说的方案，可以完美解决这个问题。对旋转操作没有任何影响。
继续加油！：）
012020-01-29
相似问题