AuK/Sortierte Folgen SS12

Wiki-Quelltext dieser Seite.

<language>Java</language>
=Bäume=
Ein Baum ist eine zweidimensionale verkettete Datenstrucktur. Ein Baum definiert sich dadurch, dass er entweder leer ist oder er enhält ein Element und weitere Teilbäume. Ein Baum ist leer, wenn er nur aus einem äußeren und keinem inneren Knoten besteht. Somit ist ein Baum eine nicht leere Menge aus Knoten und Kanten. Der Nutzten eines Baumes beschäftigt sich mit der Strukturierung der inneren Knoten, die äußeren Knoten dienen lediglich als Platzhalter. Muss ein Knoten eine konkrete Anzahl n an direkten Nachfolgern aufweisen so spricht man von einem n-ären Baum.
In solchen Bäumen ist es zwäckmäßig sinnfoll spezielle äußere Knoten festzulegen, die weder nachfolger noch spezielle Informationen enthalten.
Solch spezielle Knoten lassen sich duch null bzw. NIL festlegen. Zu beachten ist dass jeder Binäre Baum ein Baum ist jedoch nicht jeder Baum ein Binärer Baum.

==Termminologie==
* Knoten    - Datenstrucktur zur Speicherrung eines Tupels
* Baum      - Menge von Knoten und Kanten
* Wald      - Menge von Bäumen
* Kante     - Verbindung zwischen zwei Knoten
* Pfad      - Folge verschiedener, durch Kanten verbundener, Knoten
* Wurzel    - Startknoten ohne Vorgänger
* Blatt     - Knoten ohne Nachfolger( auch äußere oder Nichtendknoten )
* innere Knoten - Knoten mit mindestens einem Nachfolger
* Vater     - Vorgänger eines Knotens
* Bruder    - Knoten mit dem Selben Vaterknoten
* Großvater - Vorgänger des Vaterknotens
* Onkel     - Bruder des Vaters

=Binäre Suchbäume=
Eine spezialisierung eines binären Baumes ist der binäre Suchbaum.
Der binäre Suchbaum besitzt die Eigenschaft, dass der Schlüssel des linken Kindknotens vom Knoten N jeweils kleiner oder gleich dem Schlüssel von N ist, wobei der Schlüssel des rechten Kindknotens größer ist als der von N. Daraus folgt, dass wenn Y ein Schlüssel im linken Teilbaum von N, und X ein Schlüssel im rechten Teilbaum von N ist, dann ist der Schlüssel von Y kleiner oder gleich dem Schlüssel von N und N ist kleiner X.
Ein binärer Suchbaum repräsentiert sich durch seine verkettete Datenstruktur, in welcher jeder Knoten ein Objekt darstellt. Jeder Knoten enthält dabei folgende Attribute:
* einen Zeiger auf den Elternknoten
* einen Zeiger auf den linken Kindknoten
* einen Zeiger auf den rechten Kindknoten
* einen Schlüssel
Besitzt der jeweilige Knoten keine Kinder oder kein Elternelement, zeigt das entsprechende Attribut auf null bzw. auf NIL, wobei NIL ein auch ein Knoten repräsentiert dessen Zweck, ebenso wie bei null, darin besteht, den binären Suchbaum terminieren zu lassen.

==Einfügen eines Elementes==

Beim Einfügen eines Elementes macht man sich die Eigenschaft zunutze, dass der Schlüssel des linken Sohns jeweils kleiner oder gleich dem Schlussel ist, den der Knoten selbst enthält. Der rechte Kindknoten dagegen enthält einen echt größeren Schlüssel.
Fügt man also einen Schlüssel in den Baum ein so beginnt man beim Vergleich mit der Wurzel. Ist der Einzufügende Schlüssel größer als der Schlüssel der Wurzel, so setzt man den Vergleich im rechten Teilbaum des aktuellen Knotens fort. Andernfalls also wenn der Schlüssel kleiner 
oder gleich dem Schlüssel der Wurzel ist, setzt man den Vergleich im linken Teilbaum des aktuellen Knotens fort.
Trifft man bei diesem Verfahren auf einen Knoten dessen Wertigkeit null entspricht, so wird an dieser Stelle der neue Schlüssel eingefügt.
Für den Programmablauf lässt sich also folgendes allgemein formulieren:
# Abfrage ob der einzufügende Schlüssel größer oder gleich dem Schlüssel von N ist
# Abfrage ob der sich daraus ergebende Kindknoten dem Wert null entspricht
# wenn ja, dann erzeuge neuen Knoten mit dem einzufügenden Schlüssel
# sonst beginne mit Schritt 1 wobei N nun N.links bzw n.rechts ist

Für die Methode zum Einfügen in einen BST ergibt sich zum einen eine rekursive sowie eine iterative Umsetzungsmöglichkeit, die im folgenden 
durch Pseudocode beschrieben werden.
:'''Rekursive Implementierung''':
 '''InsertRek( Schlüssel K, Knoten N )'''
 if Schlüssel < N.Schlüssel do
     if N.links is null do
         N.links = neuer Knoten
         N.links.Schlüssel = K
         N.links.Vater = N
     else do 
         InsertRek( K, N.links )
 else
     if N.rechts is null
         N.rechts = neuer Knoten
         N.rechts.Schlüssel = K
         N.rechts.Vater = N
     else do 
         InsertRek( K, N.rechts ) 

:'''Iterative Implementierung''':
 '''InsertIt( Schlüssel K )'''
 Knoten p = Wurzel
 Knoten o = null
 while p not null
     o = p
     if K < p.schlüssel or K is p.schlüssel
         p = p.links
     else if K > p.schlüssel
         p = p.rechts
     else return
 p = neuer Knoten
 p.Schlüssel = K
 p.Vater = o
 if Wurzel is null
     Wurzel = p
 else if K < o.schlüssel or K is o.schlüssel
     o.links = p
 else o.rechts = p

==Finden eines Elementes==

Beim suchen eines Elementes wird die spezielle Anordnung der Elemente in einem Baum genutzt. Ist der Baum leer, so ist der Schlüssel nicht enthalten. Ist das zu suchende Element größer als der Schlüssel der Wurzel bzw. des Knotens des aktuellen Teilbaumes so vergleicht man dessen rechten Kindknoten, ist er gleich so wurde das gesuchte Element gefunden ansonsten vergleicht man die Wurzel bzw. den linken Kindknoten des aktuellen Knotens. Beinhaltet der binäre Suchbaum ein oder mehrere Duplikate, so wird immer nur der Schlüssel gefunden, der den gerringsten
Weg zu Wurzel des Baumes besitzt, also der Schlüssel mit der geringsten Tiefe. Folgende Schritte sind also beim Einfügen durchzuführen:

