BST有重复

我知道， BST不允许重复。 例如，如果我有一个单词“RABSAB”。

上述字符串的二进制搜索树是：

  R /\ AS \ B 

如果我们想在树中包含重复项，该怎么办？ 树怎么会改变？ 我在接受采访时被问到这个问题。

他们让我画画：

1. 二叉树
2. 不平衡的二进制搜索树
3. 没有重复的二叉搜索树
4. 带有重复项的二叉搜索树

任何帮助表示赞赏！

PS：通过绘制相关树帮助我

Answer 1

在没有重复的二进制搜索树中插入的规则是：

1. 如果元素小于root，则向左移动
2. 如果元素大于root，则向右移动。

要允许重复条目，您必须修改规则，如下：

1. 如果元素小于或等于root，则向左移动
2. 如果元素大于root，则向右移动。

要么

1. 如果元素小于root，则向左移动
2. 如果元素大于或等于root，则向右移动。

要么

1. 如果元素小于root，则向左移动
2. 如果元素大于root，则向右移动。
3. 如果元素等于根，则增加计数。

所以您的BST单词“RABSAB” ，带有重复项可以像：

  R / \ AS / \ AB / B 

要么，

  R / \ AS \ A \ B \ B 

要么

  R(1) / \ / \ A(2) S(1) \ \ B(2) 

在前两种情况下，插入和搜索都变得有点复杂！ 你会在这里找到很多解释！

第三种情况更容易维护。

所有这些都成功地用于允许重复，现在选择是你的！

Answer 2

一种选择是修改树，以便一个分支将包含重复项，例如让左分支保存小于或等于父项的节点，或者使右分支保存大于或等于父项的节点

另一种选择是将所有重复项存储在节点中，而不是

 class Node { Node left, right; Object data; } 

你会反而拥有

 class Node { Node left, right; List data; } 

要么

 class Node { Node left, right; Object data; int count; } 

Answer 3

在正常的BST插入和搜索中，两者都基于小于（>）和大于（<）规则发生。

您可以尝试插入小于等于（> =）或大于等于（<=）并尝试使用相同的规则进行搜索。

或者，您可以在每个节点中包含一个数组以容纳重复元素。

Answer 4

对于输入RABPAB ，您可以使用LIST创建BST来存储所有等值键。 使用能够存储它的数据结构将所有等值键放置在同一级别中。

BST看起来像这样，

  R / \ A--AP \ B--B 

存储整数值的BST的Java代码可能是这样的，

 class Node { Node left, right; int data[maxvalue]; } 

这里maxvalue是最大可能的等值键。