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

左<=根<=右

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

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

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

在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树。

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