我在试着寻找二叉搜索树的定义我发现到处都是不同的定义。

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

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

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

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

编辑:也许我不清楚,我看到的定义是

1)左<=根<右

2)左<根<=右

3)左<根<右,这样就不存在重复的键。


当前回答

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

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

其他回答

你说的三件事都是真的。

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

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

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

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

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

左<=根<=右

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

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

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

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

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

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

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

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