我正在尝试找到二叉搜索树的定义,并且我一直在到处寻找不同的定义。
有人说对于任何给定的子树,左子键小于或等于根。
有人说对于任何给定的子树,右子键大于或等于根。
我以前的大学数据结构书上说“每个元素都有一个键,并且没有两个元素具有相同的键”。
bst 是否有通用的定义?特别是关于如何处理具有相同键的多个实例的树。
编辑:也许我不清楚,我看到的定义是
1) 左
2) 左
3) left
许多算法会指定排除重复项。例如,麻省理工学院算法书中的示例算法通常提供没有重复的示例。实现重复项是相当简单的(无论是作为节点上的列表,还是在一个特定方向上)。
大多数(我见过)将左子元素指定为 。实际上,允许右子节点或左子节点等于根节点的 BST 将需要额外的计算步骤来完成允许重复节点的搜索。
最好在节点处使用列表来存储重复项,因为在节点的一侧插入“=”值需要重写该侧的树以将节点放置为子节点,或者将节点放置为大节点-child,在下面的某个点,这消除了一些搜索效率。
您必须记住,大多数课堂示例都经过简化以描述和传达概念。在许多现实情况下,它们不值得蹲下。但是,在元素节点处使用列表并不违反“每个元素都有一个键,并且没有两个元素具有相同的键”这一说法。
所以按照你的数据结构书上所说的去做吧!
Edit:
二叉搜索树的通用定义涉及基于沿两个方向之一遍历数据结构来存储和搜索键。从实用意义上来说,这意味着如果值为 ,则您将沿两个“方向”之一遍历数据结构。因此,从这个意义上说,重复值根本没有任何意义。
这与 BSP(或二分搜索分区)不同,但也没有那么不同。搜索算法有两个“旅行”方向之一,或者已经完成(成功与否)。因此,我很抱歉我原来的答案没有解决“通用定义”的概念,因为重复项实际上是一个不同的主题(成功搜索后处理的内容,而不是作为二分搜索的一部分。)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)