AVL tree partition
-
04-11-2019 - |
Pergunta
The statement sais the following
Design a function to partition an AVL tree such that, given an AVL tree and a key $x$, it returns two AVL trees, one containing the keys lower or equal than $x$, and the other containing the remaining keys. The complexity must be better than $\mathcal{O}(n)$ (being $n$ the cardinality of the tree).
My attempt is the following recursive algorithm (in pseudo code, so notation abuse is probable).
split(T x, Node root, Node link, Node lower){
if(root.key <= x){
if(lower.isEmpty())
lower=BinaryTree(root.left,root,null);
else link.right = BinaryTree(root.left,root,null);
link = root;
if (root.key< x)
split(x,root.right.root,link,lower);
} else split(x,root.left.root,link,lower);
}
if I am not mistaken, the algorithm returns a binary search tree (but possibly not balanced) whose keys are the ones in the original tree lower of equal than $x$. An analogous one can be done to build the other tree.
So, the question is how to balance both trees without icreasing the current $\mathcal{O}(\log n)$ complexity.
Nenhuma solução correta