* Abfrage ob der Baum leer ist
* Vergleich ob der gesuchte Schlüssel der Schlüssel des Wurzelelementes ist
* Wenn Schlüssel kleiner oder gleich ist, dann suche im linken Teilbaum weiter sonst rechts

:'''Rekursive Implementierung''':
 '''searchRek( Schlüssel k, Knoten n )'''
 if n is null
     return null
 if k is n.schlüssel
     return n 
 if k < n.schlüssel
     return searchRek( k, n.links )
 else return searchRek( k, n.rechts )	

:'''Iterative Implementierung''':
 '''searchIt( Schlüssel k, Knoten n )'''
 Knoten nI = n
 while nI not null and nI.schlüssel not k
     if k < nI.schlüssel
         nI = nI.links
     else nI = nI.rechts
 return nI

==Finden des Minimums==

Um den minimalen Schlüssel im Baum zu finden wandert man einfach von der Wurzel beginnend immer am linken Teilbaum entlang, bis der nächst folgende Knoten den Wert null enthält. Enthält der linke Teilbaum den Wert null, so terminiert der Algorithmus und gibt eine Adresse auf das gesuchte Minimum zurück.

:'''Iterative Implementierung''':
 '''Knoten getMinIt( Knoten wurzel )'''
 if wurzel is null
     return null
 while wurzel.links not null
     wurzel = wurzel.links
 return wurzel

:'''Rekursive Implementierung''':
 '''Knoten getMinRek( Knoten wurzel )'''
 if wurzel is null
     return null
 else if wurzel.links is null 
     return wurzel
 else return getMinRek( wurzel.links )

==Finden des Maximums==

Um den maximalen Schlüssel im Baum zu finden wandert man einfach von der Wurzel beginnend immer am rechten Teilbaum entlang, bis der nächst folgende Knoten den Wert null enthält.

:'''Iterative Implementierung''':
 '''Knoten getMaxIt( Knoten wurzel )'''
 if wurzel is null
     return null
 while wurzel.rechts not null
     wurzel = wurzel.rechts
 return wurzel

:'''Rekursive Implementierung''':
 '''Knoten getMaxRek( Knoten wurzel )'''
 if wurzel is null
     return null
 else if wurzel.rechts is null 
     return wurzel
 else return getMaxRek( wurzel.rechts )

==Finden des Nachfolgers==

Der Nachfolger eines Knotens ist der Knoten, dessen Schlüssel gemäß der Ordnugsrelation größer ist. Existieren Duplikate, so ist der Nachfolger
der Vaterknoten. Das Sohnelement muss in diesem Fall notwendigerweise ein linker Sohn sein. Der Nachfolger eines Knotens ist daher entweder das Minimum des rechten Teilbaumes oder, falls dieser nicht vorhanden, der Vaterknoten.

:'''Implementierung''':
 '''NachfolgerIt( Knoten n )'''
     if n is null
         return null
     if n.rechts not null
         return getMin( n.rechts )
     Knoten oben = n.vater
     while oben not null and oben.rechts is n
         n = oben
         oben = n.o
     return oben

==Traversierung eines binären Suchbaumes==
Die Eigenschaften eins binären Suchbaumes erlauben es uns den Baum komplett rekursiv zu durchlaufen. Hierbei unterscheidet man in drei versiedene Traversierungsmöglichkeiten. Zum einen ist dies die Inorder-Traversierung, wobei der Schlüssel des Teilbaumes zwischen den Werten seines linken und rechten Teilbaumes ausgegeben wird. In diesem Falle liegt die Ausgabe je nach implementierung auf- bzw. absteigend vor. Die zwei anderen Möglichkeiten den Baum zu traversieren, sind die Preorder- und die Postorder-Traversierung. Bei der Preorder-Traversierung wird der Schlüssel vor den Schlüsseln seines linken und rechten Teilbaums ausgeben und bei der Postorder-Traversierung hinter ihnen.
:'''Inorder-Traversierung''':
 '''inorderTreewalk( Node n )'''
 if n not null
     inorderTreewalk( n.left )
     print( n.key )
     inorderTreewalk( n.right )

:'''Preorder-Traversierung''':
 '''preorderTreewalk( Node n )'''
 if n not null
     print( n.key )
     preorderTreewalk( n.left )
     preorderTreewalk( n.right )

:'''Postorder-Traversierung''':
 '''postorderTreewalk( Node n )'''
 if n not null
     postorderTreewalk( n.left )
     postorderTreewalk( n.right )
     print( n.key )

:'''Rekursive Implementierung''':
 '''AusgabeVorwRek( Knoten n )'''
 if n is null do
     return ""
 else return n.toString + lineBreak + AusgabeVorwRek( nachfolger( n ) )
		
:'''Iterative Implementierung''':
 '''AusgabeVorwIt( Knoten n )'''
 String retStr = ""
 while n not null do
     retString + n.toString + lineBreak
     n = nachfolger( n )

==Löschen eines Elementes==

Das löschen eines Knotens in einem BST stellt sich als komplexer heraus. So muss eine grundsätzliche Entscheidung vorgenommen werden, ob der zu löschende Knoten höchstens ein oder zwei Kinder hat.

===Mit einem Sohn===
Wenn der zu löschende Knoten keine Kinder hat kann er bedenkenlos gelöscht werden, hat er allerdings genau ein Kind, so wird der verbleibende
Teilbaum einfach eine Etage nach oben geschoben. Man setzt also den Vorgängerknoten des Kindknotens auf den Entsprechenden linken oder rechten
Kindknoten des Vorgängerknotens des zu löschenden Elementes sowie den entsprechend linken oder rechten Kindknoten dieses Elementes auf das 
Kindelement des zu löschenden Knotens. Ist der zu löschende Knoten die Wurzel, so setzen wir den Wurzelzeiger einfach auf den entsprechend folgenden Knoten.
:'''Implementierung''':

 '''deleteNodeWithOneChild( Node n )'''
 // get the child
 Node child;         
 if n.left is null
     child = n.right
 else child = n.left
 
 // handling if the root should be deleted		
 if n is root
     child.parent = null
     root = child
     return
 				
 // handling if the node has a parent node
 if n.parent.left is n
     n.paretn.left = child
 else n.parent.right = child
 
 if child not null
     child.parent = n.parent
 
 n = null

