二进制搜索树中的重复条目

我有一个关于BST的非常简单的问题。我已经看到关于重复条目的BST的多个定义。有些定义BST不允许重复输入，其他节点的左边子节点为< =节点值，右边的子节点大于节点的值，其中一些定义与此相反（左边的子节点为<）孩子是> =）。二进制搜索树中的重复条目

所以我的问题是关于重复条目的BST的官方定义（如果存在的话）是什么？例如，在插入值后，BST的外观如何：3,5,10,8,5,10？

非常感谢您澄清定义并回答我的问题！

2012-01-02 Tareq

“官方定义”？你认为什么是“官方”？这里需要什么样的权限？ – 2012-01-02 18:35:25

我想这不是什么级别的权威，因为它是最常被接受的关于重复条目的BST的定义。 – Tareq 2012-01-02 19:14:11

一个在算法和数据结构区域中的公知的书籍是CLRS book，也被称为数据结构和算法的圣经：

enter image description here

根据该定义本书时，重复条目将放置在包含相同键的节点的右侧树中。作为一个例子，从这本书采用一看BSTS的插入算法：

enter image description here

2012-01-02 18:32:56 hsalimi

哇非常有趣和温和的答案。 – 2012-02-16 18:13:26

重要的一点是，而不是在树中有重复确保快速查找时间。如果节点一侧有重复项，则搜索时间将受到影响，因为在继续之前必须先通过所有重复项。

2012-01-02 18:25:05

在这种情况下，外部链接不是非常有用。 – 2012-01-02 18:27:56

在左子节点<节点且右子节点大于节点的树中，这不是什么大不了的事情。当找到第一个节点时，可以检查正确的孩子以获得所有重复。 – 2012-01-02 18:54:41

当然，每个节点可能只包含元素出现次数的计数 – 2012-01-02 19:03:53

回答