文章/答案/技术大牛

发布

社区首页 >问答首页 >如何允许二进制搜索树中的副本？

问如何允许二进制搜索树中的副本？
EN

Stack Overflow用户

提问于 2015-09-01 00:32:22

回答 1查看 585关注 0票数 3

我并不是在寻找代码，我只是在寻找概念。

根据加州大学伯克利分校的教授(在线CS61b课程)的说法，如果你找到了一个完全匹配的条目，你可以把你的新条目作为一个左撇子插入。

假设您总是选择精确匹配的左节点并在那里插入新条目，如果您发现的准确匹配已经有一个左子项，那么会发生什么情况？您是否将其分离并强制一个新条目取代它，并将旧的左子节点重新连接为这个新节点的子节点？

如果确切的匹配已经有一个左子，这本身就是一个完全匹配的呢？如果允许重复，代码会变得太复杂吗？

binary-search-tree

algorithm

data-structures

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-09-01 01:00:36

在附加节点之前，您需要尽可能地向左走。按照新节点的常规插入逻辑进入左侧子树。例如，如果要插入

5, 3, 7, 2, 3, 8, 7, 2, 5

生成的树如下所示：

                      5
                    /   \
                   3     7
                  / \   / \
                 2   5 7   8
                / \
               2   3

注意3s和5s在这棵树中是如何不在一起的，因为在我们插入副本时，第一个3已经有一个左子，5也是如此。

当然，这并不理想，因为搜索不会在找到所需的元素时结束。一种更好的方法是增加树结构，方法是为树中的每个节点放置重复计数，或者如果树用于关联存储，则将附加到每个节点的数据列表。

                     5(2)
                    /    \
                  3(2)   7(2)
                 /         \
               2(2)        7(1)

票数 5

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/32321857

复制

相似问题

问如何允许二进制搜索树中的副本？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何允许二进制搜索树中的副本？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何允许二进制搜索树中的副本？
EN