AuK/Sortierte Folgen SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=Bäume=
==Termminologie==
==Binäre Bäume==
=Binäre Suchbäume=
==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 Umsetzung===
'''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 Umsetzung===
'''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
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
==Einfügen eines Duplikates==
<popup name="Klassen-Definitionen">
<code id="35435435436546546">
/**
* Binary Search Tree class
* */
public class BinarySearchTree< T extends Comparable< T > > {
/**
* encapsulated class for information hiding
* */
public class Node{
Node m_LeftChild, m_RightChild, m_Parent;
T m_Element;
/**
*
* */
Node( T p_Element ){
m_Element = p_Element;
}
/**
*
* */
Node( T p_Element, Node p_Parent ){
m_Element = p_Element;
m_Parent = p_Parent;
}
/**
*
* */
Node( T p_Element, Node p_Parent, Node p_LeftChild, Node p_RightChild ){
m_Element = p_Element;
m_Parent = p_Parent;
m_LeftChild = p_LeftChild;
m_RightChild = p_RightChild;
}
/**
*
* */
public String toString(){
return m_Element.toString();
}
} // end of class Node
Node m_Root;
/**
*
* */
public void insert( T p_Element ){
if( m_Root == null )
m_Root = new Node( p_Element );
else insertRek( p_Element, m_Root );
}
/**
*
* */
public void insert( T[] p_Elements ){
for( T i : p_Elements )
insert( i );
}
/**
*
* */
private void insertRek( T p_Element, Node p_Node ){
if( p_Element.compareTo( p_Node.m_Element ) == 0 ){
Node l_Duplicate = new 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 = new Node( p_Element, p_Node );
else insertRek( p_Element, p_Node.m_LeftChild );
else
if( p_Node.m_RightChild == null )
p_Node.m_RightChild = new Node( p_Element, p_Node );
else insertRek( p_Element, p_Node.m_RightChild );
}
/**
*
* */
public Node search( T p_Element ){
return searchRek( p_Element, m_Root );
}
/**
*
* */
private Node searchRek( T p_Element, Node 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( Node 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( Node p_Node ){
// get the child
Node 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 node has an parent node
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( Node p_Node ){
Node 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;
if( 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 Node getMin( Node 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 Node getMin( ){
return getMin( m_Root );
}
/**
*
* @param p_RootNode
* @return
*/
public Node getMax( Node 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 Node getMax(){
return getMax( m_Root );
}
public Node getSuccessor( Node p_Node ){
if( p_Node == null )
return null;
if( p_Node.m_RightChild != null )
return getMin( p_Node.m_RightChild );
Node 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 Node getPredecessor( Node p_Node ){
if( p_Node == null )
return null;
if( p_Node.m_LeftChild != null )
return getMax( p_Node.m_LeftChild );
Node 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( Node p_Node ){
if( p_Node == null )
return "";
else return p_Node.toString() + '\n' + printAscending( getSuccessor(p_Node) );
}
/**
*
* @param p_Node
* @return
*/
public String printDescending( Node p_Node ){
if( p_Node == null )
return "";
else return p_Node.toString() + '\n' + printDescending( getPredecessor(p_Node) );
}
}// end of class
</code>
</popup>
==Finden eines Elementes==
==Finden des Minimums==
==Finden des Maximums==
==Finden des Nachfolgers==
==Sortierte Ausgabe des Baumes==
==Löschen eines Elementes==
===Mit einem Sohn===
===Mit zwei Söhnen===
=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===
===Fall 2===
===Fall 3===
===Fall 4===
===Fall 5===
==Löschen==
===Fall 1===
===Fall 2===
===Fall 3===
===Fall 4===
===Fall 5===