Praktikum Algorithmische Anwendungen

Wintersemester 2003/04

Praktikum 3

 

Gruppe AI A1
Michael Boiman 11027800 ai320
M. Serhat Çinar 11030409 ai440
Mustafa Ekit 11027589 ai336

 

Index

  • Projekt 3: Intervallbäume mit einem RedBlack Tree als Datenstruktur
  • Aufgabe 1: Implementierung eines Rotate (left oder right) mit Korrektur der Max-Werte in O(1)
  • Aufgabe 2: Intervallsearch mit offenen Intervallen
  • Aufgabe 3: IntervallSearchMin
  • Aufgabe 4: Implementierung von Insert, Delete und Search
  • Aufgabe 5: Implementierung der GUI
  • Dateien und Javadoc
  •  


    Projekt 3: Intervallbäume mit einem RedBlack Tree als Datenstruktur     top

    "Erweitern Sie die Implementation der Rot-Schwarz-Bäume aus Projekt 1, so dass die Basis-
    Operationen auf Intervallbäumen effizient (O(log n) bzw. O(1)) ausgeführt werden. Dazu
    müssen in den Knoten der Rot-Schwarz-Bäume Zusatzinformationen gespeichert werden.
    Bitte bearbeiten Sie folgende Aufgaben, dokumentieren Sie Ihre Lösungen und stellen Sie die
    Dokumentation auf Ihrer Homepage bereit.
    "

    Zuerst wurde erneut eine Aufteilung der Aufgaben erstellt:
    Michael Boiman: Insert- / Delete-Erweiterung, Dokumentation
    Mustafa Ekit: IntervallSearchFirst und IntervallSearchMin, Dokumentation
    M. Serhat Cinar: Vorlage einer Intervallklasse, Erweiterung der GUI, Rotate, Projektmanagement

     Als Grundlage diente die Klasse RedBlackTree.java aus der API "structure" von Duane A. Bailey, Avan S. Sandhaus, in der modifizierten Version aus dem Praktikum 2.

    Als erstes wurde eine Klasse Intervall erstellt, die im OO-Sinne sinnvolle Methoden für das Arbeiten mit Intervallen.
    Kern dieser Klasse sind die Methoden equals, compareTo und overlap:

    /**
     * Vergleicht zwei Intervalle auf Gleichheit.
     * Zwei Intervalle sind nur dann gleich, wenn ihre low und high Werte übereinstimmen
     * und beide Intervallgrenzen gleichen Typs sind, also offen oder geschlossen.
     * Offene oder geschlossene Intervallgrenzen werden berücksichtigt. 
     * @see java.lang.Object#equals(java.lang.Object)
     */
    public boolean equals(Object o){
    	if (o instanceof Intervall){
    		Intervall i = (Intervall) o;
    		if (i.getHigh()==getHigh() && 
    			i.getLow()==getLow() && 
    			i.isLeftOpen()==isLeftOpen() &&
    			i.isRightOpen()==isRightOpen())
    			return true;
    		else return false; 
    	}
    	else return false;
    }
    
    /**
     * a negative integer, zero, or a positive integer as this 
     * object is less than, equal to, or greater than the specified object.
     * Offene oder geschlossene Intervallgrenzen werden berücksichtigt.
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    public int compareTo(Object o) throws ClassCastException{
    	if (o instanceof Intervall){
    		Intervall other = (Intervall) o;
    		if (isLeftOpen() && !other.isLeftOpen()){
    			if (getLow()<=other.getLow()) return -1;
    			// (getLow()>other.getLow())
    			else return 1;
    				 
    		}
    		else if (!isLeftOpen() && other.isLeftOpen()){
    			if (getLow()<other.getLow()) return -1;
    			// (getLow()>=other.getLow())
    			else return 1;
    		}
    		else{
    			//!isLeftOpen() && !other.isLeftOpen()
    			// oder isLeftOpen() && other.isLeftOpen()
    			if (getLow()<other.getLow()) return -1;
    			else if (getLow()>other.getLow()) return 1;
    			else return 0;
    		}
    	}
    	else throw new ClassCastException();
    }
    
    /**
     * Testet, ob das gegebene Intervall sich mit diesem Intervall überscheidet.
     * Offene oder geschlossene Intervallgrenzen werden berücksichtigt.
     * @param i Intervall, mit dem verglichen werden soll.
     * @return true falls beide Intervalle sich überlappen, false sonst.
     */
    public boolean overlap(Intervall i) {
    	// |--------| i
    	//        |-----| this
    	// linksbedingung : i.getLow() <= getHigh()
    	// rechtsbedingung: getLow() <= i.getHigh()
    	
    	boolean leftcondition = false;
    	if (! i.isLeftOpen() && ! isRightOpen()){
    		// geschlossene intervalle
    		if (i.getLow() <= getHigh()) leftcondition = true;
    	}
    	else{
    		// mindestens eines ist offen
    		if (i.getLow() < getHigh()) leftcondition = true;
    	}
    	
    	boolean rightcondition = false;
    	if (! i.isLeftOpen() && ! isRightOpen()){
    		// geschlossene intervalle
    		if (getLow() <= i.getHigh()) rightcondition = true;
    	}
    	else{
    		// mindestens eines ist offen
    		if (getLow() < i.getHigh()) rightcondition = true;
    	}
    	
    	return leftcondition && rightcondition;
    }
    	  

    Des weiteren enthält die Klasse Hilfsmethoden zum Erzeugen von zufälligen Intervallen und Intervallen aus String-Repräsentationen.

    /**
     * Generiert zufällige Intervalle
     * @return Das zufällig generierte Intervall
     */
    public static Intervall createRandom(){
    	int low = rnd.nextInt(100);
    	int high = low+rnd.nextInt(100);
    	if (high==low) high++;
    	boolean isLowOpen = rnd.nextBoolean();
    	boolean isHighOpen = rnd.nextBoolean();
    	Intervall i = null;
    	try {
    		i = new Intervall(low, high, isLowOpen, isHighOpen);
    	}
    	// passiert nie
    	catch (LowBoundIsHigherThanHighBoundException e) {
    		e.printStackTrace();
    	}
    	// passiert nie
    	catch (LowBoundIsEqualToHighBoundException e) {
    		e.printStackTrace();
    	}
    	return i;
    }
    
    /**
     * Parst aus einem String ein Intervall.
     * Format: 
     * Geschlossene Intervallgrenzen: [ low ; high ]
     * Offene Intervallgrenzen: ] low ; high [
     * Die Intervallgrenzen können beliebig geschlossen oder offen sein.
     * Leerzeichen müssen nicht benutzt werden.
     * low sowie high sind Integer Zahlen, die dem Format der Klasse java.lang.Integer entsprechen.
     * @see java.lang.Integer#parseInt(String)
     * @param intervallstring String, der geparst werden soll.
     * @return Intervall, das aus dem String erzeugt wurde.
     * @throws ParseException
     * @throws LowBoundIsHigherThanHighBoundException
     * @throws LowBoundIsEqualToHighBoundException
     */
    public static Intervall parseString(String intervallstring) throws
    	ParseException, LowBoundIsHigherThanHighBoundException, 
    	LowBoundIsEqualToHighBoundException
    {
    	if (intervallstring == null)
    		throw new ParseException("Given token is null", 0);
    	if (intervallstring.length() <= 0)
    		throw new ParseException("Given token is empty", 0);
    	
    	intervallstring = intervallstring.trim();
    	int length = intervallstring.length();
    	
    	char leftBound = intervallstring.charAt(0);
    	boolean isLeftOpen;
    	if (leftBound=='[') isLeftOpen = false;
    	else if (leftBound==']') isLeftOpen = true;
    	else throw new ParseException("Missing [ or ] at begin.", 0); 
    	
    	
    	char rightBound = intervallstring.charAt(length-1);
    	boolean isRightOpen;
    	if (rightBound=='[') isRightOpen = true;
    	else if (rightBound==']') isRightOpen = false;
    	else throw new ParseException("Missing [ or ] at end.", length-1); 
    	
    	int boundseperator = intervallstring.indexOf(';');
    	if (boundseperator<0)
    		throw new ParseException("Missing ; as truncator.", 1);
    	
    	String sleftbound = intervallstring.substring(1, boundseperator);
    	sleftbound = sleftbound.trim();
    	int ileftbound = Integer.parseInt(sleftbound);
    	
    	String srightbound = intervallstring.substring(boundseperator+1, length-1);
    	srightbound = srightbound.trim();
    	int irightbound = Integer.parseInt(srightbound);
    	
    	return new Intervall(ileftbound, irightbound, isLeftOpen, isRightOpen);
    }
    	  

     MSC

     


    Aufgabe 1: Implementierung eines Rotate (left oder right) mit Korrektur der Max-Werte in O(1)     top

    Rotate

    Ausgangssituation:

     

    Rotate Left

    Das Rotate-Left wird am Knoten 2 ausgeführt:
    RedBlackIntervallTree parent = getParent(); // could be null
    RedBlackIntervallTree newRoot = getRight();
    // is the this node a child; if so, a left child?
    boolean wasChild = !isRoot();
    boolean wasRightChild = isRightChild();
    
    // hook in new root (sets newRoot's parent, as well)
    setRight(newRoot.getLeft());
    
    // put pivot below it (sets this's parent, as well)
    newRoot.setLeft(this);
    
    if (wasChild) {
    	if (wasRightChild)
    		parent.setRight(newRoot);
    	else
    		parent.setLeft(newRoot);
    }
    

     Dabei werden die Knoten 2 (this),

    7 (right bzw. newRoot) und 11 (parent) verändert.
    Ihre Maxwerte sind zu prüfen. Die anderen Teilbäume (5, 8 und 1) werden nicht verändert, behalten also ihre Maxwerte.
    Zur Korrektur der Maxwerte geht man von unten nach oben vor, da die Maxwerte so ihre Gültigkeit für ihre Eltern erhalten.
    Der Maxwert von 2 ist entweder der Maxwert des linken Kindes, der des rechten Kindes oder sein eigener:
    // max this korrigieren
    int thismax;
    int leftmax;
    int rightmax;
    
    thes.setMax(((Intervall)thes.getIntervall()).getHigh());
    if (thes.getLeft() != EMPTY){
    	thismax = thes.getMax();
    	leftmax = thes.getLeft().getMax();
    	if (leftmax>thismax) 
    		thes.setMax(thes.getLeft().getMax());
    }
    if (thes.getRight() != EMPTY){
    	thismax = thes.getMax();
    	rightmax = thes.getRight().getMax();
    	if (rightmax>thismax)
    		thes.setMax(thes.getRight().getMax());
    }
    
    Der Maxwert von 7 (hier newRoot) ist entweder der Maxwert des linken Kindes (2), der Maxwert des rechten Kindes oder der eigene Highwert:
    //		max von newRoot korrigieren
    int rootmax;
    newRoot.setMax(((Intervall)newRoot.getIntervall()).getHigh());
    if (newRoot.getLeft() != EMPTY){
    	rootmax = newRoot.getMax();
    	leftmax = newRoot.getLeft().getMax();
    	if (leftmax>rootmax) 
    		newRoot.setMax(newRoot.getLeft().getMax());
    }
    if (newRoot.getRight() != EMPTY){
    	rootmax = newRoot.getMax();
    	rightmax = newRoot.getRight().getMax();
    	if (rightmax>rootmax) 
    		newRoot.setMax(newRoot.getRight().getMax());
    }
    
    Der Maxwert von 11 (hier parent) ist entweder der Maxwert des linken Kindes (7), der Maxwert des rechten Kindes oder der eigene Highwert:
    //		max von parent korrigieren
    if (parent!=null){
    	int parentmax;
    	parent.setMax(((Intervall)parent.getIntervall()).getHigh());
    	if (parent.getLeft() != EMPTY){
    		parentmax = parent.getMax();
    		leftmax = parent.getLeft().getMax();
    		if (leftmax>parentmax) 
    			parent.setMax(parent.getLeft().getMax());
    	}
    	if (parent.getRight() != EMPTY){
    		parentmax = parent.getMax();
    		rightmax = parent.getRight().getMax();
    		if (rightmax>parentmax) 
    			parent.setMax(parent.getRight().getMax());
    	}
    }	
    
    Die gesamte Korrektur benötigt 3 Rechenschritte und ist somit in O(1) erledigt. Sie wird in eine Funktion ausgelagert, da die Korrektur für das Rotate-Right genauso aussieht:
    /**
     * Korrigiert die Max-Werte der an einer Rotation beteiligten Knoten.
     * @param thes Der aktuelle Knoten, um den rotiert wurde
     * @param newRoot Der Knoten, der an die stelle des aktuellen Knoten rotiert wurde
     * @param parent Der Vater des aktuellen Knoten, bzw. nach der Rotation der Vater von newRoot
     */
    private void fixupMaxAfterRotate(RedBlackIntervallTree thes, RedBlackIntervallTree newRoot, RedBlackIntervallTree parent){
    	// max this korrigieren
    	int thismax;
    	int leftmax;
    	int rightmax;
    	
    	thes.setMax(((Intervall)thes.getIntervall()).getHigh());
    	if (thes.getLeft() != EMPTY){
    		thismax = thes.getMax();
    		leftmax = thes.getLeft().getMax();
    		if (leftmax>thismax) 
    			thes.setMax(thes.getLeft().getMax());
    	}
    	if (thes.getRight() != EMPTY){
    		thismax = thes.getMax();
    		rightmax = thes.getRight().getMax();
    		if (rightmax>thismax)
    			thes.setMax(thes.getRight().getMax());
    	}
    	
    	//		max von newRoot korrigieren
    	int rootmax;
    	newRoot.setMax(((Intervall)newRoot.getIntervall()).getHigh());
    	if (newRoot.getLeft() != EMPTY){
    		rootmax = newRoot.getMax();
    		leftmax = newRoot.getLeft().getMax();
    		if (leftmax>rootmax) 
    			newRoot.setMax(newRoot.getLeft().getMax());
    	}
    	if (newRoot.getRight() != EMPTY){
    		rootmax = newRoot.getMax();
    		rightmax = newRoot.getRight().getMax();
    		if (rightmax>rootmax) 
    			newRoot.setMax(newRoot.getRight().getMax());
    	}
    			
    	//		max von parent korrigieren
    	if (parent!=null){
    		int parentmax;
    		parent.setMax(((Intervall)parent.getIntervall()).getHigh());
    		if (parent.getLeft() != EMPTY){
    			parentmax = parent.getMax();
    			leftmax = parent.getLeft().getMax();
    			if (leftmax>parentmax) 
    				parent.setMax(parent.getLeft().getMax());
    		}
    		if (parent.getRight() != EMPTY){
    			parentmax = parent.getMax();
    			rightmax = parent.getRight().getMax();
    			if (rightmax>parentmax) 
    				parent.setMax(parent.getRight().getMax());
    		}
    	}	
    }
    
    Die Methode wird nach dem Rotieren aufgerufen:
    protected void rotateLeft() {
    	// all of this information must be grabbed before
    	// any of the references are set.  Draw a diagram for help
    	RedBlackIntervallTree parent = getParent(); // could be null
    	RedBlackIntervallTree newRoot = getRight();
    	// is the this node a child; if so, a left child?
    	boolean wasChild = !isRoot();
    	boolean wasRightChild = isRightChild();
    
    	// hook in new root (sets newRoot's parent, as well)
    	setRight(newRoot.getLeft());
    
    	// put pivot below it (sets this's parent, as well)
    	newRoot.setLeft(this);
    
    	if (wasChild) {
    		if (wasRightChild)
    			parent.setRight(newRoot);
    		else
    			parent.setLeft(newRoot);
    	}
    	
    	fixMaxAfterRotate(this, newRoot, parent);
    }
    

     MSC

     


    Aufgabe 2: Intervallsearch mit offenen Intervallen     top

    Die Methode "searchIntervall" gibt das Objekt im Intervallbaum zurück, dessen Intervall (int[x]) und das übergebene sich überlappen. Hier ändert sich die Suche zwischen offenen und geschlossenen Intervallen nicht, da die "Überlappungsfrage" in der Klasse Intervall bereits für beide Fälle gelöst wurde. Falls sich kein Intervall überschneidet, wird der
    Sentinel NIL zurückgegeben

    Durch die while-Bedingung wird es solange gesucht, bis es beim NIL ankommt und noch kein Objekt gefunden wurde, das sich mit dem Intervall i überlappt. Die if-Bedingung entscheidet zum welchen Kind es weiterlaufen soll. Falls der Max-Wert von linkes Kind grösser oder gleich der Anfangspunkt vom Intervall i ist, läuft es zum linkes Kind weiter. Ansonsten zum rechten Kind...

     ME

     


    Aufgabe 3: IntervallSearchMin     top

    Für ein gegebenes Intervall i wird dasjenige zurückgegeben, das sich mit i überlappt und den kleinsten Anfangspunkt hat.

    Hier ist im Gegensatz zu der der normalen Suche die while-Bedingung eingeschränkt (s. Zeile 7). Die Schleife läuft bis zu der Sentinel NIL, egal ob es schon einen überlappenden gefunden hat. Die if-Bedingung erhält hier noch die Vergleichung der Anfangspunkte vom linken und rechten Intervall...

     ME

     


    Aufgabe 4: Implementierung von Insert, Delete und Search     top

    Maxwert-Korrektur in INSERT

    Dafür wurde einfach in die alte Funktion add, nach einfügen des Knotens, aber vor der ausführung von setRed() und RedFix(), wird eine Schleife durchgeführt die Ihren eigenen Maxwert (durch vergleich des eigenen High Intervall und des Linken und Rechten Maxwert) ermittelt. Nach übernahme des Maxwertes wird die Funktion fixupMaxAfterInsertDelete aufgerufen um den rest von Baum zu den neuen Max wert zu korrigieren. Nach der Max wert korrektur am Baum werden die Funktionen SetRed() und RedFix() gestartet.
    public RedBlackIntervallTree add(Comparable c) {
    	System.out.println(this.getClass().getName()+".add("+c+")");
    	
    	RedBlackIntervallTree tree = insert(c); // first, do a plain insert
    	
    	
    	// Korrektur Max Wert des neuen Knotens
    	if (tree.getLeft() != EMPTY)
    		if (tree.getLeft().getMax()>tree.getMax()) tree.setMax(tree.getLeft().getMax());
    	if (tree.getRight() != EMPTY)
    		if (tree.getRight().getMax()>tree.getMax()) tree.setMax(tree.getRight().getMax());
    	
    	System.out.println(" max: "+tree.getMax());
    	
    	// Korrektur nach oben
    	if (!tree.isRoot()) fixupMaxAfterInsertDelete(tree);
    	
    	tree.setRed(); // we insert nodes as red nodes - a first guess
    	tree.redFixup(); // now, rebalance the tree
    	return tree.getRoot(); // return new root
    }
    	  
    Die Funktion fixupMaxAfterInsertDelete wird benutzt um den Baum nach oben bis zur Wurzel durchzugehen und zu verglichen, ob der neue Maxwert höher ist. Ist dies der Fall, wird der neue Max wert korrigiert und dann weiter nach oben überprüft, wenn nicht dann sind die Max werte des Baumes nach oben hin korrekt und die Funktion wird beendet.
    private void fixupMaxAfterInsertDelete(RedBlackIntervallTree fixupnode){
    	System.out.println(this.getClass().getName()+".fixupMaxAfterInsertDelete("+fixupnode.getIntervall()+")");
    	// Korrektur nach oben
    	RedBlackIntervallTree v = fixupnode.getParent();
    	RedBlackIntervallTree n = fixupnode;
    	/* 
    		max korrigieren, bis ein knoten gefunden wird, der
    		grösseren max wert hat.
    	*/
    	int vmax = v.getMax();
    	int nmax = n.getMax();
    	while (nmax > vmax){
    		v.setMax(n.getMax());
    		System.out.println(" korrektur: "+v.getIntervall()+": max: "+v.getMax()); 
    		n = v;
    		v = v.getParent();
    		if (v != null){
    			vmax = v.getMax();
    			nmax = n.getMax();
    		}
    		else{
    			// endbedingung vmax > nmax
    			vmax = 2;
    			nmax = 1;
    		}
    	}
    }
    	  

    Maxwert-korrektur in DELETE

    Die delete Funktion wurde auch fast gleich gelassen bis auf dass man am ende die Funktion fixupMaxAfterInsertDelete aufruft um die Änderungen nach oben zu korrigieren.
    public RedBlackIntervallTree remove(Comparable c) {
    	// find the target node - the node whose intervall is removed
    	RedBlackIntervallTree target = locate(c);
    	RedBlackIntervallTree parent = target.getParent();
    	
    	if (target.isEmpty()) return getRoot();
    
    	// determine the node to be disconnected:
    	// two cases: if degree < 2 we remove target node;
    	//            otherwise, remove predecessor
    	RedBlackIntervallTree freeNode;
    	if (target.getLeft().isEmpty()
    		|| target.getRight().isEmpty()) // simply re-root tree at right
    		{
    		// < two children: target node is easily freed
    		freeNode = target;
    	}
    	else {
    		// two children: find predecessor
    		freeNode = target.getLeft();
    		while (!freeNode.getRight().isEmpty()) {
    			freeNode = freeNode.getRight();
    		}
    		// freeNode is predecessor
    	}
    	
    	target.intervall = freeNode.intervall; // move intervall reference
    
    	// child will be orphaned by the freeing of freeNode;
    	// reparent this child carefully (it may be EMPTY)
    	RedBlackIntervallTree child;
    	if (freeNode.getLeft().isEmpty()) {
    		child = freeNode.getRight();
    	}
    	else {
    		child = freeNode.getLeft();
    	}
    
    	// if child is empty, we need to set its parent, temporarily
    	child.setParent(freeNode.getParent());
    	if (!freeNode.isRoot()) {
    		if (freeNode.isLeftChild()) {
    			freeNode.getParent().setLeft(child);
    		}
    		else {
    			freeNode.getParent().setRight(child);
    		}
    	}
    	
    	System.out.print(" target: "+target.getIntervall()+" freeNode: "+freeNode.getIntervall()+" child: "+child.getIntervall());
    	if (parent != null){ 
    		System.out.print(" parent: "+parent.getIntervall());
    		parent.setMax(((Intervall)parent.getIntervall()).getHigh());
    	}
    	System.out.println();
    	RedBlackIntervallTree fixupnode = null;
    	// child nimmt die position des gelöschten knoten ein
    	if (child != EMPTY) fixupnode = child;
    	// es gibt keinen ersatz für den gelöschten knoten.
    	// der vater des gelöschten knoten muss korrigiert werden.
    	else if (parent != null) fixupnode = parent;
    	
    	if (fixupnode != null){
    		// zu korrigierender knoten ist root. also nur sich selbst korrigieren.
    		if (fixupnode == getRoot())
    			fixupnode.setMax(((Intervall)fixupnode.getIntervall()).getHigh());
    		// bis zum root oder einem max-wert liefernden knoten korrigieren
    		else fixupMaxAfterInsertDelete(fixupnode);
    	}
    	
    	
    	// Assertion: child has been reparented
    	RedBlackIntervallTree result = child.getRoot();
    	if (freeNode.isBlack())	child.blackFixup();
    	return result.getRoot();
    }
    	  

     MB

      


    Aufgabe 5: Implementierung der GUI     top

    Zur Implementierung einer GUI wurde grösstenteils auf die GUI des Praktikums zu RedBalck Trees zurückgegriffen. Die GUI wurde lediglich um einige Funktionen erweitert (SearchMin, SearchFirst). Ausserdem wurde die GUI-Komponente zur Darstellung der Knoten so erweitert, dass alle notwendigen Informationen dargestellt werden konnten. Zusätzlich wurde eine weitere Panel Klasse erzeugt, die den Intervallbaum als grafische Intervalle repräsentiert.

     MSC


    Dateien und Javadoc     top

    Javadoc online
    Alle Dateien als Zip-Archiv