Take the 2-minute tour ×

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.

share|improve this question
What have you tried? What's your thinking about what is needed? "Do my homework for me" questions are discouraged - show us you've made an effort and people will help when you get stuck. Don't put in any visible effort, and they're less likely to help. –  Paul Dec 20 '10 at 21:51
This homework: What thoughts on the structure and implementation have you had so far? –  winwaed Dec 20 '10 at 21:54
add comment

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
one of the reasons why I do like stackoverflow, I can always find man who knows more than I do, thanks –  rookie Dec 20 '10 at 22:56
add comment

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).

share|improve this answer
add comment

Your Answer


