你说的三件事都是真的。

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

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

你说的三件事都是真的。

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

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

元素排序关系<=是一个总顺序，因此关系必须是自反的，但通常二叉搜索树(又名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。