<language>Java</language>
<language>Java</language>
===Mit zwei Söhnen===

Beinhaltet der zu löschende Knoten zwei nichtleere Kindknoten, so wird zunächst der kleinste Knoten des rechten Teilbaums ermittelt. Dieser ist
da er im rechten Teilbaum ist in jedem Falle der Nachfolger von dem zu löschenden Knoten und beinhaltet keinen linken Kindknoten mehr.
Somit wird einfach der Inhalt dieses Knotens in den zu löschenden Knoten kopiert und anschließend das ermittelte minimum gelöscht. Man vereinfacht mit dieser Methode also den Fall, dass zwei Söhne existieren, zu dem Fall, dass nur ein Sohn existiert womit die löschfunktion
für einen Kindknoten angewand werden kann.
Beinhaltet der BST allerdings Duplikate, so würde die oben beschiebene Vorgehensweise zu Komplikationen führen. Würde man also nur das Minimum, welches ein Duplikat im Baum aufweist( dieses Duplikat wäre dann zwangsweise das Elternelement des Minimums ), an den Platz des zu löschenden Knotens kopieren, so würden hierbei Duplikate im rechten Teilbaum des zu gelöschten Elementes übrig bleiben. Diese Fehlplatzierung würde demnach die Invariante binärer Suchbäume verletzen.
Um dieses Problem zu beseitigen wird an die Position des zu löschenden Knotens die Liste aller Duplikate des Minimums aus dem  rechten Teilbaum eingefügt. Somit wird der Elternknoten-Zeiger der Entsprechenden Kindknoten des zu löschenden Elementes auf das Minimum im linken Teilbaum gesetzt und dessen Kindzeiger auf die Kinder des zu löschenden Knotens. Im folgenden wird dann der Kindzeiger des zu löschenden Knotens auf das Kindelement des Duplikates mit der geringsten Tiefe gesetzt und dessen Elternpointer auf das zu löschende Element. Anschließend wird der Inhalt des im rechten Teilbaum übriggebliebenen Duplikates in das zu löschende Element kopiert. Da das im rechten Teilbaum übriggebliebende Element nun im schlimmsten Fall noch einen rechten Sohn beinhaltet, kann dieses Element nun mit der oben beschriebenen Methode zum Löschen eines Elementes entfernt werden.

:'''Implementierung''':

 '''deleteNodeWithTwoChildren( Node n )'''
 Node min = getMin( n.right )
 min.left = n.left
 
 if min.left not null
     min.left.paretn = min
 // walking up if there are duplicates
 while min.key is min.parent.key
     min = min.parent
 n.left = min.left
 if n.left is null
     n.left.parent = n;
 min.left = null
 n.key = min.key
 deleteNodeWithOneChild( min )

<language>Java</language>
<language>Java</language>
<language>Java</language>
===Programmierbeispiel===
<popup>
<code id="4f9addc2b065e">
/**
 * Tupel data structure which should be safed in BST
 */

public Object Address(String p_Name, String p_Surname, String p_Street, String p_PostalCode, String p_Place){

    String m_Name = p_Name;
    String m_Surname = p_Surname;
    String m_PostalCode = p_Street;
    String m_Place = p_PostalCode;
    String m_Street = p_Place;

    public int compareTo( p_Address ){
	return m_Name.compareTo( p_Address.m_Name );
    }
	
    public String toString(){
	return m_Name + " " + m_Surname + ", " + m_Street + ", " + m_PostalCode + " " + m_Place;
    }

    return this;
}
</code>
<code id="4f9b0a0a7aacf">
/**
 * The Key to get Objects form BST
 */
public Object Key(String p_Name){

    String m_Name = p_Name;
    
    public int compareTo( p_Address ){
	return m_Name.compareTo( p_Address.m_Name );
    }
	
    public String toString(){
	return m_Name;
    }

    public int compareTo( p_Address ){
	return m_Name.compareTo( p_Address.m_Name );
    }

    return this;
}
</code>
<code id="4f9adfa5df346">
/**
	 * encapsulated class for information hiding
	 * */
	public Object Node( Object p_Element, Object p_Parent ){
		
		Object   m_LeftChild = null;
                Object   m_RightChild = null;
                Object   m_Parent = p_Parent;
		Object	 m_Element = p_Element;		
		
		
		/**
		 * 
		 * */
		public String toString(){
			return m_Element.toString();
		}
		
		return this;
	} 
</code>
<code id="4f9ae142e8ac6">
/**
 * Binary Search Tree class
 * */
