So, basically, what you are saying, is that you have a bunch of left leaning avls and want to merge them?
That's what I understand from the first graph.
You can merge and rebalance them in O(log(n)) time.
What I did was to make each tree a right child of the previous one, and then you start to rebalance at the root and moving to the right, with the rebalancing being a single or double rotation depending on the balance factors of the node and its children, and then you move to the right children and repeat.
def ReBalanceRightist(parent, node):
assert parent is not None
while node is not None:
node = AvlNode.ReBalance(node)
parent = node
node = node.right
First you unlink them, because you don't know if node will still be the root of that subtree, rebalance, and set the result of that rebalance as the new child.
Then rinse and repeat.
This works with O(log(n)) complexity as each left subtree is already balanced, and you just need one rebalance operation to balance a node (O(1)), then you repeat this along the branch, and the branch length is at most log(n), so you get O(log(n)) complexity.
I had to implement a remove_below(x) and remove_above(x) functions for an Avl, so that all the nodes with keys lesser than x or bigger than x would be removed from the tree, respectively, and the problem in the end is the same, which is, how to merge k right/left leaning trees.
You can look at the code here: