Represent AVL tree with 3 different AVL trees

Question

For some reason I need to construct 1 AVL tree but represent it with 3 different AVL Trees and keep the balance between the trees, for example for AVL tree with 15 nodes the first 5 when transverse in-order should be in the first tree the second 5 in the next tree etc...

Lets suppose that the keys are integers and you need to insert/delete nodes from the tree

Example: if the in-order transverse output of AVL tree is 1,2,3,4,5,6

It should be represent by 3 AVL trees (1,2)(3,4)(5,6) it also can be (2,1)(3,4)(5,6) the order of each tree doesn't matter.

I can't figure out the algorithm to keep this balance between the trees

Answer 1

A pragmatic way to do this is to:

• Keep track of the number of nodes in each of the three trees
• Keep track of the least and greatest value in each tree

I will not explicitly mention the updates to these attributes in the below algorithm, but take care to update them whenever needed.

Insert

1. Choose the left most tree whose greatest value is greater than the value you want to insert. If there is no such tree, choose the right most tree.

2. Make the usual AVL insertion in that tree, including the standard AVL rebalancing when appropriate.

3. If this tree happens to have 2 more nodes than the tree with the least number of nodes, then check where that smaller tree is with respect to the current tree:

   • If it is at the left, then delete the least value from the larger tree, and insert it into the tree at its immediate left (repeat the procedure from the top)

   • If it is at the right, then delete the greatest value from the larger tree and insert it into the tree at its immediate right (repeat the procedure from the top)

4. At this point all constraints are satisfied.

Delete

1. Find the tree that must have the target value based on the least-greater information we have for each tree

2. Perform the standard AVL deletion algorithm on that tree.

3. If the number of nodes in that tree is 2 less than the largest tree, then check where that greater tree is, and then:

   • If that larger tree is at the left side, get the greatest value from the immediate left neighbor of the smaller tree, and insert it into the current tree, and finally delete it from the left neighbor (repeating the current procedure from the top)
   • If that larger tree is at the right side, get the greatest value from the immediate right neighbor of the smaller tree, and insert it into the current tree, and finally delete it from the right neighbor (repeating the current procedure from the top)

4. At this point all constraints are satisfied.