关于BST和AVL存储重复元素的问题

Question

BOBO老师，有两个问题望不吝赐教，感谢：
第一个问题：关于二叉搜索树，如果要支持存储重复的元素，是不是只要定义个一个规则，例如左子树的值都小于当前节点，右子树的值都大于等于当前节点(也就是说重复的元素向右子树添加)，然后在插入元素的时候按照这个准则就可以了？如果存储重复的元素，我用纸笔简单画了一下，是不是对于floor和ceil的实现与没有重复元素的场景是一致的？
第二个问题：如果支持重复元素的话，AVL树的旋转操作该如何处理呢？比如我依然按照左子树的值都小于当前节点，右子树的值都大于等于当前节点(也就是说重复的元素向右子树添加)，如果为了维持平衡进行旋转，貌似就无法满足二叉搜索树的条件了，这个没太想好是怎样处理？

Answer 1

liuyubobobo 2020-01-29 13:41:59

1

对。但其实更简单的方式是，在节点中添加一个值：count，记录这个节点代表的元素在整棵树中存储了多少个。当然，这样做以后，删除的逻辑也需要改变一下，删除首先是对应节点的 count 值 --，如果为 0，再删除该节点。我通常都会这样处理重复元素：）

2

我上面说的方案，可以完美解决这个问题。对旋转操作没有任何影响。

继续加油！：）

• 提问者 慕哥8233928 #1

  非常感谢！