187

我试图找到二叉搜索树的定义，并且到处都在寻找不同的定义。

有人说对于任何给定的子树，左子键小于或等于根。

有人说对于任何给定的子树，右子键大于或等于根。

我的旧大学数据结构书说“每个元素都有一个键，没有两个元素有相同的键”。

bst 有一个通用的定义吗？特别是关于如何处理具有相同键的多个实例的树。

编辑：也许我不清楚，我看到的定义是

1) 左 <= 根 < 右

2) 左 < 根 <= 右

3) left < root < right，这样不存在重复的键。

4

12 回答 12

93

许多算法将指定排除重复项。例如，麻省理工学院算法书中的示例算法通常提供没有重复的示例。实现重复是相当简单的（无论是作为节点上的列表，还是在一个特定方向上。）

大多数（我见过的）将左孩子指定为<=，右孩子指定为>。实际上，允许右子节点或左子节点等于根节点的 BST 将需要额外的计算步骤来完成允许重复节点的搜索。

最好在节点上使用列表来存储重复项，因为将“=”值插入节点的一侧需要重写该侧的树以将节点放置为子节点，或者将节点放置为大节点-child，在下面的某个点，它消除了一些搜索效率。

您必须记住，大多数课堂示例都经过简化来描述和传达概念。在许多现实世界的情况下，它们不值得深蹲。但是，“每个元素都有一个键并且没有两个元素具有相同的键”这句话并没有因为在元素节点上使用列表而被违反。

所以按照你的数据结构书所说的去做吧！

编辑：

二叉搜索树的通用定义涉及基于在两个方向之一上遍历数据结构来存储和搜索键。从实用的意义上讲，这意味着如果值为 <>，则您将在两个“方向”之一中遍历数据结构。所以，从这个意义上说，重复值根本没有任何意义。

这与 BSP 或二分搜索分区不同，但并非完全不同。搜索算法具有“旅行”的两个方向之一，或者已经完成（成功与否）。所以我很抱歉我的原始答案没有解决“通用定义”的概念，因为重复确实是一个不同的主题（您在成功搜索后处理的内容，而不是作为二分搜索的一部分。）

于 2008-11-19T04:08:53.953 回答
65

如果你的二叉搜索树是一棵红黑树，或者你打算进行任何一种“树旋转”操作，重复的节点都会导致问题。想象一下你的树规则是这样的：

左 < 根 <= 右

现在想象一个简单的树，它的根是 5，左孩子是 nil，右孩子是 5。如果你对根进行左旋转，你最终会在左孩子中得到 5，在右孩子中得到 5为零。现在左树中的某些东西等于根，但您上面的规则假设左 < 根。

我花了几个小时试图弄清楚为什么我的红/黑树偶尔会乱序遍历，问题就是我上面描述的。希望有人阅读此内容并在将来节省数小时的调试时间！

于 2008-12-04T04:27:44.317 回答
56

所有三个定义都是可以接受和正确的。它们定义了 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)

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

于 2013-12-06T14:32:29.833 回答
34

在 BST 中，从节点左侧下降的所有值都小于（或等于，见后文）节点本身。类似地，在节点右侧下降的所有值都大于（或等于）该节点值(a)。

一些 BST可能选择允许重复值，因此上面的“或等于”限定词。下面的例子可以说明：

     14
    /  \
  13    22
 /     /  \
1    16    29
          /  \
        28    29

这显示了一个允许重复的 BST (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)有趣的是，如果您的排序键使用存储在节点上的整个值（因此包含相同键的节点没有其他额外信息来区分它们），则可以通过向每个节点添加计数来提高性能，而不是允许重复节点。

主要好处是添加或删除重复项只会修改计数而不是插入或删除新节点（可能需要重新平衡树的操作）。

所以，要添加一个项目，你首先要检查它是否已经存在。如果是这样，只需增加计数并退出。如果没有，您需要插入一个计数为 1 的新节点，然后重新平衡。

要删除一个项目，您找到它然后减少计数 - 只有当结果计数为零时，您才会从树中删除实际节点并重新平衡。

考虑到节点较少，搜索也更快，但这可能影响不大。

