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

左<根<=右

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

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

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

元素排序关系<=是一个总顺序，因此关系必须是自反的，但通常二叉搜索树(又名BST)是一个没有重复的树。

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

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

左<=根<=右

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

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

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

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

所有这三个定义都是可以接受和正确的。它们定义了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)

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