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)是一个没有重复的树。

否则，如果有重复你需要运行两次或更多相同的功能删除!

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

左<=根<=右

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

所有这三个定义都是可以接受和正确的。它们定义了BST的不同变体。

你的大学数据结构的书没有说明它的定义不是唯一可能的。

当然，允许复制会增加复杂性。如果你使用定义"left <= root < right"，你有一个这样的树:

      3
    /   \
  2       4

然后在这个树中添加一个重复的“3”键将导致:

      3
    /   \
  2       4
    \
     3

注意，副本不是连续的级别。

当允许像上面那样的BST表示中的副本时，这是一个大问题:副本可以被任意数量的层分隔，因此检查副本的存在并不像检查节点的直接子节点那么简单。

避免此问题的一个选项是不从结构上表示重复项(作为单独的节点)，而是使用一个计数器来计算键出现的次数。前面的例子会有一个这样的树:

      3(1)
    /     \
  2(1)     4(1)

在插入重复的"3"键后，它将变成:

      3(2)
    /     \
  2(1)     4(1)

这简化了查找、删除和插入操作，但牺牲了一些额外的字节和计数器操作。

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

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

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

许多算法将指定排除重复项。例如，麻省理工学院算法书中的示例算法通常会给出没有重复的示例。实现副本相当简单(在节点上作为列表，或者在一个特定方向上)。

大多数(我见过的)将左子节点指定为<=，右子节点指定为>。实际上，允许右子节点或左子节点中的任何一个等于根节点的BST将需要额外的计算步骤来完成允许重复节点的搜索。

最好利用节点上的列表来存储重复项，因为在节点的一侧插入'='值需要重写这一侧的树以将该节点作为子节点，或者将该节点作为子节点放置在下面的某个位置，这降低了一些搜索效率。

你必须记住，大多数课堂上的例子都是为了描述和传达概念而简化的。在现实世界的许多情况下，它们一文不值。但是，“每个元素都有一个键，并且没有两个元素具有相同的键”这句语句不会因为在元素节点上使用列表而违反。

所以按照你的数据结构书上说的去做吧!

编辑:

二叉搜索树的通用定义涉及基于在两个方向之一遍历数据结构的基础上存储和搜索键。从实际意义上讲，这意味着如果值<>，则在两个“方向”之一遍历数据结构。所以，在这种情况下，重复的值没有任何意义。

这与BSP或二进制搜索分区不同，但也不是完全不同。搜索算法有两个“旅行”方向之一，否则它就完成了(成功与否)。所以我很抱歉，我最初的答案没有解决“通用定义”的概念，因为重复的内容实际上是一个不同的主题(在成功搜索之后处理的内容，而不是作为二分搜索的一部分)。