我正在尝试寻找二叉搜索树的定义，但无论在哪里都找到了不同的定义。
有人说对于任何给定的子树，左子节点的键小于或等于根。
有些人说对于任何给定的子树，右子节点的键大于或等于根。
而我的老大学数据结构书上说“每个元素都有一个键，没有两个元素拥有相同的键。”
是否有一个通用的BST定义？特别是关于如何处理具有多个相同键的树。
编辑：也许我表达不够清楚，我看到的定义是：
1）left <= root < right
2）left < root <= right
3）left < root < right，其中不存在重复的键。
left <= node <= right，或仅在值的第一次出现之前插入。 - paxdiablo<= <= 的问题在于你基本上破坏了首先拥有 BST 的主要目的之一：对已排序集合进行快速操作。除非你按照 Rich 所说的做法或者将所有重复项放入同一个节点中，否则你将不得不遍历整个树，可能要一直遍历到底部才能检查是否存在任何重复项。 - Andrew所有三个定义都是可接受和正确的。它们定义了BST的不同变体。
你们学院的数据结构书没有澄清它的定义不是唯一可能的。
当然，允许重复项会增加复杂性。如果你使用定义“左<=根<右”，并且你有这样一棵树:
3
/ \
2 4
然后将一个“3”重复键添加到这棵树中，结果为：
3
/ \
2 4
\
3
请注意，重复项不在连续的层级中。
当允许在上述BST表示中有重复项时，这是一个较大的问题：重复项可能由任意数量的级别分隔，因此检查重复项的存在并不像仅检查节点的直接子节点那样简单。
避免此问题的一种选项是不将重复项结构化表示（作为单独的节点），而是使用计数器来计算密钥的出现次数。则先前的示例将具有以下类似的树：
3(1)
/ \
2(1) 4(1)
在插入重复的"3"键之后，它将变为：
3(2)
/ \
2(1) 4(1)
这简化了查找、删除和插入操作，但会牺牲一些额外的字节和计数操作。
在二叉搜索树（BST）中，节点左侧下降的所有值都小于（或等于，稍后查看）该节点本身。同样，节点右侧下降的所有值都大于（或等于）该节点值(a)。
一些BST可能选择允许重复的值，因此上面的“或等于”限定符。以下示例可能会更清楚：
14
/ \
13 22
/ / \
1 16 29
/ \
28 29
这显示了一个允许重复的二叉搜索树(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)有趣的是，如果您的排序键使用存储在节点中的完整值（以便包含相同键的节点没有其他额外信息来区分它们），则添加每个节点的计数可能会带来性能提升，而不是允许重复节点。
主要好处是添加或删除副本将仅修改计数，而不是插入或删除新节点（这可能需要重新平衡树）。
因此，要添加项，您首先需要检查它是否已经存在。如果是，则只需增加计数并退出。如果没有，则需要插入一个计数为一的新节点，然后重新平衡。
要删除项，您找到它然后减少计数 - 仅当结果计数为零时，才从树中删除实际节点并重新平衡。
给定较少的节点，搜索也会更快，但这可能不会有很大的影响。
例如，以下两棵树（左侧为非计数树，右侧为计数树）将是等价的（在计数树中，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需要重新平衡（因为它现在的高度差为2），这将涉及到重新平衡结果为22-29-28-30子树，如下所示（这是一个选项，还有其他选项也符合“高度差必须为零或一”的规则）：
\ \
22 29
\ / \
29 --> 28 30
/ \ /
28 30 22
对右子树执行相同的操作只需要将根节点从22.2修改为22.1（无需重新平衡）。
>= 比较，只有一组重复数据的最左节点可以成为父节点（从而确保所有节点都是右子节点）；如果有许多相同的重复数据，则可能导致灾难性的树。 - Andrew此外，在第308页中定义了红黑树为“带有每个节点一位额外存储空间的二叉搜索树：它的颜色”，因此，在此书中定义的红黑树支持重复项。“二叉搜索树中的键始终以满足二叉搜索树属性的方式存储：设
x是二叉搜索树中的一个节点。如果y是x左子树中的一个节点，则y:key <= x:key。如果y是x右子树中的一个节点，则y:key >= x:key。”
任何定义都是有效的。只要您在实现中保持一致（始终将相等节点放置到右侧，始终将它们放置到左侧或永远不允许它们），那么就可以了。我认为最常见的做法是不允许它们存在，但如果它们被允许并且被放置在左侧或右侧，则仍然是BST。
我想在 @Robert Paulson 的回答中添加一些信息。
假设节点包含键和数据。因此，具有相同键的节点可能包含不同的数据。（因此搜索必须找到所有具有相同键的节点）
- left <= cur < right
- left < cur <= right
- left <= cur <= right
- left < cur < right && cur 包含具有相同键的 兄弟节点。
- left < cur < right，且不存在重复的键。
1和2. 如果树没有任何旋转相关的函数来防止倾斜，则可以正常工作。
但这种形式不能与 AVL树 或 Red-Black树 一起使用，因为旋转会破坏原则。
即使 search() 找到具有该键的节点，它也必须遍历到叶节点以获取具有重复键的节点。
搜索的时间复杂度为theta(logN)
3. 将适用于任何具有旋转相关函数的 BST。
但搜索将花费O(n)，破坏使用BST的目的。
假设我们拥有以下树，具有 3) 原则。
12
/ \
10 20
/ \ /
9 11 12
/ \
10 12
12 - 12 - 12
/ \
10 - 10 20
/ \
9 11
left <= root <= right
由于我查看的所有文档都不允许重复键，而我又不想重新编写旋转方法以解决此问题，因此我决定修改我的节点以允许节点内部具有多个值且树中没有重复的键。
你说的这三件事都是真的。
我想你可以反转你的树，把更小的键放在右边，但实际上，“左”和“右”的概念只是一个视觉概念，帮助我们思考一个没有左或右的数据结构，所以它并不重要。
>=存在。"理想" 取决于你的需求，但是如果你有很多重复的值，并且允许这些重复的值存在于结构中，你的二叉搜索树可能会变成线性的 - 即O(n)。 - Robert Paulson
{num = 1, count 5}。我认为这对于基本数据类型和字符串来说很有效，但对于其他非原始数据类型则不适用。 - k4anubhav