[JAVA] Albero autobilanciato

[sicula83]

Ciao ragazzi stavo svolgendo questo esercizio; ecco qui il testo:
http://www.dmi.unict.it/~faro/prog2/...8/zg8rfct2.pdf

Non so implementare solamente il metodo selfBallace(); in pratica a ricevimento il professore mi ha consigliato di non implementare right rotate e left rotate, bensì utilizzare una coda e poi richiamare una preorder per creare l'albero riempendo i nodi da sx a dx, così da averlo bilanciato.

Ecco il codice che ho fatto finora:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */



/**
 *
 
 */
//import java.lang.RuntimeException;
//import java.util.Queue;
import java.util.LinkedList;
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws Exception {
        // TODO code application logic here
        AlberoBilanciato a=new AlberoBilanciato();
        a.insert("C");
        a.insert("D");
        a.insert("B");
        a.insert("A");
        a.preorder();
        System.out.println("Altezza albero "+a.height());
        System.out.println("Size albero "+a.size());
        System.out.println("L'albero è bilanciato? "+a.isBallanced(a.root));
        System.out.println("Size del nodo B "+a.size(a.root.left));
        System.out.println("Cancellazione di un elemento");
        a.delete("C");
        a.preorder();
        System.out.println(a.Left(a.root()).info);
        System.out.println("L'albero è bilanciato? "+a.isBallanced(a.root));
        a.selfBallance();
        System.out.println("L'albero è bilanciato? "+a.isBallanced(a.root));
    }

}
interface SelfBallancedTree
{
    public int size();
    public BTNode root() throws EmptyTreeException;
    public BTNode left(BTNode x) throws InvalidArgumentException;
    public BTNode right(BTNode x) throws InvalidArgumentException;
    public BTNode parent(BTNode x) throws InvalidArgumentException;
    public int size(BTNode x) throws InvalidArgumentException;
    public void insert(String s);
    public BTNode delete(String s);
    public boolean isBallanced(BTNode x);
    public void selfBallance();  //Mi manca questo solamente
}
class BTNode
{
    protected String info; //info nodo
    protected BTNode parent,left,right;

    public BTNode()
    {
        info=null;
        parent=left=right=null;
    }
    public BTNode(String in)
    {
        info=in;
        parent=left=right=null;
    }
    public void visit()
    {
        System.out.println(" "+info);
    }

}
class AlberoBilanciato implements SelfBallancedTree
{
    protected BTNode root;
    protected int size,height;