例如，以下两棵树（左侧不计数，右侧计数）将等价（在计数树中，i.c表示citem 的副本i）：

     __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.2to的简单修改22.1（不需要重新平衡）。

于 2008-11-19T04:04:23.370 回答
11

在 Cormen、Leiserson、Rivest 和 Stein 所著的第三版“算法简介”一书中，二叉搜索树 (BST) 被明确定义为允许重复。这可以在图 12.1 和以下（第 287 页）中看到：

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

此外，然后在第 308 页将红黑树定义为：

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

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

于 2016-09-07T08:01:44.370 回答
6

任何定义都是有效的。只要您在实现中保持一致（始终将相等的节点放在右侧，始终将它们放在左侧，或者永远不允许它们），那么您就可以了。我认为不允许它们是最常见的，但如果它们被允许并且放置在左侧或右侧，它仍然是 BST。

于 2008-11-19T03:47:19.097 回答
5

我只想为@Robert Paulson 回答的内容添加更多信息。

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

  1. 左 <= 当前 < 右
  1. 左 < cur <= 右
  1. 左 <= 当前 <= 右
  1. left < cur < right && cur 包含具有相同键的兄弟节点。
  1. left < cur < right，这样就不存在重复的键。

如果树没有任何与旋转相关的功能来防止偏斜，则 1 和 2. 可以正常工作。
但是这种形式不适用于AVL 树或Red-Black 树，因为旋转会破坏主体。
并且即使 search() 找到具有键的节点，它也必须向下遍历到具有重复键的节点的叶节点。
使 search = theta(logN)

3. 的时间复杂度可以很好地与任何形式的具有旋转相关功能的 BST 配合使用。
但是搜索将花费O(n)，破坏了使用 BST 的目的。
假设我们有如下树，3) 主体。

         12
       /    \
     10     20
    /  \    /
   9   11  12 
      /      \
    10       12

如果我们在这棵树上执行search(12)，即使我们在根处找到 12，我们也必须继续搜索左右子节点以寻找重复键。
正如我所说，这需要 O(n) 时间。

4.是我个人的最爱。假设兄弟节点意味着具有相同键的节点。
我们可以把上面的树变成下面的。

         12 - 12 - 12
       /    \
10 - 10     20
    /  \
   9   11

现在任何搜索都将花费 O(logN)，因为我们不必遍历子项来查找重复键。
而且这个主体也适用于AVL或RB 树。

于 2020-04-18T16:42:26.217 回答
3

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

left <= root <= right

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

于 2011-04-11T20:56:38.177 回答
2

你说的这三件事都是真的。

  • 键是唯一的
  • 左边是小于这个的键
  • 右边是大于这个的键

我想你可以反转你的树并将较小的键放在右边，但实际上“左”和“右”的概念就是这样：一个视觉概念，帮助我们思考一个没有真正左的数据结构或者正确，所以这并不重要。

于 2008-11-19T03:52:02.537 回答
1

重复键 • 如果多个数据项具有相同的键，会发生什么情况？– 这在红黑树中提出了一个小问题。– 重要的是，具有相同密钥的节点分布在具有相同密钥的其他节点的两侧。– 也就是说，如果密钥按 50、50、50 的顺序到达， • 您希望第二个 50 位于第一个的右侧，第三个 50 位于第一个的左侧。• 否则，树会变得不平衡。• 这可以通过插入算法中的某种随机化过程来处理。– 但是，如果必须找到具有相同键的所有项目，则搜索过程会变得更加复杂。• 使用相同密钥取缔物品更简单。– 在本次讨论中，我们假设不允许重复

可以为包含重复键的树的每个节点创建一个链表，并将数据存储在链表中。

于 2013-07-29T22:17:07.880 回答
1

1.) 左 <= 根 < 右

2.) 左 < 根 <= 右

3.) left < root < right，这样不存在重复的键。

我可能不得不去挖掘我的算法书籍，但我的头顶（3）是规范形式。

(1) 或 (2) 仅在您开始允许重复节点并将重复节点放入树本身（而不是包含列表的节点）时出现。

于 2008-11-19T05:22:58.373 回答
0

元素排序关系 <= 是一个总顺序，因此关系必须是自反的，但通常二叉搜索树（又名 BST）是没有重复的树。

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

于 2012-02-13T18:56:28.267 回答