Ho trovato in diversi posti su Internet come trasformare un albero di ricerca binario in un albero AVL in O (nlog (n)). Mi chiedevo come si può fare in O (n) (come il limite peggiore). Sembra abbastanza possibile con rotazioni giuste ma non so come implementarlo esattamente. Qualsiasi idea è benvenuta.
Se non ti interessa usare la memoria extra, puoi scaricare il BST in un array ordinato. Quindi puoi bilanciare perfettamente il nuovo albero.
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;
}
Questo ha ancora bisogno di aggiungere il fattore di equilibrio.
Leggi altre domande sui tag big-o trees binary-tree