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

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

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

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

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

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

编辑:

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

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

在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(不需要重新平衡)。

你说的三件事都是真的。

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

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

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

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