二叉搜索树的定义中允许重复的键吗?

小开

任何定义都是有效的。只要在实现中保持一致(总是把相等的节点放在右边，总是把它们放在左边，或者不允许它们这样做)，那么就没问题。我认为不允许它们是最常见的，但如果允许它们并放置在左边或右边，它仍然是一个BST。

小开

你说的三件事都是真的。

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

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

小开

在BST中，节点左侧降序的所有值都小于(或等于，稍后将讨论)节点本身。类似地，节点右侧降序的所有值都大于(或等于)该节点的value^(一)。

一些bst 五月选择允许重复值，因此"或等于"限定符。下面的例子可以说明:

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

这显示了一个允许duplicates^(b)的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)

重复增加了一些复杂性，因为在找到值之后，您可能需要继续搜索具有相同值的其他节点。显然，这对于hasVal并不重要，因为它不关心有多少个，只关心是否至少存在一个。然而，对于像countVal这样的东西，它会很重要，因为它需要知道有多少个。

^(一)你可以实际上在相反的方向排序它们，如果你希望这样，只要你调整你如何搜索一个特定的键。BST只需要保持某种排序顺序，无论是升序还是降序(甚至是一些奇怪的多层排序方法，如所有奇数升序，然后所有偶数降序)都无关紧要。

有趣的是，如果你的排序键使用存储在节点上的整个值(这样包含相同键的节点有没有其他额外信息来区分它们)，可以通过向每个节点添加计数来提高性能，而不是允许重复节点。

这样做的主要好处是，添加或删除副本只会修改计数，而不是插入或删除新节点(这一操作可能需要重新平衡树)。

因此，对于添加一个项，首先检查它是否已经存在。如果是，增加计数并退出。如果不是，则需要插入一个新节点，其计数为1，然后重新平衡。

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

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

例如，下面的两棵树(左边的非计数树和右边的计数树)将是等价的(在计数树中，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将涉及重新平衡(因为它现在有两个高度差)产生的22-29-28-30子树，如下所示(这是一个选项，还有其他选项也满足“高度差必须为0或1”;规则):

\                      \
22                     29
\                   /  \
29      -->      28    30
/  \             /
28    30         22

在右边的树上做同样的操作是简单地将根节点从22.2修改为22.1(不需要重新平衡)。

小开

许多算法将指定排除重复项。例如，麻省理工学院算法书中的示例算法通常会给出没有重复的示例。实现副本相当简单(在节点上作为列表，或者在一个特定方向上)。

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

最好利用节点上的列表来存储重复项，因为在节点的一侧插入'='值需要重写这一侧的树以将该节点作为子节点，或者将该节点作为子节点放置在下面的某个位置，这降低了一些搜索效率。

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

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

编辑:

二叉搜索树的通用定义涉及基于在两个方向之一遍历数据结构的基础上存储和搜索键。从实际意义上讲，这意味着如果值是<>，您将沿着两个“方向”之一遍历数据结构。所以，在这种情况下，重复的值没有任何意义。

这与BSP或二进制搜索分区不同，但也不是完全不同。搜索算法有两个“旅行”方向之一，否则它就完成了(成功与否)。所以我很抱歉，我最初的答案没有解决“通用定义”的概念，因为重复的内容实际上是一个不同的主题(在成功搜索之后处理的内容，而不是作为二分搜索的一部分)。

小开

1.) left <= root <正确的

2.)左<根<=右

3.)左<根& lt;对，这样就不存在重复的键。

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

(1)或(2)只发生在你开始允许重复节点而且你把重复节点放在树本身(而不是包含列表的节点)。

小开

如果您的二叉搜索树是红黑树，或者您打算进行任何类型的“树旋转”操作，重复的节点将导致问题。假设你的树规则是这样的:

左& lt;根<=右

现在想象一个简单的树，它的根是5，左子结点是nil，右子结点是5。如果你在根结点上做一个左旋转你会在左子结点中得到一个5在根结点中得到一个5而右子结点为nil。左边树中的某个元素等于根结点，但上面的规则假设了left <根。

我花了几个小时试图弄清楚为什么我的红/黑树偶尔会乱序，问题就是我上面描述的。希望有人读了这篇文章，将来可以节省调试的时间!

小开

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

left <= root <= right

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

小开

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

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

小开

< p >复制钥匙 •如果有多个数据项会发生什么同样的钥匙? 这在红黑树中出现了一个小问题。 —具有相同密钥的节点分布在上面是很重要的其他节点的两边都有相同的键。 -也就是说，如果钥匙以50,50,50的顺序到达， •第二个50要在第一个50的右边，还有第三个50去第一个的左边。 •否则，树将变得不平衡。 •这可以通过某种随机化来处理进程中的插入算法。 -然而，如果搜索过程变得更加复杂必须找到所有具有相同密钥的项目。 •禁用具有相同键的项目更简单。 -在这个讨论中，我们假设不允许重复

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

小开

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

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

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

      3
/   \
2       4

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

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

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

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

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

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

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

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

小开

在Cormen, Leiserson, Rivest和Stein所著的《算法介绍》(第三版)一书中，二叉搜索树(BST)被明确定义为允许重复。这可以从图12.1和以下(第287页)中看到:

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

此外，红黑树在308页被定义为:

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

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

小开

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

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

左<= cur <正确的

左& lt;正确的

左<= cur <=右

左& lt;坏蛋& lt;对吧,,同级节点包含相同的键。

左& lt;坏蛋& lt;对，这样就不存在重复的键。

< p > 1,2. 如果树没有任何rotation-related功能来防止倾斜，则可以正常工作但此形式为不工作与AVL树或红黑树，因为旋转将破坏主体。
而且即使search()找到了具有密钥的节点，它也必须向下遍历到具有重复密钥的叶节点使搜索的时间复杂度= θ(logN)

3.将很好地与任何形式的BST旋转相关的函数但是搜索将花费O (n)，破坏了使用BST.
的目的假设我们有如下的树，有3)主体。

         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树