RBTree - baumstruktur darstellen

[snowblind]

Hi, ich programmier im Moment an einem Red-Black-Tree.
Nun will ich den erstmal so ausgeben, dass die Struktur richtig zu erkennen ist. Also z.b. so:

        root
   .----+----.
left           right

Oder von mir aus auch "von links nach rechts" (statt oben-unten).

...Ich hab auch anderswo bzw hier im Forum schonmal gesucht, aber nix sehr brauchbares gefunden. Hier z.b. *click*, leider komm ich mit dem Code nich so wirklich zurecht, hab schon bissle damit rumprobiert, hat aber nie geklappt (entweder null pointer exceptions, oder er schreibt mir nur <null> überall hin...^^')
Mein Baum ist "normal" aufgebaut, also root, leftChild, rightChild, usw.
Wenn ihr irgendwelche Code-Stücke braucht, sagt bescheid ^^"

...Was ich übrigens schon hinbekommen hab, war ne ähnliche Ausgabe wie:

        aa
    bb
        cc
dd
        ee
    ff
        gg

Wobei das aber insofern dumm is, dass keine Äste sichtbar sind, bzw, wenn nun z.b. da, wo das ee steht, <null> wäre, die zeile einfach weggelassen wird, und die Struktur nun nimmer so toll aussieht wie vorher.

...Ich hoffe ihr könnt mir irgendwie helfen, bin schon seit Tagen am probiern und komm auf keinen grünen Zweig...^^"

Danke, snow

 

[HLX]

Wenn ihr irgendwelche Code-Stücke braucht, sagt bescheid ^^"

bescheid

Zeig uns mal, was du schon hast.

 

[snowblind]

import MyExceptions.NodeAlreadyGivenException;
import MyExceptions.NodeNotFoundException;
import MyExceptions.TreeEmptyException;
import MyExceptions.TypeException;
/**
 * Erzeugt einen Binaer-Baum
 */
public class Tree {
    private Node root; // Die Wurzel des Baumes   

    /**
     * Konstruktor fuer den Baum
     * Die Wurzel zeigt auf null
     * Das Array ist leer
     */
    public Tree() {               
        root = null;     
    }   
    
    /**
     * loescht einen Knoten
     * 
     * @param key	Der Knoten der geloescht werden soll
     * @return	true, wenn der Knoten gefunden und geloescht wurde
     * @throws Exception	NodeNotFoundException wenn Knoten nicht gefunden wird
     */
    public boolean delete(Object key) throws Exception {		
        Node x,y,z; 
        z = root; 
        while (z != null) { 
        	if(((Comparable)key).compareTo(z.key) == 0)	
                break;        
            else 
                if ((((Comparable)key).compareTo(z.key) < 0)) 
                    z = z.leftChild; 
                else  
                    z = z.rightChild; 
        } 
        if(z == null) {
        	NodeNotFoundException.main(key);
        	return false; 
        }
        if(z.leftChild == null || z.rightChild == null) 
            y = z; 
        else { 
            y = z.rightChild; 
            while (y.leftChild != null) y = y.leftChild; 
        } 
        if(y.leftChild != null) 
            x = y.leftChild; 
        else 
            x = y.rightChild;          
        if(x != null)
        	x.parent = y.parent; 
        if(y.parent != null) 
            if (y == y.parent.leftChild) 
                y.parent.leftChild = x; 
            else 
                y.parent.rightChild = x; 
        else 
            root = x; 
        if(y != z) { 
            y.leftChild = z.leftChild; 
            if(y.leftChild != null) 
            	y.leftChild.parent=y; 
            y.rightChild = z.rightChild; 
            if(y.rightChild != null)
            	y.rightChild.parent = y; 
            y.parent = z.parent; 
            if(z.parent != null) 
                if (z == z.parent.leftChild) 
                    z.parent.leftChild = y; 
                else 
                    z.parent.rightChild = y;  
            else  
                root = y;  
        } 
    return (true); 
    } // Ende von delete
    
    /**
     * sucht einen Knoten im Baum
     * @param key	der Knoten der gesucht wird
     * @return	der Knoten der gesucht wird,
     * 			oder null wenn er nicht gefunden wurde
     * @throws Exception TreeEmptyException wenn der baum leer ist
     */    
    public Node find(Object key) throws Exception {     // find node with given key
    	TreeEmptyException.main(root);                  // (assumes non-empty tree)
        Node current = root;
        while (!current.key.equals(key)) {
        	if (((Comparable)key).compareTo(current.key) < 0)
        		current = current.rightChild;
        	else
        		current = current.leftChild; 
        	if (current.rightChild == null || current.leftChild == null)	
        		return (null);	
        }
        return (current);	
    }  // end find()
        
    /**
     * fuegt einen Knoten in den Baum ein
     * @param newNode	der neue Knoten
     * @throws Exception	TypeException wenn der KNoten ungleich den Typ der Wurzel ist
     */
    public void einfuegen(Node newNode) throws Exception {
    	TypeException.main(root, newNode);
    	insert(newNode, root, null);
    }
    
    public void insert (Node newNode, Node k, Node parent) throws Exception {
    	if (root == null) {
    		root = newNode;
    	} else {
    		if (k == null) {        		
        		if(((Comparable)newNode.key).compareTo(parent.key) < 0) {
        			parent.leftChild = newNode;
        			newNode.parent = parent;
        		}
        		else {
        			parent.rightChild = newNode;
        			newNode.parent = parent;
        		}
        		k = newNode;
        	}
        	else {
        		if(((Comparable)newNode.key).compareTo(k.key) < 0)
        			insert(newNode, k.leftChild, k);
        		else if(((Comparable)newNode.key).compareTo(k.key) > 0)
        			insert(newNode, k.rightChild, k);
        		else 
        			throw new NodeAlreadyGivenException(newNode.toString());     			
        	}
    	}
    }    
    
    /**
     * toString methode indem der Baum traversiert wird
     * @throws Exception	TreeEmptyException wenn der Baum leer ist
     */
    public void ausgeben() throws Exception  {
    	if(root != null) {
    		System.out.println(">>> BinTree (traversieren):");		
    		inOrder(root);
    		System.out.println("\n");
    	} else 
    		throw new TreeEmptyException();
    }
    
    public void inOrder(Node k) {
    	if(k.leftChild != null) { 
    		inOrder(k.leftChild); 
    	}   	
    	k.displayNode();
    	if(k.rightChild != null) { 
    		inOrder(k.rightChild); 
    	}   	
    }    
    
    public void ausgebenAlsBaum() {
    	ausgebenAlsBaum(root, 0);
    }
    
    public void ausgebenAlsBaum(Node n, int tiefe) {
    	if(n.rightChild != null)
    		ausgebenAlsBaum(n.rightChild, tiefe+1);
    	
    	for(int i = 0; i < tiefe; i++)
    		System.out.print("\t");
    	System.out.print(n.key + "\n");
    	
    	if(n.leftChild != null)
    		ausgebenAlsBaum(n.leftChild, tiefe+1);
    }

}

/**
 * Die Klasse Node dient der Klasse Tree; Der Tree besteht aus Nodes.
 * Jeder Knoten hat einen Vater bis zu zwei Kindern.
 * Ausserdem hat er ein DatenObjekt und ein key-Objekt, das die Sortierung
 * des Baumes bestimmt.
 */
public class Node {
    public Object key;			// der schluessel, für die Sortierung
    public Object data;			// die Daten des Knotens
    public Node leftChild;		// linkes Kind des Knoten
    public Node rightChild; 	// rechtes Kind des Knoten
    public Node parent;			// Vater des Knoten
          
    /**
     * erzeugt ein Node-Objekt
     * @param key	Schluessel
     * @param data	Daten
     */
    public Node(Object key, Object data) {
    	this.key = key;
    	this.data = data;
    }
    
    /**
     * Ermöglicht die Ausgabe des Knoten
     */
    public void displayNode() { 
        System.out.print('{');
        System.out.print(this.toString());
        System.out.print("}");
    }
    
    /**
     * toString Methode des Knoten
     */
    public String toString() {    	
        	String erg = this.key + " : " + this.data;
            return erg;
        }
        	 

}

Das ist jetzt die normale Tree-Klasse. Den Red-Black-Tree wollte ich davon ableiten, damit bin ich halt noch nicht ganz fertig, wollte jetzt erstmal ne gescheite Baum-Ausgabe (direkt in der Tree-Klasse) implementiern, damit ich die Rotations-Methoden kontrolliern kann, die ich für RBTree schreibe.

Hoffe das langt, wenn du noch mehr Code brauchst sag bescheid ^^

 

[HLX]

Ok. In dem Code gibt es sicher noch eine Menge Änderungsbedarf. Beispielimplementierungen für einen RB-Tree findest du leicht über Google.

Bei der reihenweise Ausgabe könnte dies helfen:

void print(List aktRow) {
    List newRow = new ArrayList();
    if (aktRow == null) {
        newRow.add(root);
    }
    else {
        for (Iterator<Node> iter = aktRow.iterator(); iter.hasNext();) {
            Node node = (Node) iter.next();
            if (node.leftChild != null) {
                newRow.add(node.leftChild);
            }
            if (node.rightChild != null) {
                newRow.add(node.rightChild);
            }
        }
    }
    if (!newRow.isEmpty()) {
        System.out.println(newRow);
        print(newRow);
    }
}

Aufruf über print(null).

Damit die einzelnen Knoten noch schön versetzt ausgegeben werden müsstest du allerdings noch irgendwie jeweils einen offset mitgeben.

 

[snowblind]

Hi HLX,

Danke für dein Beispiel, jedoch funktioniert es bei mir nicht richtig. Bei der implementierung wollte er newRow immer als ArrayList casten, und dann kommt es entweder zu einer ClassCastException oder es kommt einfach gar keine Ausgabe.
Ausserdem befürchte ich, dass das eh nicht das is was ich suche...Ich denke, das ist auch wieder nur sowas, wo dann in jeder ausgabezeile ein Knoten ausgegeben wird, und halt je nach "Entfernung zur Wurzel" entsprechend eingerückt ist.
Mein Problem ist ja aber, dass ich wissen möchte, wie ich zeichen wie -| oder + usw einfügen muss, dass daraus eine richtige Baumstruktur entsteht, an der man sehen kann, welcher Knoten mit welchem anderen über einen Ast verbunden ist (Siehe mein erster Post).

 

[HLX]

Hi HLX,

Danke für dein Beispiel, jedoch funktioniert es bei mir nicht richtig. Bei der implementierung wollte er newRow immer als ArrayList casten, und dann kommt es entweder zu einer ClassCastException oder es kommt einfach gar keine Ausgabe.

Wo gibt es denn bei newRow was zu casten? In welcher Zeile passiert das?

Ausserdem befürchte ich, dass das eh nicht das is was ich suche...Ich denke, das ist auch wieder nur sowas, wo dann in jeder ausgabezeile ein Knoten ausgegeben wird, und halt je nach "Entfernung zur Wurzel" entsprechend eingerückt ist.

Nein, die Ausgabe gibt Knoten, die auf gleicher Tiefe sind in einer Zeile aus. Die Liste ist dafür ein Hilfsmittel. Allerdings sind diese wie gesagt noch nicht eingerückt. Die Einrückung müsstest du noch für jeden Knoten ermitteln und separat ablegen (damit sich Kinder-Knoten an ihrem Eltern-Knoten ausrichten können).

 

[snowblind]

Hi,
Sorry erstmal dass ich so lang nix mehr hören lassen hab, ich hab viel am Hut, und muss hier einen dummen Baum nach dem nächsten schreiben :-0
Also, hier bidde:

Wo gibt es denn bei newRow was zu casten? In welcher Zeile passiert das?

Siehe unten: Entweder so, oder er will halt statt List newRow ein ArrayList newRow...

void print(List aktRow) {
	    List newRow = (List) new ArrayList();
	   ...

Und so weiter...Daraus resultieren dann noch andere Fehler, ich versteh nich alles, irgendwas stimmt wohl mit den Generics nicht (kenn mich mit Generics überhaupt nich aus, sorry) und wegen dem Cast spielt das alles verrückt.

Nein, die Ausgabe gibt Knoten, die auf gleicher Tiefe sind in einer Zeile aus. Die Liste ist dafür ein Hilfsmittel. Allerdings sind diese wie gesagt noch nicht eingerückt. Die Einrückung müsstest du noch für jeden Knoten ermitteln und separat ablegen (damit sich Kinder-Knoten an ihrem Eltern-Knoten ausrichten können).

Hm, ja gut, und das is halt das Problem...Erstens, wie kann ich die Knoten untereinander richtig einrücken und mit Strichen (als Äste) verbinden, und zweitens, wie kann ich auch die nicht besetzten (=null) Knoten zeichnen, die bis zur untersten Ebene sichtbar sein sollten (Damit der Baum halt einsehbar ist?)?

Ich hab das ganze mittlerweile mal so hinbekommen, is leider ein Bisschen viel Code, ihr könnts ja einfach mal zu dem Rest von mir dazufügen und anschaun:

public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("Ausgabe des Baumes:\n\n");
		int zaehler = 1;
		Stack<Node> globalStack = new Stack<Node>();
		globalStack.push(getRoot());
		int nBlanks = 32;
		boolean isRowEmpty = false;
		while (isRowEmpty == false) {
			Stack<Node> localStack = new Stack<Node>();

			isRowEmpty = true;
			for (int j = 0; j < nBlanks; j++)
				sb.append(' ');
			while (globalStack.isEmpty() == false) {
				zaehler++;
				Node temp = globalStack.pop();
				if (temp != null) {
					sb.append(temp);
					// sb.append("ö");
					localStack.push(temp.getLeftChild());
					localStack.push(temp.getRightChild());

					if (temp.getLeftChild() != null
							|| temp.getRightChild() != null)
						isRowEmpty = false;
				} else {
					sb.append(NULLNODE);
					localStack.push(null);
					localStack.push(null);
				}
				for (int j = 0; j < nBlanks * 2 - 2; j++)
					sb.append(' ');
			}
			sb.append("\n");

			nBlanks /= 2;

			// //////hier noch / und \ dazu

			for (int i = 1; i <= zaehler / 2; i++) {
				for (int j = 0; j < nBlanks + 3; j++)
					sb.append(' ');
				sb.append("/");
				for (int j = 0; j < nBlanks * 2 -4; j++)
					sb.append('¯');
				// sb.append('=');
				sb.append("\\");
			}
			sb.append("\n");

			// ///////////////////////////////////

			while (localStack.isEmpty() == false)
				globalStack.push(localStack.pop());
		}
		return sb.toString();
	}

Ich zeig mal die Ausgabe dazu:

                                               ee                                                              
                   /¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯\
                "bb"                              "gg"                              
           /¯¯¯¯¯¯¯¯¯¯¯¯\           /¯¯¯¯¯¯¯¯¯¯¯¯\
        aa              cc              ff              zz              
       /¯¯¯¯\       /¯¯¯¯\       /¯¯¯¯\       /¯¯¯¯\
    --      --      --      --      --      --      "yy"      --      
     /\     /\     /\     /\     /\     /\     /\     /\

(Das ee steht normal in der mitte vom oberen Ast, also ganz richtig, es stimmt hier nur das Format von dem Java Code nich so ganz oder so, weiss nicht genau ^^'
Wie ihr nun aber auch sehn könnt, wir das ganze circa ab der 4. Ebene etwas ungenau...Es verrückt alles umso mehr, je mehr man nach unten kommt.
Vielleicht ist mein Ansatz nicht so gut, oder kann man das Verrücken vielleicht auch einfach beheben?

Grüße, snow

 

[sayang]

SCNR

musste grad fast kotzen, da ich bei dem Titel an mein Studium erinnert wurde... naja, der Prof halt
Haben das damals in Swing programmiert. Aber denke nicht, dass ich das Programm noch irgendwo wiederfinden werde. Sorry.

Lg
sayang