Duplicate Keys • What happens if there's more than one data item with the same key? – This presents a slight problem in red-black trees. – It's important that nodes with the same key are distributed on both sides of other nodes with the same key. – That is, if keys arrive in the order 50, 50, 50, • you want the second 50 to go to the right of the first one, and the third 50 to go to the left of the first one. • Otherwise, the tree becomes unbalanced. • This could be handled by some kind of randomizing process in the insertion algorithm. – However, the search process then becomes more complicated if all items with the same key must be found. • It's simpler to outlaw items with the same key. – In this discussion we'll assume duplicates aren't allowed

可以为树的每个节点创建包含重复键的链表，并将数据存储在列表中。

在使用红黑树实现时，我遇到了用多个键验证树的问题，直到我意识到使用红黑插入旋转时，必须放松对的约束

左<=根<=右

由于我所查看的任何文档都不允许重复键，而且我不想重写旋转方法来解释它，所以我决定修改节点以允许节点内的多个值，并且树中不允许重复键。

任何定义都是有效的。只要在实现中保持一致(总是把相等的节点放在右边，总是把它们放在左边，或者不允许它们这样做)，那么就没问题。我认为不允许它们是最常见的，但如果允许它们并放置在左边或右边，它仍然是一个BST。

在Cormen、Leiserson、Rivest和Stein合著的《算法介绍》第三版中，二叉搜索树(BST)被明确定义为允许重复。这可以从图12.1和以下(第287页)中看到:

二叉搜索树中的键总是以满足二叉搜索树属性的方式存储:设x是二叉搜索树中的一个节点。如果y是x的左子树中的一个节点，则y:key <= x:key。如果y是x的右子树中的一个节点，那么y:key >= x:key。”

此外，红黑树在308页被定义为:

红黑树是一种二叉搜索树，每个节点有一个额外的存储位:它的颜色。

因此，本书定义的红黑树支持重复。

1.)左<=根<右 2.)左<根<=右 3.)左<根<右，这样就不存在重复的键。

我可能要去翻出我的算法书籍，但我的头脑中(3)是标准形式。

(1)或(2)只在你开始允许重复的节点并且你把重复的节点放在树本身(而不是包含列表的节点)时才会出现。

如果您的二叉搜索树是红黑树，或者您打算进行任何类型的“树旋转”操作，重复的节点将导致问题。假设你的树规则是这样的:

左<根<=右

现在想象一个简单的树，它的根是5，左子结点是nil，右子结点是5。如果你在根结点上做一个左旋转你会在左子结点中得到一个5在根结点中得到一个5而右子结点为nil。现在左树中的某个元素等于根结点，但上面的规则假设左<根结点。

我花了几个小时试图弄清楚为什么我的红/黑树偶尔会乱序，问题就是我上面描述的。希望有人读了这篇文章，将来可以节省调试的时间!