拆分2-3树成小于和大于给定值X [英] Split 2-3 tree into less-than and greater-than given value X

问题描述

我需要编写函数，它接收一些关键的x和拆分2-3树成2 2-3棵。在第一棵树有其均大于x，它是不太所有节点，并在第二位。我需要用复杂的 O（LOGN）使其。感谢您事先的任何想法。

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.

修改 我想过要找密钥x，在树中。而拆分后的两个子树（大或如果存在小）到2棵，并开始后往上走，每一次检查子树，我还没有检查尚未并加入到树之一。我的问题是，所有叶必须在同一级别

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.

推荐答案

假设你已经把 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.

这篇关于拆分2-3树成小于和大于给定值X的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！