public Object BinarySearchTree(){
	

	
	Object m_Root;
	
	/**
	 * 
	 * */
	public void insert( Object p_Element ){
		if( m_Root == null )
			m_Root =   Node( p_Element, null );
		else insertRek( p_Element, m_Root );
	}
	
	/**
	 * 
	 * 
	public void insert( Object[] p_Elements ){
		for( Object i : p_Elements )
			insert( i );
	}*/
	
	/**
	 * 
	 * */
	private void insertRek( Object p_Element, Object p_Node ){
		if( p_Element.compareTo( p_Node.m_Element ) == 0 ){
			Object l_Duplicate =   Node( p_Element, p_Node );
			l_Duplicate.m_LeftChild = p_Node.m_LeftChild;
			if( p_Node.m_LeftChild != null )
				p_Node.m_LeftChild.m_Parent = l_Duplicate;
			p_Node.m_LeftChild = l_Duplicate;
			return;
		}
		if( p_Element.compareTo( p_Node.m_Element ) < 0 )
			if( p_Node.m_LeftChild == null )
				p_Node.m_LeftChild =   Node( p_Element, p_Node );
			else insertRek( p_Element, p_Node.m_LeftChild );
		else
			if( p_Node.m_RightChild == null )
				p_Node.m_RightChild =   Node( p_Element, p_Node );
			else insertRek( p_Element, p_Node.m_RightChild );
	}
	
	/**
	 * 
	 * */
	public Object search( Object p_Element ){
		return searchRek( p_Element, m_Root );
	}
	
	/**
	 * 
	 * */
	private Object searchRek( Object p_Element, Object p_Node ){
		if( p_Node == null )
			return null;
		if( p_Element.compareTo( p_Node.m_Element ) == 0 )
			return p_Node;
		if( p_Element.compareTo( p_Node.m_Element ) < 0 )
			return searchRek( p_Element, p_Node.m_LeftChild );
		else
			return searchRek( p_Element, p_Node.m_RightChild );		
	}
	
	/**
	 * 
	 * @param p_Node
	 */
	public void delete( Object p_Node ){
		if( p_Node == null )
			return;
		if( p_Node.m_LeftChild == null || p_Node.m_RightChild == null )
			deleteNodeWithOneChild( p_Node );
		else deleteNodeWithTwoChildren( p_Node );
	}
	
	/**
	 * 
	 * @param p_Node
	 */
	private void deleteNodeWithOneChild( Object p_Node ){
		// get the child
		Object l_Child = (p_Node.m_LeftChild == null ) ? p_Node.m_RightChild : p_Node.m_LeftChild;
		
		// handling if the root should be deleted
		if( p_Node == m_Root ){
			l_Child.m_Parent = null;
			m_Root = l_Child;
			return;
		}
		
		// handling if the Object has an parent Object
		if( p_Node.m_Parent.m_LeftChild == p_Node )
			p_Node.m_Parent.m_LeftChild = l_Child;
		else p_Node.m_Parent.m_RightChild = l_Child;
		
		if( l_Child != null )
			l_Child.m_Parent = p_Node.m_Parent;
		
		p_Node = null;		
		
	}
	
	/**
	 * 
	 * @param p_Node
	 */
	private void deleteNodeWithTwoChildren( Object p_Node ){
		Object l_Min = getMin( p_Node.m_RightChild );
		
		l_Min.m_LeftChild = p_Node.m_LeftChild;
		if( l_Min.m_LeftChild != null )
			l_Min.m_LeftChild.m_Parent = l_Min;
		
		while( l_Min.m_Element.compareTo( l_Min.m_Parent.m_Element  ) == 0 )
			l_Min = l_Min.m_Parent;
		
		p_Node.m_LeftChild = l_Min.m_LeftChild;
		if( p_Node.m_LeftChild != null )
			p_Node.m_LeftChild.m_Parent = p_Node;
		l_Min.m_LeftChild = null;
		
		p_Node.m_Element = l_Min.m_Element;
		
		deleteNodeWithOneChild( l_Min );		
	}
	
	/**
	 * 
	 * @param p_RootNode
	 * @return
	 */
	public Object getMin( Object p_RootNode ){
		if( p_RootNode == null )
			return null;
		if( p_RootNode.m_LeftChild == null )
			return p_RootNode;
		else return getMin( p_RootNode.m_LeftChild );
	}
	
	/**
	 * 
	 * @return
	 */
	public Object getMin( ){
		return getMin( m_Root );
	}
	
	/**
	 * 
	 * @param p_RootNode
	 * @return
	 */
	public Object getMax( Object p_RootNode ){
		if( p_RootNode == null )
			return null;
		if( p_RootNode.m_RightChild == null )
			return p_RootNode;
		else return getMax( p_RootNode.m_RightChild );
	}
	
	/**
	 * 
	 * @return
	 */
	public Object getMax(){
		return getMax( m_Root );
	}
	
	public Object getSuccessor( Object p_Node ){
		if( p_Node == null )
			return null;
		if( p_Node.m_RightChild != null )
			return getMin( p_Node.m_RightChild );
		Object l_Successor = p_Node.m_Parent;
		while( l_Successor != null && l_Successor.m_RightChild == p_Node ){
			p_Node = l_Successor;
			l_Successor = p_Node.m_Parent;
		}
		return l_Successor;
	}
	
	public Object getPredecessor( Object p_Node ){
		if( p_Node == null )
			return null;
		if( p_Node.m_LeftChild != null )
			return getMax( p_Node.m_LeftChild );
		Object l_Predeccessor = p_Node.m_Parent;
		while( l_Predeccessor != null && l_Predeccessor.m_LeftChild == p_Node ){
			p_Node = l_Predeccessor;
			l_Predeccessor = p_Node.m_Parent;
		}
		return l_Predeccessor;
	}
	
	/**
	 * 
	 * @return
	 */
	public String printAscending(){
		return printAscending( getMin() );
	}
	
	/**
	 * 
	 * @return
	 */
	public String printDescending(){
		return printDescending( getMax() );
	}
	
	/**
	 * 
	 * @param p_Node
	 * @return
	 */
	public String printAscending( Object p_Node ){
		if( p_Node == null )
			return "";
		else return p_Node.toString() + '\n' + printAscending( getSuccessor(p_Node) );
	}
	
	/**
	 * 
	 * @param p_Node
	 * @return
	 */
	public String printDescending(  Object p_Node  ){
		if( p_Node == null )
			return "";
		else return p_Node.toString() + '\n' + printDescending( getPredecessor(p_Node) );
	}
	
	/**
	 * 
	 * */
	public void inorderTreewalk( Object p_Node ){
		if( p_Node != null ){
			inorderTreewalk( p_Node.m_LeftChild );
			System.out.println( p_Node.m_Element.toString() );
			inorderTreewalk(p_Node.m_RightChild);
		}	
	}
	
	public void preorderTreewalk( Object p_Node ){
		if( p_Node != null ){
			System.out.println( p_Node.m_Element.toString() );
			preorderTreewalk(p_Node.m_LeftChild);
			preorderTreewalk(p_Node.m_RightChild);
		}
	}
	
	public void postorderTreewalk( Object p_Node ){
		if( p_Node != null ){
			preorderTreewalk(p_Node.m_LeftChild);
			preorderTreewalk(p_Node.m_RightChild);
			System.out.println( p_Node.m_Element.toString() );
		}
	}
	
	public void inorderTraversation(){
		inorderTreewalk( m_Root );
	}
	
	public void preorderTraversation(){
		preorderTreewalk( m_Root );
	}
	
	public void postorderTraversation(){
		postorderTreewalk( m_Root );
	}
	
	return this;
	
}

</code>

