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

左<=根<=右

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

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

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

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

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

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

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

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

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

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。