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

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

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

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

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

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

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

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

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。