I found in different places on the internet how to turn a Binary Search Tree into an AVL tree in O(nlog(n)). I was wondering how can this be done in O(n) (as the worst case limit). It kinda seems possible with right rotations but I just don’t know how to implement it exactly. Any idea is welcomed.
3
If you don’t care about using extra memory then you can dump out the BST into a sorted array. Then you can balance the new tree perfectly.
tree balance(int[] array){
if(array.length == 0) return null;
Node n = new Node(array[$/2]);
n.left = balance(array[0..$/2]);
n.right = balance(array[$/2+1..$]);
return n;
}
This still needs to have the balance factor added.