</popup>
<run id="4f9b0a0a7ab72">
Bst = BinarySearchTree();
System.out.println( "Daten werden eingelesen ..." );
Bst.insert( Address( "Max"   , "Mustermann" , "Musterstaße 1a", "02828", "Görlitz"     ) );
Bst.insert( Address( "Antje" , "Musterfrau" , "Dorfstraße 22a", "02829", "Markersdorf" ) );
Bst.insert( Address( "Tom"   , "Tomsen"     , "Tomstraße 44b" , "02826", "Görlitz"     ) );
Bst.insert( Address( "Romano", "Romansen"   , "Romstaße 76c"  , "02823", "Rohausn"     ) );
Bst.insert( Address( "Jens"  , "Jensen"     , "Jenstraße 1b"  , "02826", "Görlitz"     ) );
Bst.insert( Address( "Jenny" , "Jensen"     , "Jennystraße 1a", "02828", "Görlitz"     ) );
Bst.insert( Address( "Ronny" , "Ronnsen"    , "Rostraße 9h"   , "02827", "Gölitz"      ) );
Bst.insert( Address( "Lisa"  , "Lisansen"   , "Listraße 4"    , "02829", "Königshain"  ) );
Bst.insert( Address( "Susi"  , "Susinsen"   , "Susnstraße 5"  , "02835", "Sushausn"    ) );
Bst.insert( Address( "Lars"  , "Larson"     , "Lalastraße 7f" , "02826", "Gersdorf"    ) );
Bst.insert( Address( "Markus", "Markson"    , "Markstaße 6h"  , "02825", "Königshain"  ) );
Bst.insert( Address( "Johan" , "Johnson"    , "Johanstraße 3" , "02829", "Markersdorf" ) );
Bst.insert( Address( "Ash"   , "Ketschom"   , "Pokestraße 4"  , "03346", "Alabastia"   ) );
System.out.println( "Daten wurden eingelesen! " );
System.out.println(  );
System.out.println( "Inorder-Traversierung" );
System.out.println(  );
Bst.inorderTraversation(  );
System.out.println(  );
System.out.println( "Preorder-Traversierung" );
System.out.println(  );
Bst.preorderTraversation(  );
System.out.println(  );
System.out.println( "Postorder-Traversierung" );
System.out.println(  );
Bst.postorderTraversation(  );
System.out.println(  );
System.out.println( "Suchen eines Elementes..." );
System.out.println( Bst.search( Key( "Jens" ).toString(  ) ));
System.out.println(  );
System.out.println(  );
System.out.println(  );
System.out.println( "Lösche einen Knoten." );

</run>

=2-3-4-Bäume=

==Eigenschaften==
# Knoten enthalten bis zu 3 Schlüssel
# 3-Knoten mit 3 ausgehenden Verkettungen sind zugelassen
# 4-Knoten mit 4 ausgehenden Verkettungen sind zugelassen
# Binärbaum Eigenschaften vorhanden (2-Knoten)

==Suchen eines Elements==
Beim Suchen in 2-3-4-Bäumen wird die Top-Down-Methode verwendet. Dabei wird ausgehend von dem kleinsten Element des Wurzelknotens, den entsprechenden Verkettungen bis zum gesuchten Schlüssel gefolgt.
Im ersten Schritt wird dabei der gesuchte Schlüssel mit dem aktiven Element verglichen. Liefert der Vergleich eine wahre Aussage ist schon an dieser Stelle die Suche beendet. Ist dies nicht der Fall wird geprüft, ob der gesuchte Schlüssel kleiner ist als das aktive Element im aktuellen Knoten. Ist dieses Kriterium wahr geht man die Verkettung vor dem aktiven Element weiter entlang und setzt das kleinste Element des Kindknotens als neues aktives Element und beginnt wieder im ersten Schritt. 
Im Fall, dass das Kriterium nicht erfüllt ist wird im Wurzelknoten das nächstgrößere Element aktiviert und beginnt mit diesem wieder bei Schritt eins. Sollte kein nächstes Element im aktuellen Knoten vorhanden sein wird der Verkettung nach dem zuletzt aktiven Elements zum kleinsten Element des Kindknotens gefolgt und der Erste Schritt wieder ausgeführt.

==Einfügen eines Elements==

===Günstiger Fall===

Beim Einfügen wird ein Knoten solange aufgefüllt, bis er 3 Elemente enthält. Soll noch ein viertes Element aufgenommen werden ist dies nur durch ein Spalten des Knotens möglich. Dabei wird der überfüllte Knoten in 3 Teile gesplittet: 
* Knoten mit zwei Elementen
* Knoten mit einem Element
* Mittleres Element
Das mittlere Element rutscht bei der Spaltung in den Elternknoten und stellt somit die Verkettung der zwei neuen Knoten dar.


===Ungünstiger Fall===

Muss der überfüllte Knoten wie im Günstigen Falle gespalten werden und der Elternknoten ist schon mit 3 Elementen belegt, wird das Spalten in Richtung Wurzel solange nach oben gereicht bis man entweder auf kein 4-Knoten mehr trifft oder auf die Wurzel stößt. Bei der Wurzel wird jedoch nach gleicher Aufteilungsregel eine neue Wurzel erzeugt, wenn diese ebenfalls schon voll besetzt ist.

Laufzeit: $O$(log n)

===Split-Operation===

Eine alternative Möglichkeit um dem ungünstigen Fall sofort vorzubeugen ist die Split-Operation. Dabei wird anders als bei den oben beschriebenen Methoden, während ein Element in den Baum eingefügt wird beim Durchlauf zusätzlich nach 4-Knoten gesucht, die daraufhin ausgepalten werden. Somit wird die Split-Operation im schlimmsten Fall einmal durchgeführt.

==Löschen eines Elements==
Das Löschen eines Elements aus einem Knoten lässt sich immer auf das Löschen eines Elements in einem Blatt zurückführen. Dafür ist es zunächst nötig die Position des zu löschenden Elements zu wissen. Neben dieser Position i wird außerdem das Element benötigt, welches sich an der äußersten rechten Stelle befindet um beide Elemente zu tauschen. Nun kann das Element aus dem Blatt gelöscht werden, wobei drei Fälle zu unterscheiden sind:
* mehr als ein Element im Blatt - einfaches Entfernen
* ein Element im Blatt und Nachbarknoten (gleicher Vorgänger) mindestens zwei Elemente - leihen eines Elements aus dem Nachbarknoten - Schlüssel in Vorgängerknoten verschieben - Vorgängerelement des zu löschenden Elements rückt an dessen Position und ersetz dieses
* nur ein Element im Blatt und Nachbarknoten - Element entfernen - Vorgängerelement mit Nachbarelement zusammengefügt
* vorhergehender Fall und Vorgängerknoten nur ein Element - gleiche Operation auf höherer Ebene

