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

你说的三件事都是真的。

密钥是唯一的 左边是比这个小的键 右边是比这个大的键

我想你可以把你的树倒过来，把较小的键放在右边，但实际上“左”和“右”的概念只是:一个可视化的概念，帮助我们思考一个没有真正的左或右的数据结构，所以这并不重要。

在BST中，节点左侧降序的所有值都小于(或等于，稍后将讨论)节点本身。类似地，节点右侧降序的所有值都大于(或等于)该节点值(a)。

一些bst可能会选择允许重复值，因此上面有“或等于”限定符。下面的例子可以说明:

     14
    /  \
  13    22
 /     /  \
1    16    29
          /  \
        28    29

这显示了一个允许重复的BST (b) -您可以看到，要查找一个值，您可以从根节点开始，根据您的搜索值是否小于或大于节点值，沿着左或右子树向下查找。

这可以用类似这样的东西递归完成:

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)

重复增加了一些复杂性，因为在找到值之后，您可能需要继续搜索具有相同值的其他节点。显然，这对hasVal来说并不重要，因为它不关心有多少个，只关心是否至少存在一个。然而，对于countVal之类的东西，这很重要，因为它需要知道有多少个。

(a)如果你调整了搜索特定键的方式，你可以按照相反的方向对它们进行排序。BST只需要保持某种排序顺序，无论是升序还是降序(甚至是一些奇怪的多层排序方法，如所有奇数升序，然后所有偶数降序)都无关紧要。

(b)有趣的是，如果你的排序键使用存储在一个节点上的整个值(这样包含相同键的节点就没有其他额外的信息来区分它们)，向每个节点添加一个计数可以提高性能，而不是允许重复的节点。

这样做的主要好处是，添加或删除副本只会修改计数，而不是插入或删除新节点(这一操作可能需要重新平衡树)。

因此，要添加一个项目，首先要检查它是否已经存在。如果是，增加计数并退出。如果不是，则需要插入一个新节点，其计数为1，然后重新平衡。

要删除一个项，您找到它，然后递减计数-只有当结果计数为零时，您才从树中删除实际节点并重新平衡。

考虑到节点更少，搜索也会更快，但这可能不会产生太大影响。

例如，下面两棵树(左边的非计数树和右边的计数树)是等价的(在计数树中，i.c表示i项的c个副本):

     __14__                    ___22.2___
    /      \                  /          \
  14        22             7.1            29.1
 /  \      /  \           /   \          /    \
1    14  22    29      1.1     14.3  28.1      30.1
 \            /  \
  7         28    30

从左侧树中移除叶节点22将涉及重新平衡(因为它现在有两个高度差)所产生的22-29-28-30子树，如下所示(这是一个选项，还有其他选项也满足“高度差必须为0或1”规则):

\                      \
 22                     29
   \                   /  \
    29      -->      28    30
   /  \             /
 28    30         22

在右边的树上执行相同的操作，只需将根节点从22.2修改为22.1(不需要重新平衡)。

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

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

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

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

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

编辑:

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

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

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

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

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

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

左<根<=右

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

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

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

左<=根<=右

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

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

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

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的不同变体。

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

当然，允许复制会增加复杂性。如果你使用定义"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)

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

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

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

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

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

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

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

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

左<= 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树。