Tim*_*eld 128 computer-science binary-tree data-structures
我正在尝试找到二叉搜索树的定义,并且我一直在寻找不同的定义.
有人说,对于任何给定的子树,左子键小于或等于根.
有人说,对于任何给定的子树,右子键大于或等于根.
我的旧大学数据结构书中说"每个元素都有一个键,没有两个元素具有相同的键."
是否存在bst的通用定义？特别是关于如何处理具有相同密钥的多个实例的树.
编辑:也许我不清楚,我看到的定义是
1)左<= root <右
2)左<root <=右
3)左<root <右,这样就不存在重复的密钥.
Chr*_*ris 73
许多算法将指定排除重复项.例如,MIT算法书中的示例算法通常提供没有重复的示例.实现重复(在节点上或在一个特定方向上作为列表)是相当简单的.)
大多数(我见过)将左边的孩子指定为<=,将右边的孩子指定为>.实际上,允许右子节点或左子节点等于根节点的BST将需要额外的计算步骤来完成允许重复节点的搜索.
最好利用节点上的列表来存储重复项,因为在节点的一侧插入"="值需要重写该侧的树以将节点作为子节点放置,或者节点放置为宏-child,在某些点下面,这消除了一些搜索效率.
您必须记住,大多数课堂示例都经过简化,以描绘和传达概念.在许多现实世界的情况下,他们不值得蹲下.但是声明"每个元素都有一个键,没有两个元素具有相同的键",在元素节点上使用列表不会违反.
那么请关注您的数据结构书所说的内容!
编辑:
二进制搜索树的通用定义涉及基于在两个方向之一上遍历数据结构来存储和搜索密钥.从语用意义上讲,这意味着如果值为<>,则可以在两个"方向"之一中遍历数据结构.因此,从这个意义上说,重复的值根本没有任何意义.
这与BSP或二进制搜索分区不同,但并非完全不同.搜索算法有"旅行"的两个方向之一,或者已经完成(成功与否).所以我很抱歉我的原始答案没有解决"通用定义"的概念,因为重复实际上是一个独特的主题(成功搜索后处理的内容,而不是二进制搜索的一部分.)
Ric*_*ich 45
如果您的二叉搜索树是红黑树,或者您打算进行任何类型的"树旋转"操作,则重复的节点将导致问题.想象一下你的树规则是这样的:
左<root <=右
现在想象一个简单的树,其根为5,左子为零,右子为5.如果在根上进行左旋转,则最终在左子项中为5,在右子项中为5没有.现在左侧树中的某些内容等于根,但上面的规则假定为左<root.
我花了好几个小时试图弄清楚为什么我的红/黑树偶尔会出现故障,这个问题就是我上面所描述的.希望有人能够阅读此内容并在将来节省自己的调试时间!
小智 35
所有三个定义都是可接受和正确的.它们定义了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)
这简化了查找,删除和插入操作,代价是一些额外的字节和计数器操作.
pax*_*blo 21
在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只需要保持一些排序顺序,无论是升序还是降序都不相关.
小智 8
在Cormen,Leiserson,Rivest和Stein的第三版"算法导论"一书中,二叉搜索树(BST)被明确定义为允许重复.这可以在图12.1和以下(第287页)中看到:
"二叉搜索树中的键总是以满足二叉搜索树属性的方式存储:
x设为二叉搜索树y中的节点.如果是左子树中的节点x,那么y:key <= x:key.如果y是x然后是右子树中的一个节点y:key >= x:key."
此外,在第308页上定义了一个红黑树,如下所示:
"红黑树是一个二叉搜索树,每个节点有一个额外的存储空间:它的颜色"
因此,本书中定义的红黑树支持重复.
任何定义都是有效的。只要您在实现中保持一致（始终将相等的节点放在右侧，始终将它们放在左侧，或者永远不允许它们），那么您就可以了。我认为不允许它们是最常见的，但如果它们被允许并放置在左侧或右侧，它仍然是 BST。
我只想为@Robert Paulson 的回答添加更多信息。
让我们假设节点包含键和数据。因此具有相同键的节点可能包含不同的数据。
（所以搜索必须找到所有具有相同键的节点）
- 左 <= 当前 < 右
- 左 < 当前 <= 右
- 左 <= 当前 <= 右
- left < cur < right && cur 包含具有相同键的兄弟节点。
- left < cur < right，这样就不存在重复的键了。
1 & 2. 如果树没有任何与旋转相关的功能来防止偏斜，则工作正常。
但是这种形式不适用于AVL 树或红黑树，因为旋转会破坏主体。
即使 search() 找到了带有键的节点，它也必须向下遍历到带有重复键的节点的叶节点。
使搜索的时间复杂度 = theta(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 树。