java 有重复的 BST
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16727871/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
BST with duplicates
提问by user
I know that, BSTdoes not allow duplicates. For example, if I have a word "RABSAB".
我知道，BST不允许重复。例如，如果我有一个词“RABSAB”。
The Binary search tree for the above string is:
上述字符串的二叉搜索树是：
R
/\
A S
\
B
What if we wanted to include the duplicates in the tree. How the tree gonna change? I was asked this question in an interview.
如果我们想在树中包含重复项怎么办。树怎么变？我在一次采访中被问到这个问题。
They asked me to draw:
他们让我画：
- a binary tree
- an unbalanced Binary Search Tree
- a binary search tree without duplicates
- a binary search tree with duplicates
- 二叉树
- 不平衡的二叉搜索树
- 没有重复的二叉搜索树
- 具有重复项的二叉搜索树
Any Help is appreciated!
任何帮助表示赞赏！
PS: Help me by drawing the related trees
PS：通过绘制相关树来帮助我
回答by Sazzadur Rahaman
Rule to insert in a binary Search tree without duplicate is:
在没有重复的二叉搜索树中插入的规则是：
- Go left if element is less than root
- Go right if the element is greater than root.
- 如果元素小于根，则向左
- 如果元素大于根，则向右走。
And to allow duplicate entries you have to modify the rule like bellow:
要允许重复条目，您必须修改规则，如下所示：
- Go left if the element is less or equal root
- Go right if the element is greater than root.
- 如果元素小于或等于根，则向左
- 如果元素大于根，则向右走。
or
或者
- Go left if the element is less than root
- Go right if the element is greater or equal root.
- 如果元素小于根，则向左
- 如果元素大于或等于根，则向右走。
or
或者
- Go left if the element is less than root
- Go right if the element is greater than root.
- Increase the count if the element is equal to the root.
- 如果元素小于根，则向左
- 如果元素大于根，则向右走。
- 如果元素等于根，则增加计数。
So your BSTfor word "RABSAB", with duplicates can be like:
所以你BST的单词"RABSAB"，重复可能是这样的：
R
/ \
A S
/ \
A B
/
B
Or,
或者，
R
/ \
A S
\
A
\
B
\
B
or
或者
R(1)
/ \
/ \
A(2) S(1)
\
\
B(2)
In First two cases, both insertion and search becomes bit complex! You will find it herewith great deal of explanation!
在前两种情况下，插入和搜索都变得有点复杂！你会在这里找到大量的解释！
And the third case is somewhat easier to maintain.
第三种情况更容易维护。
All of them are used successfully to allow duplicates, now the choice is yours!
所有这些都已成功使用以允许重复，现在选择权在您手中！
回答by Zim-Zam O'Pootertoot
One option is to modify the tree so that one branch will include the duplicates, for example have the left branches hold nodes that are less than or equal to the parent, alternatively have the right branches hold nodes that are greater than or equal to the parent
一种选择是修改树，以便一个分支将包含重复项，例如让左分支保存小于或等于父节点的节点，或者让右分支保存大于或等于父节点的节点
Another option is to store all duplicates in a node, so instead of
另一种选择是将所有重复项存储在一个节点中，而不是
class Node {
Node left, right;
Object data;
}
you would instead have
你会有
class Node {
Node left, right;
List data;
}
or
或者
class Node {
Node left, right;
Object data;
int count;
}
回答by amitdonanand
In a normal BST insertion and search both occur based on less than(>) and greater than (<) rule.
在正常的 BST 插入和搜索中，都基于小于（>）和大于（<）规则。
You could instead try insertion on less than equal to (>=) or greater than equal to (<=) and try using the same rule for searching.
您可以改为尝试插入小于等于 (>=) 或大于等于 (<=) 并尝试使用相同的搜索规则。
Alternatively you could include an array in every node to accommodate duplicate elements.
或者，您可以在每个节点中包含一个数组以容纳重复元素。
回答by Deepu
For your input RABPAB, You can create a BSTby using a LIST to store all the equal valued keys. All the equal valued keys are placed in the same level using a data structure capable of storing it.
对于您的输入RABPAB，您可以BST通过使用 LIST 来存储所有等值键来创建一个。所有等值的键都使用能够存储它的数据结构放置在同一级别。
The BST will look something like this,
BST 看起来像这样，
R
/ \
A--A P
\
B--B
The Java code for your BST storing integer values could be like this,
您的 BST 存储整数值的 Java 代码可能是这样的，
class Node
{
Node left, right;
int data[maxvalue];
}
Here maxvalueis the maximum possible equal valued keys.
这maxvalue是最大可能的等值键。
