Assume that I have two AVL trees and that each element from the first tree is smaller then any element from the second tree. What is the most efficient way to concatenate them into one single AVL tree? I've searched everywhere but haven't found anything useful.
+1
A:
I suspect that you'll just have to walk one tree (hopefully the smaller) and individually add each of it's elements to the other tree. The AVL insert/delete operations are not designed to handle adding a whole subtree at a time.
Dale Hagglund
2010-01-10 14:12:53
I have a feeling that it can be done linearly. Using the naïve approach takes O(n log n) time.
avakar
2010-01-10 14:27:06
This takes O(n log n) -> much slower than meriton's solution
inspectorG4dget
2010-02-12 15:45:57
@meriton's solution is indeed very nice, but it assumes (a) that every node in one tree is strictly less than every node in the other tree, (b) you have access to the raw avl tree data structures, and (c) can perform rotations directly on the tree nodes. If (a) doesn't hold, or the low level tree manipulations aren't available to you (most likely because you're using an avl library) then you may have to fall back on simply inserting each node from the smaller tree into the larger.
Dale Hagglund
2010-02-13 04:15:07
+6
A:
Assuming you may destroy the input trees:
- remove the rightmost element for the left tree, and use it to construct a new root node, whose left child is the left tree, and whose right child is the right tree: O(log n)
- determine and set that node's balance factor: O(log n). In (temporary) violation of the invariant, the balance factor may be outside the range {-1, 0, 1}
- rotate to get the balance factor back into range: O(log n) rotations: O(log n)
Thus, the entire operation can be performed in O(log n).
Edit: On second thought, it is easier to reason about the rotations in the following algorithm. It is also quite likely faster:
- Determine the height of both trees: O(log n). Assume the right tree is taller (the other case is symmetric).
- remove the rightmost element from the left tree. Let 'n' be that element. (Adjust its computed height if necessary): O(log n)
- In the right tree, navigate left until you reach the node whose subtree has the same height as the left tree. Let r be that node. O(log n)
- replace that node with (left,n,r). By construction, this node is 1 taller than r. Increment its parent's balance accordingly. O(1)
- rebalance like you would after inserting. O(log n)
meriton
2010-01-10 14:50:20
Are you quite sure? (You might easily be correct, but I'm just curious.) Suppose the left tree is much smaller than the right tree ie, much shallower. Why will O(log n) rotations restore the AVL property? How do you decide where to rotate?
Dale Hagglund
2010-01-10 14:57:45
What Dale says: the usual choice of rotations for an AVL tree allows an imbalance of size 2 to be corrected back into range [-1,1] with O(log n) rotations. You need a new scheme for choosing rotations in order to correct an arbitrary imbalance. Since that's the part of AVL trees that I can never remember, and have to look up every time, I expect that even if the choice of rotations is obvious, it's not obvious to me :-)
Steve Jessop
2010-01-10 15:21:50
Good points. I found it easier to prove another algorithm (c.f. my edited answer).
meriton
2010-01-10 16:36:08
Thanks for your answer. It worked! One thing, though, at point 3 you need to navigate left until you reach a node with 'node.height <= left_tree.height + 1'.
bilygates
2010-01-11 16:21:16