在二叉search树的定义中是否允许重复键？
我试图find一个二叉search树的定义，我一直在find不同的定义。
有人说，对于任何给定的子树，左侧的子键小于或等于根。
有人说，对于任何给定的子树，正确的子键大于或等于根。
而我以前的大学数据结构书说：“每个元素都有一个关键，没有两个元素具有相同的关键”。
有没有bst的普遍定义？ 特别是关于如何处理具有相同密钥的多个实例的树。
编辑：也许我不清楚，我看到的定义是
1）left <= root <right
2）左<root <=右
3）左<root <右，这样不存在重复的键。
许多algorithm将指定排除重复项。 例如，“MITalgorithm”书中的示例algorithm通常会提供没有重复的示例。 实现重复是相当简单的（无论是作为节点上的列表，还是作为一个特定的方向）。
大多数（我见过）指定左边的孩子为<=，右边的孩子为>。 实际上，允许右侧或左侧儿童等于根节点的BST将需要额外的计算步骤来完成允许重复节点的search。
最好利用节点上的列表来存储重复项，因为向节点的一侧插入'='值需要重写该节点上的树以将该节点作为子节点，或者该节点被放置为macros – 在下面的某个点，这消除了一些search效率。
你必须记住，大部分课堂的例子都被简化来描述和传达这个概念。 在许多现实世界中，它们不值得蹲下。 但是，声明“每个元素都有一个键，没有两个元素具有相同的键”，并不违反在元素节点处使用列表。
所以去你的数据结构书所说的！
编辑：
二叉search树的通用定义涉及基于在两个方向中的一个方向上遍历数据结构来存储和search密钥。 在实用意义上，这意味着如果值是<>，则可以在两个“方向”之一中遍历数据结构。 所以，在这个意义上说，重复的价值根本就没有任何意义。
这与BSP或二进制search分区不同，但并不完全相同。 searchalgorithm有两个“旅行”方向之一，或者成功（或不成功）。所以我很抱歉，我的原始答案没有解决“通用定义”的概念，因为重复是一个独特的主题（成功search后处理的内容，而不是二进制search的一部分）。
如果你的二叉search树是一棵红黑树，或者你打算进行任何一种“树轮”操作，重复的节点将会引起问题。 想象一下你的树规则是这样的：
左<root <=右
现在设想一个简单的树，它的根是5，左边的孩子是零，右边的孩子是5.如果你做一个左旋转的根，你最终在左边的孩子5和右边的孩子5根没有。 现在左树中的东西等于根，但是你上面的规则假定左<root。
我花了好几个小时试图弄清楚为什么我的红/黑树偶尔会出现乱序问题，这个问题就是我上面所说的。 希望有人读这个节省自己的时间debugging在未来几个小时！
在BST中，节点左侧下降的所有值小于（或等于，稍后参见）节点本身。 类似地，节点右侧下降的所有值都大于（或等于）节点值（a） 。
一些BST可能会select允许重复值，因此上面的“或等于”限定符。
以下例子可能会澄清：
| +--- 14 ---+ | | +--- 13 +--- 22 ---+ | | | 1 16 +--- 29 ---+ | | 28 29
这显示了允许重复的BST – 您可以看到要查找值，您从根节点开始，根据search值是小于还是大于节点值，沿着左侧或右侧子树向下。
这可以用类似下面的方法recursion地完成：
def hasVal (node, srchval): if node == NULL: return false if node.val == srchval: return true if node.val > srchval: return hasVal (node.left, srchval) return hasVal (node.right, srchval)
并用以下方式调用它：
foundIt = hasVal (rootNode, valToLookFor)
复制会增加一点复杂性，因为您可能需要在find相同值的其他节点的值后继续search。
（a）如果您调整了search特定键的方式，您可以按照相反的方向对它们进行sorting。 BST只需要维护一些sorting顺序，无论是升序还是降序都不相关。
所有三个定义都是可以接受和正确的 他们定义了BST的不同变化。
你的大学数据结构的书没有说明它的定义不是唯一可能的。
当然，允许重复增加了复杂性。 如果使用定义“left <= root <right”，并且您有一棵树，如：
3 / \ 2 4
然后向这棵树添加一个“3”重复键将导致：
3 / \ 2 4 \ 3
请注意，重复项不在连续的级别。
这是一个很大的问题，当允许重复在上面的BST表示时：重复可以被任意数量的级别分开，因此检查重复的存在并不像检查节点的直接子节点那么简单。
避免这个问题的一个select是在结构上不表示重复（作为单独的节点），而是使用计数器来计算密钥的出现次数。 之前的例子会有一个像这样的树：
3(1) / \ 2(1) 4(1)
并在插入复制的“3”键后将变成：
3(2) / \ 2(1) 4(1)
这简化了查找，删除和插入操作，代价是一些额外的字节和计数器操作。
在红黑树的实现上，我得到了用多个键validation树的问题，直到我意识到在红黑插入旋转的情况下，你必须将约束
left <= root <= right
由于我没有看到的文档允许重复的键，我不想重写旋转方法来解决它，我只是决定修改我的节点，以允许节点内的多个值，并没有重复的键那个树。
任何定义都是有效的。 只要你在你的实现中一致（总是把相等的节点放在正确的位置，总是把它们放在左边，或者永远不要让它们），那么你没事。 我认为不允许他们是最常见的，但是如果他们被允许并放置在左边或右边，它仍然是BST。
你说的三件事情都是真的。
- 钥匙是独特的
- 在左边是比这个更less的键
- 右边是比这个更大的键
我想你可以把你的树倒过来放在右边，但是实际上“左”和“右”的概念就是：一个视觉概念，帮助我们思考一个没有剩下的数据结构或对，所以这并不重要。
在Cormen，Leiserson，Rivest和Stein的“algorithm导论”第三版中，二叉search树（BST）被明确定义为允许重复 。 这可以在图12.1和下面（第287页）中看到：
“二叉search树中的键总是以满足二叉search树属性的方式存储：令
x是二叉search树中的一个节点，如果y是x的左子树中的一个节点，则y:key <= x:key。如果y是x的右子树中的一个节点，则y:key >= x:key。
另外，在308页上定义红黑树，如下：
“红黑树是一个二叉search树，每个节点有一个额外的存储位：它的颜色”
因此，本书定义的红黑树支持重复。
1.）left <= root <right
2）左<root <=右
3.）left <root <right，这样不存在重复的键。
我可能不得不去挖掘我的algorithm书籍，但是我的头顶（3）是规范的forms。
（1）或（2）只有当你开始允许重复的节点， 并把重复的节点放在树本身（而不是包含一个列表的节点）时才会出现。
元素顺序关系<=是一个总顺序，所以关系必须是自反的，但通常二叉search树（aka BST）是没有重复的树。
否则，如果有重复，你需要运行两次或更多相同的删除function！
重复密钥•如果有多个数据项使用相同的密钥，会发生什么情况？ – 这在红黑树上呈现出一个小问题。 – 具有相同密钥的节点分布在具有相同密钥的其他节点的两侧是很重要的。 – 也就是说，如果按键的顺序是50,50,50，您希望第二个50到第一个的右边，第三个50到第一个的左边。 否则，树变得不平衡。 这可以通过插入algorithm中的某种随机过程来处理。 – 但是，如果必须find所有具有相同密钥的项目，则search过程变得更加复杂。 •使用相同的钥匙取缔物品会更简单。 – 在这个讨论中，我们假设重复是不允许的
可以为包含重复键的树的每个节点创build一个链表，并将数据存储在列表中。
