我试图找到二叉搜索树的定义，并且我一直在寻找不同的定义 .
有人说，对于任何给定的子树，左子键小于或等于根 .
有人说，对于任何给定的子树，右子键大于或等于根 .
我的旧大学数据结构书中说“每个元素都有一个键，没有两个元素具有相同的键 . ”
是否存在bst的通用定义？特别是关于如何处理具有相同密钥的多个实例的树 .
编辑：也许我不清楚，我看到的定义是
1）左<= root <右
2）左<root <=右
3）左<root <右，这样就不存在重复的密钥 .
许多算法将指定排除重复项 . 例如，MIT算法书中的示例算法通常提供没有重复的示例 . 实现重复（在节点上或在一个特定方向上作为列表）是相当简单的 . ）
大多数（我见过）将左边的孩子指定为<=，将右边的孩子指定为> . 实际上，允许右子节点或左子节点等于根节点的BST将需要额外的计算步骤来完成允许重复节点的搜索 .
最好利用节点上的列表来存储重复项，因为在节点的一侧插入'='值需要重写该侧的树以将节点作为子节点放置，或者节点放置为宏-child，在某些点下面，这消除了一些搜索效率 .
您必须记住，大多数课堂示例都经过简化，以描绘和传达概念 . 在许多现实世界的情况下，他们不值得蹲下 . 但是声明“每个元素都有一个键，没有两个元素具有相同的键”，在元素节点上使用列表不会违反 .
那么请关注您的数据结构书所说的内容！
编辑：
二进制搜索树的通用定义涉及基于在两个方向之一上遍历数据结构来存储和搜索密钥 . 从语用意义上讲，这意味着如果值为<>，则以两个“方向”之一遍历数据结构 . 因此，从这个意义上讲，重复的值根本没有任何意义 .
这与BSP或二进制搜索分区不同，但并非完全不同 . 搜索算法有“旅行”的两个方向之一，或者已经完成（成功与否） . 所以我很抱歉我的原始答案没有解决“通用定义”的概念，因为重复实际上是一个独特的主题（成功搜索后处理的内容，而不是二进制搜索的一部分 . ）
如果您的二叉搜索树是红黑树，或者您打算进行任何类型的“树旋转”操作，则重复的节点将导致问题 . 想象一下你的树规则是这样的：
左<root <=右
现在想象一个简单的树，其根为5，左子为零，右子为5.如果在根上进行左旋转，则最终在左子项中为5，在右子项中为5没有 . 现在左侧树中的某些内容等于根，但上面的规则假定为左<root .
我花了几个小时试图弄清楚为什么我的红/黑树偶尔会不按顺序遍历，问题就是我上面所描述的 . 希望有人能够阅读此内容，并在将来节省自己的调试时间！
所有三个定义都是可接受和正确的 . 它们定义了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)
这简化了查找，删除和插入操作，代价是一些额外的字节和计数器操作 .
在BST中，节点左侧下降的所有值都小于（或等于，稍后参见）节点本身 . 类似地，在节点右侧下降的所有值都大于（或等于）节点值（a） .
一些BST可能会选择允许重复值，因此上面的“或等于”限定符 .
以下示例可能会澄清：
| +--- 14 ---+ | | +--- 13 +--- 22 ---+ | | | 1 16 +--- 29 ---+ | | 28 29
这显示了允许重复的BST - 您可以看到要查找值，您可以从根节点开始，然后根据您的搜索值是否小于或大于节点值向下或向右或向下移动子树 .
这可以通过以下方式递归完成：
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)
重复项会增加一点复杂性，因为一旦找到相同值的其他节点的值，您可能需要继续搜索 .
（a）如果你愿意调整搜索特定键的方式，你可以按照相反的方向对它们进行排序 . BST只需要保持一些排序顺序，无论是升序还是降序都不相关 .
在Cormen，Leiserson，Rivest和Stein的第9版"Introduction to algorithms"第三版中，二叉搜索树（BST）被明确定义为 allowing duplicates . 这可以在图12.1和以下（第287页）中看到：
“二叉搜索树中的键总是以满足二叉搜索树属性的方式存储：令x为二叉搜索树中的节点 . 如果y是x的左子树中的节点，然后y：key <= x：key . 如果y是x的右子树中的节点，则y：key> = x：key . “
此外，在第308页上定义了一个红黑树，如下所示：
“红黑树是一个二叉搜索树，每个节点有一个额外的存储空间：它的颜色”
因此，本书中定义的红黑树支持重复 .
在红黑树实现上工作我遇到了用多个键验证树的问题，直到我意识到使用红黑插入旋转，你必须放松约束到
left <= root <= right
由于我所看到的文档都没有允许重复键，我不想重写旋转方法来解释它，我只是决定修改我的节点以允许节点内的多个值，并且没有重复键那个树 .
任何定义都是有效的 . 只要你在实现中保持一致（总是将相同的节点放在右边，总是将它们放在左边，或者永远不允许它们）那么你就没事了 . 我认为最常见的是不允许它们，但如果它们被允许并且向左或向右放置它仍然是BST .
你说的那三件事都是真的 .
键是唯一的
左边是小于这个的键
右边是大于这个的键
我想你可以反转你的树并将较小的键放在右边，但实际上“左”和“右”的概念就是这样：一个视觉概念，帮助我们思考一个实际上没有左边的数据结构或者是对，所以这并不重要 .
1.）left <= root <right 2.）left <root <= right 3.）left <root <right，这样就不存在重复的键 .
我可能不得不去挖掘我的算法书籍，但我的头脑（3）是规范的形式 .
（1）或（2）仅在您开始允许重复节点并且将重复节点放在树本身（而不是包含列表的节点）时出现 .
元素排序关系<=是total order所以关系必须是自反的，但通常二元搜索树（又名BST）是没有重复的树 .
否则，如果有重复项，则需要运行两次或更多次相同的删除功能！
重复键•如果有多个具有相同键的数据项，会发生什么？ - 这在红黑树中存在轻微问题 . - 具有相同密钥的节点在具有相同密钥的其他节点的两侧分布是很重要的 . - 也就是说，如果按键按照50,50,50的顺序到达，你需要第二个50到第一个的右边，第三个50到第一个的左边 . •否则，树变得不 balancer . •这可以通过插入算法中的某种随机化过程来处理 . - 但是，如果必须找到具有相同密钥的所有项目，则搜索过程会变得更加复杂 . •使用相同的密钥禁止项目更简单 . - 在本次讨论中，我们假设不允许重复
可以为树的每个节点创建一个链表，其中包含重复键并在列表中存储数据 .
11 回答
许多算法将指定排除重复项 . 例如，MIT算法书中的示例算法通常提供没有重复的示例 . 实现重复（在节点上或在一个特定方向上作为列表）是相当简单的 . ）
大多数（我见过）将左边的孩子指定为<=，将右边的孩子指定为> . 实际上，允许右子节点或左子节点等于根节点的BST将需要额外的计算步骤来完成允许重复节点的搜索 .
最好利用节点上的列表来存储重复项，因为在节点的一侧插入'='值需要重写该侧的树以将节点作为子节点放置，或者节点放置为宏-child，在某些点下面，这消除了一些搜索效率 .
您必须记住，大多数课堂示例都经过简化，以描绘和传达概念 . 在许多现实世界的情况下，他们不值得蹲下 . 但是声明“每个元素都有一个键，没有两个元素具有相同的键”，在元素节点上使用列表不会违反 .
那么请关注您的数据结构书所说的内容！
编辑：
二进制搜索树的通用定义涉及基于在两个方向之一上遍历数据结构来存储和搜索密钥 . 从语用意义上讲，这意味着如果值为<>，则以两个“方向”之一遍历数据结构 . 因此，从这个意义上讲，重复的值根本没有任何意义 .
这与BSP或二进制搜索分区不同，但并非完全不同 . 搜索算法有“旅行”的两个方向之一，或者已经完成（成功与否） . 所以我很抱歉我的原始答案没有解决“通用定义”的概念，因为重复实际上是一个独特的主题（成功搜索后处理的内容，而不是二进制搜索的一部分 . ）
如果您的二叉搜索树是红黑树，或者您打算进行任何类型的“树旋转”操作，则重复的节点将导致问题 . 想象一下你的树规则是这样的：
左<root <=右
现在想象一个简单的树，其根为5，左子为零，右子为5.如果在根上进行左旋转，则最终在左子项中为5，在右子项中为5没有 . 现在左侧树中的某些内容等于根，但上面的规则假定为左<root .
我花了几个小时试图弄清楚为什么我的红/黑树偶尔会不按顺序遍历，问题就是我上面所描述的 . 希望有人能够阅读此内容，并在将来节省自己的调试时间！
所有三个定义都是可接受和正确的 . 它们定义了BST的不同变体 .
您的大学数据结构的书未能澄清其定义不是唯一可能的 .
当然，允许重复会增加复杂性 . 如果您使用“left <= root <right”定义，并且您有一棵树，如：
然后在此树中添加“3”重复键将导致：
请注意，重复项不是连续的级别 .
当允许BST表示中的重复项如上所述时，这是一个大问题：重复项可以由任意数量的级别分隔，因此检查重复项的存在并不像检查节点的直接子项那么简单 .
避免此问题的一个选项是不在结构上表示重复（作为单独的节点），而是使用计数器来计算密钥的出现次数 . 之前的示例将具有如下树：
插入复制“3”键后，它将变为：
这简化了查找，删除和插入操作，代价是一些额外的字节和计数器操作 .
在BST中，节点左侧下降的所有值都小于（或等于，稍后参见）节点本身 . 类似地，在节点右侧下降的所有值都大于（或等于）节点值（a） .
一些BST可能会选择允许重复值，因此上面的“或等于”限定符 .
以下示例可能会澄清：
这显示了允许重复的BST - 您可以看到要查找值，您可以从根节点开始，然后根据您的搜索值是否小于或大于节点值向下或向右或向下移动子树 .
这可以通过以下方式递归完成：
并调用它：
重复项会增加一点复杂性，因为一旦找到相同值的其他节点的值，您可能需要继续搜索 .
（a）如果你愿意调整搜索特定键的方式，你可以按照相反的方向对它们进行排序 . BST只需要保持一些排序顺序，无论是升序还是降序都不相关 .
在Cormen，Leiserson，Rivest和Stein的第9版"Introduction to algorithms"第三版中，二叉搜索树（BST）被明确定义为 allowing duplicates . 这可以在图12.1和以下（第287页）中看到：
此外，在第308页上定义了一个红黑树，如下所示：
因此，本书中定义的红黑树支持重复 .
在红黑树实现上工作我遇到了用多个键验证树的问题，直到我意识到使用红黑插入旋转，你必须放松约束到
left <= root <= right由于我所看到的文档都没有允许重复键，我不想重写旋转方法来解释它，我只是决定修改我的节点以允许节点内的多个值，并且没有重复键那个树 .
任何定义都是有效的 . 只要你在实现中保持一致（总是将相同的节点放在右边，总是将它们放在左边，或者永远不允许它们）那么你就没事了 . 我认为最常见的是不允许它们，但如果它们被允许并且向左或向右放置它仍然是BST .
你说的那三件事都是真的 .
键是唯一的
左边是小于这个的键
右边是大于这个的键
我想你可以反转你的树并将较小的键放在右边，但实际上“左”和“右”的概念就是这样：一个视觉概念，帮助我们思考一个实际上没有左边的数据结构或者是对，所以这并不重要 .
我可能不得不去挖掘我的算法书籍，但我的头脑（3）是规范的形式 .
（1）或（2）仅在您开始允许重复节点并且将重复节点放在树本身（而不是包含列表的节点）时出现 .
元素排序关系<=是total order所以关系必须是自反的，但通常二元搜索树（又名BST）是没有重复的树 .
否则，如果有重复项，则需要运行两次或更多次相同的删除功能！
重复键•如果有多个具有相同键的数据项，会发生什么？ - 这在红黑树中存在轻微问题 . - 具有相同密钥的节点在具有相同密钥的其他节点的两侧分布是很重要的 . - 也就是说，如果按键按照50,50,50的顺序到达，你需要第二个50到第一个的右边，第三个50到第一个的左边 . •否则，树变得不 balancer . •这可以通过插入算法中的某种随机化过程来处理 . - 但是，如果必须找到具有相同密钥的所有项目，则搜索过程会变得更加复杂 . •使用相同的密钥禁止项目更简单 . - 在本次讨论中，我们假设不允许重复
可以为树的每个节点创建一个链表，其中包含重复键并在列表中存储数据 .