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

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

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

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

你说的三件事都是真的。

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

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

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

左<=根<=右

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

所有这三个定义都是可以接受和正确的。它们定义了BST的不同变体。

你的大学数据结构的书没有说明它的定义不是唯一可能的。

当然，允许复制会增加复杂性。如果你使用定义"left <= root < right"，你有一个这样的树:

      3
    /   \
  2       4

然后在这个树中添加一个重复的“3”键将导致:

      3
    /   \
  2       4
    \
     3

注意，副本不是连续的级别。

当允许像上面那样的BST表示中的副本时，这是一个大问题:副本可以被任意数量的层分隔，因此检查副本的存在并不像检查节点的直接子节点那么简单。

避免此问题的一个选项是不从结构上表示重复项(作为单独的节点)，而是使用一个计数器来计算键出现的次数。前面的例子会有一个这样的树:

      3(1)
    /     \
  2(1)     4(1)

在插入重复的"3"键后，它将变成:

      3(2)
    /     \
  2(1)     4(1)

这简化了查找、删除和插入操作，但牺牲了一些额外的字节和计数器操作。