我在试着寻找二叉搜索树的定义我发现到处都是不同的定义。
有人说,对于任何给定的子树,左子键都小于或等于根键。
有人说,对于任何给定的子树,右子键大于或等于根键。
我以前的大学数据结构书说“每个元素都有一个键,没有两个元素有相同的键。”
bst有一个通用的定义吗?特别是关于如何处理具有相同键的多个实例的树。
编辑:也许我不清楚,我看到的定义是
1)左<=根<右
2)左<根<=右
3)左<根<右,这样就不存在重复的键。
我在试着寻找二叉搜索树的定义我发现到处都是不同的定义。
有人说,对于任何给定的子树,左子键都小于或等于根键。
有人说,对于任何给定的子树,右子键大于或等于根键。
我以前的大学数据结构书说“每个元素都有一个键,没有两个元素有相同的键。”
bst有一个通用的定义吗?特别是关于如何处理具有相同键的多个实例的树。
编辑:也许我不清楚,我看到的定义是
1)左<=根<右
2)左<根<=右
3)左<根<右,这样就不存在重复的键。
当前回答
所有这三个定义都是可以接受和正确的。它们定义了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)
这简化了查找、删除和插入操作,但牺牲了一些额外的字节和计数器操作。
其他回答
Duplicate Keys • What happens if there's more than one data item with the same key? – This presents a slight problem in red-black trees. – It's important that nodes with the same key are distributed on both sides of other nodes with the same key. – That is, if keys arrive in the order 50, 50, 50, • you want the second 50 to go to the right of the first one, and the third 50 to go to the left of the first one. • Otherwise, the tree becomes unbalanced. • This could be handled by some kind of randomizing process in the insertion algorithm. – However, the search process then becomes more complicated if all items with the same key must be found. • It's simpler to outlaw items with the same key. – In this discussion we'll assume duplicates aren't allowed
可以为树的每个节点创建包含重复键的链表,并将数据存储在列表中。
如果您的二叉搜索树是红黑树,或者您打算进行任何类型的“树旋转”操作,重复的节点将导致问题。假设你的树规则是这样的:
左<根<=右
现在想象一个简单的树,它的根是5,左子结点是nil,右子结点是5。如果你在根结点上做一个左旋转你会在左子结点中得到一个5在根结点中得到一个5而右子结点为nil。现在左树中的某个元素等于根结点,但上面的规则假设左<根结点。
我花了几个小时试图弄清楚为什么我的红/黑树偶尔会乱序,问题就是我上面描述的。希望有人读了这篇文章,将来可以节省调试的时间!
所有这三个定义都是可以接受和正确的。它们定义了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)
这简化了查找、删除和插入操作,但牺牲了一些额外的字节和计数器操作。
在Cormen、Leiserson、Rivest和Stein合著的《算法介绍》第三版中,二叉搜索树(BST)被明确定义为允许重复。这可以从图12.1和以下(第287页)中看到:
二叉搜索树中的键总是以满足二叉搜索树属性的方式存储:设x是二叉搜索树中的一个节点。如果y是x的左子树中的一个节点,则y:key <= x:key。如果y是x的右子树中的一个节点,那么y:key >= x:key。”
此外,红黑树在308页被定义为:
红黑树是一种二叉搜索树,每个节点有一个额外的存储位:它的颜色。
因此,本书定义的红黑树支持重复。
在使用红黑树实现时,我遇到了用多个键验证树的问题,直到我意识到使用红黑插入旋转时,必须放松对的约束
左<=根<=右
由于我所查看的任何文档都不允许重复键,而且我不想重写旋转方法来解释它,所以我决定修改节点以允许节点内的多个值,并且树中不允许重复键。