二叉搜索树中的重复条目

Question

二叉搜索树中的重复条目

4

我有一个关于BST的非常简单的问题。我看过多个关于重复条目的BST定义。有些定义BST不允许重复条目，另一些定义节点的左子树小于等于节点的值，右子树大于节点的值，还有一些定义是相反的（左子树小于节点，右子树大于等于节点）。所以我的问题是，对于允许重复条目的BST，官方定义是什么（如果存在的话）？例如，在插入值3、5、10、8、5、10后，BST会是什么样子？

感谢您事先澄清定义并回答我的问题！

- Tareq

“官方定义”？你认为什么才是“官方”的？这里需要什么级别的权威性？ - S.Lott

我猜这与权限级别无关，更多的是关于二叉搜索树在重复条目方面最常被接受的定义是什么。 - Tareq

2个回答

3

重要的一点是，树中没有重复元素可以确保快速查找时间。如果节点的一个侧面有重复项，则搜索时间会受到影响，因为您必须在继续之前检查所有重复项。 http://en.wikipedia.org/wiki/Binary_search_tree

- light_303

这个外部链接在这种情况下并不是很有用。 - Niklas B.

在左子节点小于节点且右子节点大于或等于节点的树中，这并不是什么大问题。当找到第一个节点时，只需检查右侧子节点即可获取所有重复项。 - Nikolay Polivanov

当然，每个节点都可以包含元素出现次数的计数。 - C. Reed

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

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

- TonySalimi · Accepted Answer

算法和数据结构领域中著名的书籍之一是CLRS book，也被称为数据结构和算法圣经：

enter image description here

根据本书的定义，重复的条目被放置在包含相同关键字的节点的右子树中。例如，看一下从本书采用的BST插入算法：

enter image description here