将 2-3 树拆分为小于和大于给定值 X
我需要编写函数，它接收一些键 x 并将 2-3 树拆分为 2 2-3 树。在第一棵树中，所有节点都大于 x，而在第二棵树中，所有节点都小于 x。我需要使其复杂度O(logn)。预先感谢您的任何想法。
已编辑 我想到在树中找到钥匙x。将其两棵子树（如果存在的话，则更大或更小）分成两棵树，然后开始向上，每次检查我尚未检查的子树并加入其中一棵树。我的问题是所有叶子必须处于同一水平。
I need to write function, which receives some key x and split 2-3 tree into 2 2-3 trees. In first tree there are all nodes which are bigger than x, and in second which are less. I need to make it with complexity O(logn). thanks in advance for any idea.
edited
I thought about finding key x in the tree. And after split its two sub-trees(bigger or lesser if they exist) into 2 trees, and after begin to go up and every time to check sub-trees which I've not checked yet and to join to one of the trees. My problem is that all leaves must be at the same level.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您从根移动到键并分割每个节点，以便一个指向比键大的节点，另一个指向其余的节点，然后使较大的节点成为较大树的一部分，例如将最左边的节点放在在它的更高一级，（先不要修复树，在最后修复）直到你到达钥匙，你就会得到你的树。然后，您只需修复您使用的路径上的两棵树（请注意，两棵树上都存在相同的路径）。
If you move from the root to your key and split each node so one points at the nodes larger than the key and the other at the rest and then make the larger node be a part of your larger tree, say by having the leftmost node at one level higher point at it, (don't fix the tree yet, do it at the end) until you reach the key you will get your trees. Then you just need to fix both trees on the path you used (note that the same path exists on both trees).
假设您已经在讲座中介绍了 2-3-4 树，以下是提示：看看是否也可以对 2-3 棵树应用相同的插入算法。特别是，使插入始终从叶子开始，然后适当地重构树。完成后，确定您获得的算法的复杂性。
Assuming you have covered 2-3-4 trees in the lecture already, here is a hint: see whether you can apply the same insertion algorithm for 2-3 trees also. In particular, make insertions always start in the leaf, and then restructure the tree appropriately. When done, determine the complexity of the algorithm you got.