    public AlberoBilanciato()
    {
        root=null;
        size=0;
        height=0;
    }
    public int size(){return size;}
    public int height(){return getAltezzaNodo(root);}
    public BTNode root(){return root;}
    public boolean isBallanced(BTNode x)
    {
        int bf=getAltezzaNodo(x.left)-getAltezzaNodo(x.right);
        return ((bf>=-1)&& (bf<=1));
    }
    public BTNode left(BTNode x) throws InvalidArgumentException
    {
        BTNode tmp=Search(x.info);
        BTNode te=tmp.left;
        if(te==null)
            throw new InvalidArgumentException("Left non presente");
        return te;
    }
    public BTNode Left(BTNode x) throws InvalidArgumentException
    {
        if(x==null)
            throw new InvalidArgumentException("");
        return x.left;
    }
    public BTNode right(BTNode x) throws InvalidArgumentException
    {
        BTNode tmp=Search(x.info);
        BTNode te=tmp.right;
        if(te==null)
            throw new InvalidArgumentException("Right non presente");
        return te;
    }
    public BTNode parent(BTNode x) throws InvalidArgumentException
    {
        BTNode tmp=Search(x.info);
        BTNode te=tmp.parent;
        if(te==null)
            throw new InvalidArgumentException("Right non presente");
        return te;
    }
    public BTNode Search(String info)
    {
        BTNode p=root;
        while(p!=null)
        {
            int res=((Comparable)info).compareTo(p.info);
            if(res==0)
                return p;
            else if(res>0)
                p=p.right;
            else
                p=p.left;
        }
        return null;
    }
    public void insert(String s)
    {
        BTNode d=new BTNode(s);
        if(root==null)
            root=d;
        else
        {
            BTNode p=root,pred=null;
            while(p!=null)
            {
                if(s.equals(p.info))
                    return;
                pred=p;
                if(s.compareTo(p.info)<0)
                    p=p.left;
                else
                    p=p.right;
            }
            if(s.compareTo(pred.info)<0)
            {
                pred.left=d;
                d.parent=pred;
            }
            else
            {
                pred.right=d;
                d.parent=pred;
            }
        }
        size++;
    }
    public void inorder()
    {
        inorder(root);
    }
    public void inorder(BTNode p)
    {
        if(p!=null)
        {
            inorder(p.left);
            p.visit();
            inorder(p.right);
        }
    }
    public void preorder()
    {
        preorder(root);
    }
    public void preorder(BTNode p)
    {
        if(p!=null)
        {
            p.visit();
            preorder(p.left);
            preorder(p.right);
        }
    }
    public int getAltezzaNodo(BTNode p)
    {
        return getAltezzaNodo(p,0);
    }
    public int getAltezzaNodo(BTNode p,int altezza)
    {
        if(p!=null)
        {
            if(p.left==null && p.right==null)
                return altezza;
            else
            {
                int a=getAltezzaNodo(p.left,altezza+1);
                int b=getAltezzaNodo(p.right,altezza+1);
                if(a>b)
                    return a;
                else
                    return b;
            }
        }
        return altezza-1;
    }
    public int size(BTNode x) throws InvalidArgumentException
    {
        if(x==null)
        {
            return 0;
        }
        else
        {
            int nodisx=size(x.left);
            int nodidx=size(x.right);
            return 1+nodisx+nodidx;
        }
    }
    public BTNode min(BTNode y)
    {
        BTNode x=Search(y.info);
        while(x.left!=null)
            x=x.left;
        return x;
    }
    public BTNode successore(BTNode y)
    {
        BTNode x=Search(y.info);
        if(x.right!=null)
            return min(x.right);
        y=x.parent;
        while(x!=null && x==y.right)
        {
            x=y;
            y=y.parent;
        }
        return y;
    }
    public BTNode delete(String s)
    {
        BTNode x=new BTNode(s);
        BTNode z=Search(x.info);
        BTNode y;
        if(z.left==null || z.right==null)
        {
            y=z;
        }
        else
            y=successore(z);
        if(y.left!=null)
            x=y.left;
        else
            x=y.right;
        if(x!=null)
            x.parent=y.parent;
        if(y.parent==null)
            root=x;
        else 
            if(y.parent.left==y)
                y.parent.left=x;
            else
                y.parent.right=x;
        if(y!=z)
            z.info=y.info;
        return y;
    }
    public void selfBallance()
    {
        if(this.isBallanced(root))
            System.out.println("Non è necessario il bilanciamento");
        else
            //System.out.println("Applicarlo");
        {
            BTNode p=root;
            preordercrea(p);
        }
     }
     public void preordercrea(BTNode p)
     {
         if(p!=null)
         {
             Coda c=new Coda();
             c.enQueue(p.info);
             while(p.left!=null || p.right!=null)
             {
                 c.enQueue(p.left);
                 c.enQueue(p.right);
             }
             size++;
         }
     }

}
class Coda{
	protected NodoL head;
	protected NodoL tail;
	public Coda(){
		head=tail=null;
	}

	public boolean isEmpty(){
		return head==null;
	}

	public void enQueue(Object info){
		NodoL x = new NodoL(info);
		if(isEmpty())
			head=tail=x;
		else{
			tail.setNext(x);
			tail=x;
		}
	}

	public Object deQueue() {
		try{
		if(isEmpty())
			throw new InvalidArgumentException("ERRORE: la coda e' vuota. Impossibile estrarre elementi");
		else{
			Object ret = head.getInfo();
			head=head.getNext();
			return ret;
		}
	}catch(Exception e){ System.out.println(e.getMessage());
		return null;}
	}

	public Object readHead(){
		try{
		if(isEmpty())
			throw new InvalidArgumentException("ERRORE: la coda e' vuota. Impossibile leggere elementi");
		else
			return head.getInfo();
		}catch(Exception e){ System.out.println(e.getMessage());
		return null;}
	}

	public void makeEmpty(){
		head=tail=null;
	}

	public String toString(){
		String str="";
		if(isEmpty())
			str+="La coda e' vuota...";
		else{
			str+="<- ";
			NodoL aux=head;
			for(; aux!=null; aux=aux.getNext())
				str+=aux.getInfo()+" ";
			str+=" <-";
		}
		return str;
	}

}
class NodoL{
	private Object info;
	private NodoL next;

	public NodoL(Object info){
		this(info,null);
	}

	public NodoL(Object info, NodoL next){
		this.info=info;
		this.next=next;
	}

	public void setInfo(Object info){
		this.info=info;
	}

	public Object getInfo(){
		return info;
	}

	public void setNext(NodoL next){
		this.next=next;
	}

	public NodoL getNext(){
		return next;
	}

	public String toString(){
		return ""+info;
	}
}
class InvalidArgumentException extends Exception
{
    public InvalidArgumentException() {
    }


    /**
     * Constructs an instance of <code>InvalidArgumentException</code> with the specified detail message.
     * @param msg the detail message.
     */
    public InvalidArgumentException(String msg) {
        super(msg);
    }
}
class EmptyTreeException extends Exception
{
    public EmptyTreeException(){

    }
    public EmptyTreeException(String msg){
        super(msg);
    }
}