=A-V-L-Bäume=

==Eigenschaften==
# balancierte Knoten
# Höhenunterschied = 1
# Rotation um mittleres Element

==Balancekriterium==
Höhenunterschied = HöheRechts - HöheLinks

[[Bild:RoJe_Unbenannt-4.jpg]]

==Suchen==

==Einfügen==

==Löschen==

==Einfachrotation==

==Doppelrotation==

=B-Bäume=

===Eigenschaften===
# alle Höhen von Wurzel zu Blatt immer gleich
# jeder Knoten besteht aus min. k und max. 2k Elemente
# unterschiedliche Anzahl von Elementen in Knoten möglich
# Wurzel besteht aus zwischen 1 und 2k Elementen 
# Knoten mit n Elementen besitzt n+1 Verkettungen
# Blätter haben keine bzw. undefinierte Verkettungen

===Suchen eines Elements===

Der Suchalgorithmus arbeitet nach dem gleichen Schema, wie es bei den 2-3-4-Bäumen der Fall ist.

===Einfügen eines Elements===

Zunächst wird die korrekte Position zum Einfügen des Schlüssels ermittelt. Besitzt der sich an dieser Position befindende Knoten weniger als 2k Elemente erfolgt ein einfaches Einfügen des Schlüssels in den aktuellen Knoten. 
Befinden sich schon 2k Elemente vor dem Einfügen in dem Knoten, ist dieser Überfüllt und es wird auf die Splitting-Methode, wie bei den 2-3-4-Bäumen zurückgegriffen.

====Einfügealgortithmus====

<code id="4f9ab5786a914">Insert ( KEY )
find leaf or node L;
  if ( L overflows ){
    split L, push up the middle key
    to parent node P;´
  }
  if (P overflows){
    repeat the split recursively;
  }
    else{
       add the KEY K in node L;
    }</code>

===Löschen eines Elements===

Beim Löschvorgang in B-Bäumen muss unterschieden werden, ob sich das zu löschende Element in einem Blatt oder Knoten befindet. In einem Knoten wird der Schlüssel gelöscht und gegen das kleinste Element aus dem rechten Unterbaum ersetzt.
Wird dabei ein Element, was zum Ersetzen benötigt wurde, aus einem Blatt oder Knoten so entfernt, dass es die Baumeigenschaften verletzt(mindestens k Einträge). Hier werden nun die Nachbarblätter zur Hilfe genommen. 
Dabei gibt es zwei Möglichkeiten:

# Blatt Schlüssel und Nachbar Schlüssel sind zusammen größer als 2k - Durchführen einer "Redistribution" (gleichmäßige Aufteilung der Einträge auf die beiden Blätter)

# Blätter / Knoten zusammen weniger als 2k Einträge - Durchführung einer "Concatention" (Verschmelzung von benachbarten Blättern - Gegenstück zum Splitting beim Einfügen)

===Wahl von k===

Die Wahl der Anzahl der möglichen Einträge eines Knotens hängt von der verwendeten Hardware ab. Das beinhaltet den Zugriff auf den Hintergrundspeicher und die Größe des Arbeitsspeichers. 
Dabei ist das Ziel auf geringe Zugriffszeiten auf den langsamen Hintergrundspeicher gerichtet.
Ein weiterer wichtiger Punkt ist, dass je mehr Einträge in einem Knoten aufgenommen werden können, desto flacher wird der Baum. Im Bezug auf den Hintergrundspeicher bedeutet das, weniger Zugriffe.
Der Nachteil dabei ist, dass mit steigendem k die Zugriffe länger dauern. Des weiteren muss beachtet werden, das der Arbeitsspeicher die Knotengröße begrenzt. Wie man erkennen kann steht die Wahl von k mit verschiedenen Faktoren in Verbindung. Daher muss k individuell für jedes System ermittelt werden. 

==B*-Bäume==

===Eigenschaften===
# alle Höhen von Wurzel zu Blatt immer gleich
#''' jeder Knoten hat max. 2k Elemente und ist zu 2/3 aufgefüllt'''
# unterschiedliche Anzahl von Elementen in Knoten möglich
# Wurzel besteht aus zwischen 1 und 2k Elementen 
# Knoten mit n Elementen besitzt n+1 Verkettungen
# Blätter haben keine bzw. undefinierte Verkettungen

===Vergleich B-Bäume und B*-Bäume===

====Vorteile:====

Sind Knoten minimaler besetzt, haben die Knoten von B*-Baum mehr Söhne als die von B-Bäumen. 
Sind alle Knoten minimal besetzt(worst-case), ist die Höhe der B*-Bäume geringer als die von normalen B-Bäumen.
Hinzukommt, dass B*-Bäume eine bessere Speicherauslastung garantieren.

====Nachteile:====

Bei sehr stark befüllten Knoten (z.B. mindestens 2k-1 Einträge in einem B-Baum), kommt es mit einer sehr hohen Wahrscheinlichkeit zu einem Nachteil in Einfüge-Operationen, da man vermehrt auf volle Knoten treffen würde. Dies würde bei jedem vollen Knoten ein Splitting mit sich bringen, welches sich oft rekursiv bis zur Wurzel fortsetzen würde.
Daher laufen bei B*-Bäume die Operationen weniger lokal ab als bei B-Bäumen.
Hinzukommen außerdem die generell aufwendigeren Operationen.

==B+-Bäume==

===Punktsuche und Bereichssuche===

===Eigenschaften===

===next()-Operation===

===Parallele Operationen===

===(un)sichere Knoten===

=Rot-Schwarz-Bäume=
==Komponenten der Knoten==
* Farbe
* Schlüssel
* Adresse des Eleternknotens
* Adresse des linken Kindknotens
* Adresse des rechten Kindknotens

==Eigenschaften==
# Jeder Konten ist entweder rot oder schwarz
# Die Wurzel ist schwarz
# Jedes Blatt( null/ nil ) ist schwarz
# Die Kind-Knoten eines Roten Knotens sind jeweils schwarz
# Alle Pfade die von einem bestimmten Knoten ausgehen und in einem Blatt dieses Teilbaums enden, haben die gleiche Anzahl an schwarzen   Knoten


==Rotationen==

Durch die Einfüge- und Löschoperationen kann es dazu kommen, das eine oder mehrere Eigenschaften des Rot-Schwarzbaumes verletzt werden.
Um die Zeigerstruktur des Baumes zu "reparieren" bedient man sich der Rotation.

