我只是想为罗伯特·保尔森的回答补充一些信息。

假设节点包含键和数据。因此具有相同键的节点可能包含不同的数据。 (因此搜索必须找到具有相同键的所有节点)

左<= cur <右

左< cur <=右

左<= cur <= right

左< cur <右&& cur包含具有相同键的兄弟节点。

左< cur <右，这样就不存在重复的键。

1 & 2. works fine if the tree does not have any rotation-related functions to prevent skewness. But this form doesn't work with AVL tree or Red-Black tree, because rotation will break the principal. And even if search() finds the node with the key, it must traverse down to the leaf node for the nodes with duplicate key. Making time complexity for search = theta(logN) 3. will work well with any form of BST with rotation-related functions. But the search will take O(n), ruining the purpose of using BST. Say we have the tree as below, with 3) principal.

         12
       /    \
     10     20
    /  \    /
   9   11  12 
      /      \
    10       12

如果我们在这棵树上搜索(12)，即使我们在根结点上找到了12，我们也必须同时搜索左子结点和右子结点来寻找重复的键。 这需要O(n)个时间。 4. 是我个人的最爱。兄弟节点是指具有相同键的节点。 我们可以把上面的树变成下面的树。

         12 - 12 - 12
       /    \
10 - 10     20
    /  \
   9   11

现在任何搜索都需要O(logN)因为我们不需要遍历重复的子键。 这个原理也适用于AVL和RB树。

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

左<根<=右

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

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

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

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

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

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

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

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

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

编辑:

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

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

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

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

左<=根<=右

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