BST to AVL in O(n) [closed]

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.


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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *