将2-3棵树分割成小于或大于给定值X的树
将2-3棵树分割成小于或大于给定值X的树
提问于 2010-12-20 21:49:34
我需要编写函数，它接收一些键x并将2-3棵树分割成2-3棵树。在第一棵树中，所有节点都大于x，而在第二棵树中，节点数量较少。我需要使用复杂性O(logn)实现它。事先谢谢你的任何想法。
编辑了，我想在树中找到键x。然后把它的两个子树(大的或小的，如果它们存在的话)分成2棵，然后开始上升，每次检查我还没有检查过的子树，然后加入其中的一棵树。我的问题是，所有的叶子都必须在同一水平。
回答 2
Stack Overflow用户
回答已采纳
发布于 2010-12-20 22:04:18
假设您已经在讲座中介绍了2-3-4棵树，下面是一个提示:看看您是否也可以对2-3树应用相同的插入算法。特别是，插入总是从叶子开始，然后适当地重构树。完成后，确定您得到的算法的复杂性。
Stack Overflow用户
发布于 2010-12-21 08:04:53
如果您从根目录移动到您的键，并将每个节点分开，那么一个节点在大于键的节点上，另一个节点在其余节点上，然后使较大的节点成为您的大树的一部分，例如，让最左边的节点位于一个较高的节点上，(请先不要修复树，然后在最后完成它)，直到您到达您的树的键为止。然后，只需修复使用的路径上的两棵树(请注意，在两棵树上都存在相同的路径)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4494288
复制相关文章
相似问题
腾讯云开发者
