Trying to understand a way to split an AVL tree in O(log n)

Question

I'm trying to understand a presentation about AVL trees. It says that the way to split AVL trees in node x is as follows: You search for the node x and mark every left son of every node when you turn right. Later, you merge all the marked subtrees.

Now, i've drawn a complete BST with 15 nodes and tried the algorithm by splitting node 7: Now, I mark nodes 2 and 5, try to merge them, and the left tree does not have node 6 in it. The description about how to split trees is not complete and I don't know what i'm supposed to do with it.

Answer 1

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.

@staticmethod
def ReBalanceRightist(parent, node):
    assert parent is not None
    while node is not None:
        AvlNode.UnlinkNodes(parent, node)
        node = AvlNode.ReBalance(node)
        AvlNode.LinkNodes(parent, 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:

https://github.com/Izikiel/AvlPython

Answer 2

I think the devil is in the phrase "every left son of every node where you turns right". If you look at the picture on the slide each marked subtree has a node attached at the top. So in your example you mark 2 as the left son of 4 and 5 as the left son of 6. Now in the merging process you need to include 4 and 6 as well as the subtrees rooted at 2 and 5