===Linksrotation===
===Rechtsrotation===

==Einfügen==

:'''Fall 1''':
Der erste Fall beschreibt den Sachverhalt, dass der neu eingefügte Knoten die Wurzel des Baumes darstellt. Dies würde berreits die Eigenschaft, dass die Wurzel des Baumes schwarz sein muss verletzen. Aus diesem Grund wird die noch rote Wurzel schwarz gefärbt wodurch das Gleichgewicht wieder hergestellt ist.

 '''insertCase1( Knoten n )'''
     if n.parent is null
         n.color = BLACK
     else insertCase2( n )

:'''Fall 2''':
Ist der Vater des neuen Knotens schwarz, so tritt der zweite Fall ein. In diesem Fall könnte der Gedanke aufkommen, dass die fünfte Eigenschaft, also dass der Baum auf allen Pfaden von der wurzel zu den Blättern die gleiche Schwaarztiefe besitzt. Da allerdings ein schwazknoten( Nil ) beim einfügen gelöscht wird bleibt die Schwarztiefe im Baum erhalten und es ist nichts weiter zu tun.
 
 '''insertCase2( Knoten n )'''
 if n.parent.color is BLACK
     return
 else insertCase3( n )

:'''Fall 3''':
Ab dem Fall drei beginnent, kann davon ausgegangen werden, dass der einzufügende Knoten einen Großvater besitzt, da der Vater rot sein muss ( sonst wäre bereits Fall eins oder Fall zwei eingetreten ) und damit nicht die Wurzel sein kann. Somit beschreibt der dritte Fall die Situation, dass sowohl der Onkel als auch der Vater rot sind. Da durch das Anhängen eines weiteren roten Knotens nun die Eigenschaft verletzt wird, dass ein roter Knoten immer zwei schwarze Kindknoten haben muss, werden der Onkel sowie der Vaterknoten schwarz und der Großvater rot gefärbt. Mit diesem Verfahren sowie der Hilfe der Verfahren von Fall eins und Fall zwei verschiebt man das Problem also soweit nach oben bis es sich auflöst, andernfalls betrachtet man einen neuen Fall.

 '''insertCase3( Knoten n )'''
 if uncle( n ) not null and uncle( n ).color is RED
     n.parent = BLACK
     uncle( n ).color = BLACK
     grandparent( n ).color = RED
     insertCase1( n )
 else insertCase4( n )

:'''Fall 4''':
Der nächste Fall betrachtet die Situation, dass der Onkel des neuen Knotens schwarz ist( kann also auch Nil sein ) und der neue Knoten das 
rechte Kind seines roten Vaters ist, welcher jedoch links an seinem Größvater sitzt. Analog dazu kann der neu einzufügende Knoten auch das linke Kind seines roten Vaters sein, welcher rechts an seinem Großvater angebracht ist. Im ersten der beiden Fälle wird eine Linksrotation
und im zweiten eine Rechtsrotation um den Vater durchgeführt. Anschließend wird in jedem Falle der fünfte und damit letzte Fall überprüft.

 '''insertCase4( Knoten n )'''
 if n is n.parent.right and n.parent is gradnparent( n ).left
     rotateLeft( n.parent )
     n = n.left
 else 
     if n is n.parent.left and n.parent is gradnparent( n ).right
         rotateRight( n.parent )
         n = n.right
 insertCase5( n )

:'''Fall 5''':
Der letzte Fall beinhaltet die Situationen, dass der neue Knoten einen schwarzen Onkel hat( auch Nil ist schwarz ) und der linke Knoten seines Vaters ist, der sich ebenfalls links am Großvater befindet bzw. dass der neue Knoten rechts an seinem Vater hängt, der sich ebenfalls am Großvater befindet. Da in diesem Fall die Eigenschaft verletzt ist, dass der Vater des neuen knoten keine zwei schwarzen Kinder aufweisen kann, bedient man sich einer Rechtsrotation, sofern der neue Knoten links an seinem Vater ist und sich dieser links am Großvater befindet. Im entgegengesetztem Fall bedient man sich der Linksrotation um den Großvater. Anschließend wird der ehemalige Vater schwarz und der ehemalige Großvater rot gefärbt.

 '''insertCase5( Knoten n )'''
 n.parent.color = BLACK
 grandparent( n ).color = RED
 if n is n.parent.left and n.patent is grandparent( n ).left
     rotateRight( grandparent( n ) )
 else rotateLeft( grandparent ( n ) )

==Löschen==
:'''Fall 1''':
Der erste Fall beschreibt die Situation, dass der Konfliktknoten( n ) die Wurzel des Baumes darstellt. Da die Wurzel immer schwarz sein muss ist an dieser Stelle nichts weiter zu tun, da der schwarze Knoten( also die Wurzel ) von jedem Pfad entfernt wurde. Da die neue Wurzel ebenfalls schwarz ist bleiben alle Eigenschaften des Rot-Schwarz-Baumes erhalten.

 '''deleteCase1( Node n )'''
 if n.parent is null
     return
 else deleteCase2( n )

:'''Fall 2''':
Im zweiten Fall wird auf die Situation eingegangen, dass der Bruder des Konfliktknotens rot ist. Tritt dieser Fall ein, so wird die Farbe vom Vater sowie vom Bruder des Konfliktknotens invertiert. Im Anschluss daran wird eine Rotation um den Vater durchgeführt, wodurch der Bruder zum Großvater des Konfliktknotens wird.

 '''deleteCase2( Node n )'''
 if sibling( n ).color is RED
     n.parent.color = RED
     sibling( n).color = BLACK
     if n is n.parent.left
         rotateLeft( n.parent )
     else rotateRight( n.parent )
 deleteCase3( n )

:'''Fall 3''':
Sind der Vater, der Bruder und die Kinder des Konfliktknotens schwarz, so tritt der dritte Fall ein. In diesem Fall wird der Bruder rot gefärbt. Im weiteren haben jedoch noch immer alle Pfade, die durch den Vater laufen einen schwarzen Knoten weniger, woduch die Eigenschaft der gleichmäßigen Schwarztiefe verletzt wird. Um dies zu "reparieren" und die Ordnung wieder herzustellen versucht man einen der sechs Fälle anzuwenden.
 
 '''deleteCase3( Node n )'''
 if n.parent.color is BLACK and
    sibling( n ).color is BLACK and
    sibling( n ).left.color is BLACK and
    sibling( n ).right.color is BLACK 
    do
        sibling( n ).color = RED
        deleteCase1( n.parent )
 else do
     delelteCase4( n )

