在定义二叉搜索树时，是否允许重复的键？

Question

在定义二叉搜索树时，是否允许重复的键？

data-structurescomputer-sciencebinary-tree

212

我正在尝试寻找二叉搜索树的定义，但无论在哪里都找到了不同的定义。

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

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

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

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

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

1）left <= root < right

2）left < root <= right

3）left < root < right，其中不存在重复的键。

- Tim Merrifield

13个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mszlazak · Answer 1

重复的键 • 如果有多个具有相同键的数据项会发生什么情况？ - 这在红黑树中会带来一些问题。 - 很重要的是，具有相同键的节点分布在其他具有相同键的节点两侧。 - 也就是说，如果按照50、50、50的顺序到达键值， • 您希望第二个50放置在第一个50的右边，第三个50将放置在第一个50的左边。 • 否则，树会失衡。 • 可以通过插入算法中的某种随机化过程来处理这个问题。 - 然而，如果必须找到所有具有相同键的项，则搜索过程变得更加复杂。 • 禁止具有相同键的项会更简单。 - 在本讨论中，我们假设不允许重复项。

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

- Alberto · Answer 2

元素的排序关系<=是一个全序，因此该关系必须是自反的，但通常二叉搜索树（也称为BST）是一棵没有重复元素的树。

否则，如果有重复元素，则需要运行两次或多次相同的删除函数！

- Gautam Mahapatra · Answer 3

BST（二叉搜索树）的定义使用键来存储。对于数据库而言，键是唯一的。BST还可以用于将数据库存储在物理文件系统中，以供DBMS使用。（在实际情况中，键与其他数据一起被用来存储数据库中的记录。）带有红黑树或AVL类似操作的BST是一种高效的结构。如果允许重复，则需要使用额外的链接字段来指向具有重复键的所有记录，形成一个链表形式。