:'''Fall 4''':
Der vierte Fall beinhaltet den Sachverhalt, dass der Bruder sowie die Kinder schwarz sind, der Vater jedoch eine rote Farbe beinhaltet. Um in diesem Fall die Ordnung wieder herzustellen ist es ausreichend dem Vater die Farbe des Bruders( schwarz ) und dem Bruder die Farbe des Vaters( rot ) zuzuweisen. Durch dieses Verfahren bleibt die Anzahl der schwarzen Knoten die nicht durch den Konfliktknoten führen gleich. Da aber auf allden Pfaden, die duch den Konfliktknoten führen ein schwarzer Knoten eingefügt wird wird das Gleichgewicht wieder hergestellt.

 '''deleteCase4( Node n )'''
 if n.parent.color is RED and
    sibling( n ).color is BLACK and
    sibling( n ).left.color is BLACK and
    sibling( n ).right.color is BLACK
    do
        sibling( n ).color = RED
        n.color = BLACK
 else deleteCase5( n )

:'''Fall 5''':
Der fünfte Fall trifft auf zwei Sachverhalte zu, die sich lediglich durch ihre Ausrichtung unterscheiden. Zum einen ist dies, dass das linke Kind des Bruders rot und das rechte Kind sowie der Bruder des Konfliktknotens schwarz sind. Der Konfliktknoten ist hierbei das linke Kind seines Vaters. Der zweite Fall stellt also somit die Situation dar, dass das rechte Kind des Bruders rot und das linke Kind sowie der Bruder schwarz sind. In diesem Fall ist der Konfliktknoten das rechte Kind seines Vaters.
Um in diesem Fall die Ordnung zu wahren wird bei der ersten Möglichkeit des fünften Falles eine Rechts- und bei der zweiten dem entsprechend eine Linksrotation um den Bruder durchgeführt. Das linke bzw. das rechte Kind des Bruders wird dabei dessen neuer Vater und dieser wird Bruder des Konfliktknotens. Zudem werden die Farben des Bruders und des neuen Vaters getauscht. Zwar haben alle Pfade noch die gleiche Anzahl an schwarzen Knoten wie vorher jedoch hat der Konfliktknoten nun einen schwarzen Bruder der rechts bzw. links ein rotes Kind hat. Damit ist die Voraussetzung für den sechsten Fall gegeben ohne dass der Konfliktknoten noch der Vater beeinflusst wurden.

 '''deleteCase6( Node n )'''
 if n is n.parent.left and
    sibling( n ).color is BLACK and 
    sibling( n ).left.color is RED and
    sibling( n ).right.color is BLACK
    do 
        sibling( n ).color = RED
        sibling( n ).left.color = BLACK
        rotateRight( sibling( n ) )
    else
        if n is parent.right and
           sibling( n ).color is BLACK and
           sibling( n ).left.color is BLACK and
           sibling( n ).right.color is RED
           do
               sibling( n ).color = RED
               rotateLeft( sibling( n ) )
 deleteCase6( n )

:'''Fall 6''':
Der letzte Fall fordert, dass der Bruder des Konfliktknotens schwarz, das Rechte Kind des Bruders rot ist. Zudem soll der Konfliktknoten das linke Kind seines Vaters sein. Aquivalent dazu ist auch die Möglichkeit, dass das linke Kind des Bruders rot ist und der Konfliktknoten das rechte Kind seines Vaters ist. Hierbei würden dann jeweils eine Links- bzw. eine Rechtsrotation um den Vater des Konfliktknotens stattfinden, wodurch der Bruder zum Großvater des Konfliktknotens wird und der Bruder wird Vater des ehemaligen rechten bzw. linken Kindes des Konfliktknotens. Im weiteren wird die Farbe des Bruders mit der Farbe des Vaters( jeweils vom Konfliktknoten ) getauscht. Das rechte bzw. das linke Kind wird schwarzgefärbt. Zu beachten ist, dass der noch immer die selbe Farbe in der Wurzel hat, wodurch die vierte Eigenschaft, dass wenn ein Knoten rot ist beide Kinder schwarz sein müssen, erhalten bleibt. Allerdings hat der Konfliktknoten einen weiteren schwarzen Vorfahren. Um diesen Sachverhalt näher zu analysieren verdeutlichen wir, dass der Vater falls er vor der Transformation  nicht schwarz war er es anschließend ist. War der Vater vor der Transformation bereits schwarz, so ist er es anschließend immernoch und er hat seinen ehemaligen Bruder nun als schwarzen Großvater. Somit beinhalten die Pfade, die duch den Konfliktknoten verlaufen einen zusätzlichen Schwarzen Knoten. Für die Pfade, die den Konfliktknoen nicht enthalten ergeben sich nun zwei möglichkeiten. Zum einen kann dieser Pfad duch den Bruder des Konfliktknotens verlaufen, in diesem Fall verliefe der Pfad vor und nach der Transformatation durch den alten Bruder sowie den neuen Vater des Konfliktknotens. In diesem Falle hätten die beiden Knoten lediglich ihre Farbe vertauscht, was zur Folge hätte, dass sich an der Schwarztiefe dieses Pfades nichts ändert. Zum anderen kann es allerdings auch sein, dass der Pfad duch den neuen Onkel, welcher das rechte bzw. das linke Kind des Bruders ist, des Konfliktknotens verläuft. Das bedeutet, dass der Pfad nach der Transformation nicht mehr duch den Bruder, dessen Vater sowie dem rechten bzw. dem linken Kind des Bruders verläuft, sondern stattdessen nur noch durch den Bruder, der nun die Farbe seines alten Vaters besitzt, sowie durch das rechte bzw. linke Kind des Bruders, dessen Farbe duch die Transformation von rot auf schwarz gewechselt hat. Beide Fälle verändern somit nichts an der Anzahl der schwarzen Knoten auf den Pfaden wodurch das Gleichgewicht wieder hergestellt ist.

 '''deleteCase6( Node n )'''
 sibling( n ).color = n.parent.color
 n.parent.color = BLACK
 if n is n.parent.left do
     sibling( n ).right.color = BLACK
     rotateLeft( n.parent )
 else do
     sibling( n ).left.color = BLACK
     rotateRight( n.parent )