10.

 Kapitel    
BÄUME  
(Teil1)   GRUNDLAGEN  
 

Algorithmen  &  Datenstrukturen  

Prof.  Dr.  Wolfgang  Schramm  
 Übersicht  
1  

1.  Einführung  
2.  Algorithmen  
3.  EigenschaCen  von  
Programmiersprachen  
4.  Algorithmenparadigmen  
5.  Suchen  &  SorLeren  
6.  Hashing  
7.  Komplexität  von  Algorithmen  
8.  Abstrakte  Datentypen  (ADT)  
9.  Listen  
10. Bäume  
11. Graphen  
 Lernziele  des  Kapitels  
2  
2
¨  Verstehen,  was  ein  Baum  (in  der  
InformaLk)  ist?  
¨  Kennenlernen  von  
verschiedenen  Baumarten.  
¨  ADT  Baum  (Tree)  kennenlernen.  
¨  Den  ADT  Tree  mit  seinen  
verschiedenen  OperaLonen  in  
Java  implemenLeren  können.  
¨  Spezielle  Ausprägung  von  
Bäumen  kennenlernen.  
 Inhalt  
3  

1.  Einführung  
2.  Bäume  –  Begriffe,  DefiniLon  
3.  Binäre  Bäume,  binäre  Suchbäume  
4.  Balancierte  Bäume  
n  AVL-­‐Bäume  
n  B-­‐Bäume  
5.  Weitere  Bäume  
6.  SorLeren  mit  Bäumen:  Heapsort  
 Anwendungen  von  Bäumen  
5  

o  Familienstammbuch  
o  Ergebnisse  eines  Sporkurniers  („KO-­‐System“)  
o  Organigramm  
o  Gliederung  eines  Buches  
o  Datei-­‐Struktur  im  Rechner  
o  Maximum-­‐BesLmmung  rekursiv  
o  ArithmeLscher  Ausdruck  
o  …  
 Baum  –  Begriffe  1/7  
6  

o  Dynamische  Datenstruktur  
o  Anzahl  der  Elemente  beliebig:  0  ..  ∞  
o  FunkLonen  
¤  Erzeugen  à  leerer  Baum  
¤  Einfügen  à  Baum  mit  einem  Element  mehr  
¤  Rausnehmen  à  Baum  mit  einem  Element  weniger  
¤  Nachschauen,  ob  der  Baum  leer  ist  

 à  Baum  unverändert  

¤  Linken  (rechten)  Teilbaum  bilden  
 à  (neuer)  Baum  
 
o  Visualisierung  
 Baum  –  Begriffe  2/7  
7  

o  Hierarchisches  Strukturierungs-­‐  und  OrganisaLonsprinzip.  

o  Verallgemeinerte  Liste  
¤  Mehr  als  ein  Nachfolger  erlaubt  

o  Spezieller  Graph  
¤  Zusammenhängender,  zyklenfreier  Graph  
 Baum  –  Begriffe  3/7  
8  

o  Baum  =  Menge  von  Knoten  und  Kanten,  die  besondere  EigenschaCen  aufweisen.  
o  Jeder  Baum  besitzt  einen  ausgezeichneten  Knoten,  die  Wurzel  (root);  Ausnahme:  
leerer  Baum.  
o  Jeder  Knoten,  außer  der  Wurzel  ist  durch  genau  eine  Kante  mit  seinem  
Vaterknoten  (parent,  Synonyme:  Muker,  Elternknoten,  Vorgänger)  verbunden.  Er  
wird  Kind  (child  ,  Synonyme:  Tochter,  Sohn,  Nachfolger)  dieses  Knotens  genannt.  
o  Ein  Knoten  ohne  Kinder  heißt  Bla/  (leaf),  alle  anderen  Knoten  nennt  man  innere  
Knoten.  
 Baum  –  Begriffe  4/7  
9  

Vater

Kind
 Baum  –  Begriffe  5/7  
10  

o  Ein  Pfad  (path)  in  einem  Baum  ist  eine  Folge  von  unterschiedlichen  Knoten,  in  der  die  
aufeinander  folgenden  Knoten  durch  Kanten  miteinander  verbunden  sind.  
o  Zwischen  jedem  Knoten  und  der  Wurzel  gibt  es  genau  einen  Pfad.  Das  bedeutet  dass  
→  ein  Baum  zusammenhängend  ist  und  
→  es  keine  Zyklen  gibt.  

o  Das  Niveau  (level)  eines  Knotens  ist  die  Länge  des  Pfades  von  der  Wurzel  zu  diesem  
Knoten.  
o  Die  Höhe  (height)  eines  Baumes  entspricht  dem  größten  level  eines  Blakes  +  1.  

o  Es  gibt  verschiedene  Arten  von  Bäumen.  Sie  können  dadurch  charakterisiert  sein,  dass  
jeder  Knoten  eine  besLmmte  Anzahl  von  direkten  Kindern  haben  muss  und  wie  die  
Kinder  angeordnet  sind.  
 Baum  –  Begriffe  6/7  
11  

Höhe
4
Niveau/Level Pfad

1 Unterbaum

3
 Baum  –  Begriffe  7/7  
12  

¨  Bei  Vorgabe  der  Anzahl  von  Kindern:  n-­‐ärer  Baum  (n-­‐ary  tree).  
¨  Sind  die  Kinder  jedes  Knotens  in  einer  besLmmten  Reihenfolge  
geordnet:  geordneter  Baum  (ordered  tree).  
¨  Binärer  Baum  =  geordneter  Baum,  bei  welchem  jeder  Knoten  maximal  2  
Kinder  hat.  
¨  Beispiel:  arithmeLscher  Ausdruck  als  Baum  8  +  (5  –  3)  *  4  

8 *

- 4

5 3
 Visualisierung  1/2  
13  

o  Leerer  Baum   Baum

o  Nicht-­‐leerer  Baum  

Baum

Wert

Wert Wert

Wert Wert
 Visualisierung  2/2  
14  

¨  …  oder  einfacher  

 

…so… …oder so…

 Tree  –  OperaLonen  
15  

o  Binärer  Baum  (Tree)  als  ADT:  

¤  OperaNonen  /  FuncNons  (Auswahl):  
n  insert  -­‐  fügt  ein  neues  Element  in  den  Baum  ein  
   insert:  Element  ×  Tree  →  Tree  
n  remove  –  enwernt  ein  Element  aus  dem  Baum  
   remove:  Element  ×  Tree  →  Tree  
n  empty  –  erzeugt  einen  leeren  neuen  Baum  
   empty:      →  Tree  
n  isEmpty  -­‐  liefert  true  genau  dann,  wenn  der  Baum  leer  ist  
 isEmpty:  Tree  →  boolean  
 Typische  verwendete  Datentypen  für  die  
ImplemenLerung  
16  

o  Baumknoten…  
etwas  allgemeiner  

Wert
Ein
Mehrere Wert und
Werte und Wert Wert unbeschränkt viele Kinder
Kinder

Keine Werte in
inneren Knoten
und spezieller
Blatt-
Datentyp

Wert
 Tree  –  ImplemenLerung  
17  
Knotenklasse  
class TreeNode {// Node of a binary tree public int getElement () {
int elem; return elem;
TreeNode left; }
TreeNode right;
public void setLeft (TreeNode n) {
public TreeNode (int i) { left = n;
elem = i; }
left = right = null;
} public void setRight (TreeNode n) {
right = n;
public TreeNode getLeft () { }
return left;
} public void setElement (int e) {
elem = e;
public TreeNode getRight () { }
return right;
}
 Tree  –  ImplemenLerung  (allg.)  
18  

o  Knotenklasse  
class TreeNode {// Node of a binary tree public Element getElement () {
Element elem; return elem;
TreeNode left; }
TreeNode right;
public void setLeft (TreeNode n) {
public TreeNode (Element i) { left = n;
elem = i; }
left = right = null;
} public void setRight (TreeNode n) {
right = n;
public TreeNode getLeft () { }
return left;
} public void setElement (Element e) {
elem = e;
public TreeNode getRight () { }
return right;
}
 Algorithmen  zur  Traversierung  1/2  
20  

o  Inorder  (Zwischenordnung)  Durchlauf  

¤  Zuerst  wird  der  linke  Teilbaum  besucht,  dann  der  Knoten  selbst  
und  anschließend  der  rechte  Teilbaum.  
o  Preorder  (Vorordnung)  Durchlauf  
¤  Zuerst  wird  der  der  Knoten  selbst  besucht,  dann  linke  Teilbaum  und  
anschließend  der  rechte  Teilbaum.  
o  Postorder  (Nachordnung)  Durchlauf  
¤  Zuerst  wird  der  linke  Teilbaum  besucht,  dann  der  rechte  Teilbaum  
und  anschließend  der  Knoten  selbst.  
o  Levelorder  Durchlauf  (auch:  breadth-­‐first  search)  
¤  Zuerst  werden  alle  Knoten  auf  demselben    Niveau  besucht,  dann  
wird  auf  das  nächste  Niveau  gewechselt.  
 Algorithmen  zur  Traversierung  2/2  
21  

B C

D E F G

¨  Inorder  Durchlauf  

¤  D  →  B  →  E  →  A  →  F  →  C  →  G  
¨  Preorder  Durchlauf  
¤  A  →  B  →  D  →  E  →  C  →  F  →  G  
¨  Postorder  Durchlauf  
¤  D  →  E  →  B  →  F  →  G  →  C  →  A  
¨  Levelorder  Durchlauf  
¤  A  →  B  →  C  →  D  →  E  →  F  →  G  
 Traversieren  von  Bäumen:  Inorder  
22  

Start:  wurzel  7  
linker  Unterbaum  (Wurzel  4)  
     linker  Unterbaum  (Wurzel  1)  
           linker  Unterbaum  (null)  
7            Wurzel  1  1  
           rechter  Unterbaum  (null)  
     Wurzel  4  4  
     rechter  Unterbaum  (Wurzel  6)  
           linker  Unterbaum  (null)  
4 9            Wurzel  6  6  
           rechter  Unterbaum  (null)  
Wurzel  7  7  
rechter  Unterbaum  (Wurzel  9)  
1 6 8      linker  Unterbaum  (Wurzel  8)  
           linker  Unterbaum  (null)  
           Wurzel  8  8  
           rechter  Unterbaum  (null)  
...  
 Traversieren  von  Bäumen:  Preorder  
23  
 Start:  wurzel  7  
Wurzel  7  7    
linker  Unterbaum  (Wurzel  4)  
     Wurzel  4  4    
7
     linker  Unterbaum  (Wurzel  1)  
           Wurzel  1  1    
           linker  Unterbaum  (null)  
           rechter  Unterbaum  (null)  
     rechter  Unterbaum  (Wurzel  6)  
4 9            Wurzel  6  6    
           linker  Unterbaum  (null)  
           rechter  Unterbaum  (null)  
rechter  Unterbaum  (Wurzel  9)  
     Wurzel  9  9  
1 6 8
     linker  Unterbaum  (Wurzel  8)  
           Wurzel  8  8  
           linker  Unterbaum  (null)  
...  
 Algorithmus  -­‐  Inorder  
24  

Inorder  (k)  
Eingabe:  Knoten  k  eines  binären  Baums  mit  Verweis  auf  linken  ([Link])  und  rechten  
([Link])  Teilbaum  sowie  dem  Element  [Link].  
 
Inorder  ([Link]);          //  besuche  den  linken  Teilbaum  
Verarbeite  [Link];  
Inorder  ([Link]);      //  besuche  den  rechten  Teilbaum  
 Algorithmus  -­‐  Preorder  
25  

Preorder  (k)  
Eingabe:  Knoten  k  eines  binären  Baums  mit  Verweis  auf  linken  ([Link])  und  rechten  
([Link])  Teilbaum  sowie  dem  Element  [Link].  
 
Verarbeite  [Link];  
Preorder  ([Link]);          //  besuche  den  linken  Teilbaum  
Preorder  ([Link]);      //  besuche  den  rechten  Teilbaum  
 Preorder  –  Programm  
26  

private void printPreorder (TreeNode n) {

if (n != null) {// tree not empty
println([Link]());
printPreorder ([Link]());
printPreorder ([Link]());
}
}
 Algorithmus  -­‐  Postorder  
27  

Postorder  (k)  
Eingabe:  Knoten  k  eines  binären  Baums  mit  Verweis  auf  linken  ([Link])  und  rechten  
([Link])  Teilbaum  sowie  dem  Element  [Link].  
 
Postorder  ([Link]);          //  besuche  den  linken  Teilbaum  
Postorder  ([Link]);      //  besuche  den  rechten  Teilbaum  
Verarbeite  [Link];  
 Algorithmus  -­‐  Levelorder  
28  

Levelorder  (k)  
Eingabe:  Knoten  k  eines  binären  Baums  mit  Verweis  auf  linken  ([Link])  und  rechten  
([Link])  Teilbaum  sowie  dem  Element  [Link].  
 
queue  :=  leere  Warteschlange;    //  vom  Typ  Queue  
enter  (k,  q);        //    (aktuelle)    Wurzel  in  queue  aufnehmen  
while  not  isEmpty(q)  do  
 Knoten  n  :=  leave  (q);  
 Verarbeite  [Link];  
 enter  ([Link],  q);                //    linken  Sohn  in  queue  aufnehmen    
 enter  ([Link],  q);        //    rechten  Sohn  in  queue  aufnehmen    
od  
 Suchbäume  1/2  
29  

o  Bäume  bisher:  hierarchische  RepräsentaLon  und  OrganisaLon  von  Daten.  

o  WichLgstes  Einsatzgebiet  von  Bäumen:  Unterstützung  einer  effekLven  Suche.  
o  Voraussetzung  für  den  Einsatz  zum  beim  Suchen:  Schlüsselwerte  in  den  Knoten.  
⇒  Dann  ist  es  möglich  Suchbäume  aufzubauen.  
 
Wir  werden  speziell  binäre  Suchbäume  betrachten.  
 Geordneter  Baum  
30  

x7

4 9

Werte Werte
<7 >7
1 6 8
 Suchbäume  2/2  
31  

EigenschaVen  binärer  Suchbäume  

Für  jeden  inneren  Knoten  k  gilt:  

¤  Der  Knoten  k  enthält  einen  Schlüsselwert  [Link].  

¤  Alle  Schlüsselwerte  in  linken  Teilbaum  [Link]  sind  kleiner  als  [Link].  
¤  Alle  Schlüsselwerte  in  rechten  Teilbaum  [Link]  sind  größer  als  [Link].  

⇒  Die  Elemente  in  einem  Suchbaum  sind  nach  ihrem  Schlüsselwert  angeordnet.  
⇒  Auf  den  Schlüsseln  der  Elemente  ist  eine  totale  Ordnung  definiert.  
⇒  Es  wird  eine  VergleichsoperaLon  (compareTo)  für  die  Schlüssel  bereit  gestellt.  
 Binärbaum  -­‐  Einfügen  
32  

insert D
F

C I

A E G J

node D

Finden der Einfügeposition:

parent •  Wenn der Baum leer ist, wird der
einzufügende Knoten die neue Wurzel.

•  Wenn schon Knoten im Baum sind, suchen

des Elternknotens des neuen Elements.
 Binärbaum  –  insert  1/2  
33  
Die Klasse Element stellt eine Methode compareTo zur
Verfügung. Diese liefert als Ergebnis:
public boolean insert (Element i) { •  0, wenn beide Elemente gleich sind
TreeNode parent = null; •  < 0, wenn das 1. Element < 2. Element ist
TreeNode child = root; •  > 0, wenn das 1. Element > 2. Element ist

while (child != null) { // at least 1 node in tree

parent = child;
if ([Link]([Link]()) == 0)
return false; // element already in tree, i is not inserted
else if ([Link]([Link]()) < 0)
child = [Link](); // insert in left tree
else
child = [Link](); // insert in left tree
}
 Binärbaum  –  insert  2/2  
34  

// parent node found

if (parent == null) // empty tree -> insert first node

root = new TreeNode (i);
else if ([Link]([Link]()) < 0)
[Link](new TreeNode(i)); // insert left from parent
else
[Link](new TreeNode(i)); // insert left from parent

return true; // i successfully inserted

}
}
 Binärbaum  –  Löschen  1/2  
35  

o  Löschen  des  Knotens  k  –  Fallunterscheidung  

¤  Zuerst  wird  der  der  Elternknoten  von  k  besLmmt  (sofern  es  ihn  gibt).  
a)  Der  Knoten  k  ist  ein  Blak  ⇒ Es  muss  nur  der  Elternknoten  (parent)  
besLmmt  werden  und  dort  die  Referenz  auf  k  enwernt  werden.  
b)  Der  Knoten  k  besitzt  nur  ein  Kind  (child)  ⇒ Im  Elternknoten  wird  die  
Referenz  auf  das  Kind  ersetzt  durch  die  Referenz  auf  das  Kind  von  k.  
c)  Der  Knoten  ist  ein  innerer  Knoten,  d.h.  er  hat  zwei  Kinder.  Dann  gibt  
es  2  Möglichkeiten:  
i.  Der  Knoten  k  wird  ersetzt  durch  den  am  weitesten  rechts  stehenden  
Knoten  des  linken  Teilbaums,  denn  dieser  ist  in  der  SorLerreihenfolge  der  
nächste  Knoten.  
ii.  Der  Knoten  k  wird  ersetzt  durch  den  am  weitesten  links  stehenden  Knoten  
des  rechten  Teilbaums,  denn  dieser  ist  in  der  SorLerreihenfolge  der  
nächste  Knoten.  
 Binärbaum  –  Löschen  2/2  
36  

o  Ersetzen  des  Knotens:  

¤  Austausch  der  Daten  der  Knoten  
n  einfach,  aber  u.U.  viel  zu  kopieren.  
¤  Aktualisieren  der  Referenzen  der  Knoten  
n  Vermeidung  aufwändigen  Kopierens,  das  fehlerträchLg  sein  kann  (bei  
flachen  Kopien).  
n  Bei  balancierten  Bäumen  müssen  auch  immer  wieder  Referenzen  
aktualisiert  werden.  Dazu  ist  dies  eine  gute  Vorbereitung.  
 Binärbaum  –  Löschalgorithmus  1/2  
37  

RemoveNode  (T,  x)  

Eingabe:  Baum  T,  Schlüssel  x,  des  zu  löschenden  Elements.  
 
k    :=  search  (T,  x);      //  liefert  Knoten  k  mit  Schlüssel  x  im  Baum  T  
if  k  ==  null  then  return  fi;      //  x  nicht  im  Baum  
if  k  ==  [Link]    //  Sonderfall:  Wurzel  soll  gelöscht  werden  
if  [Link]  ==  null  then  [Link]  :=  [Link];  
else  if  [Link]  ==  null  then  [Link]  :=  [Link];  
else    
   child  :=  größtes  Element  im  linken  Teilbaum  von  k  (d.h.  von  [Link]);  
   ersetze  k  durch  child;  
fi  
 Binärbaum  –  Löschalgorithmus  2/2  
38  

else  //  Normaler  Knoten  soll  gelöscht  werden  

if  [Link]  ==  null  then  
   p  :=  parent(k);  //  merke  den  Elternknoten      
   if  k  ist  linkes  Kind  von  p  then  [Link]  :=  [Link];  
                                                                                 else    [Link]  :=  [Link];  fi  
else  if  [Link]  ==  null  then    
       if  k  ist  linkes  Kind  von  p  then  [Link]  :=  [Link];  
                                                                                     else    [Link]  :=  [Link];  fi  
else    
       child  :=  größtes  Element  im  linken  Teilbaum  von  k  (d.h.  von  [Link]);  
       ersetze  k  durch  child;  
fi  
fi  
 Binärbaum  –  Löschen/Fälle  1/2  
39  

remove F F node

tmp C I

A E G J

D H

E
child
C I

Löschen des Wurzelknotens A D G J

H
 Binärbaum  –  Löschen/Fälle  2/2  
40  

remove D F parent

node D I

A E G J

C H

tmp
F

C I
child

A E G J
Löschen eines inneren Knotens
H
 Komplexität  der  OperaLonen  1/2  
41  

Suchen,  Einfügen,  Löschen  

Feststellung:  es  wird  jeweils  nur  ein  Pfad  von  der  Wurzel  bis  zum  entsprechenden  
Knoten  bearbeitet.  
¤  Der  Aufwand  wird  besLmmt  durch  die  Höhe  des  Baums  ⇒ die  maximale  Höhe  
h,  die  der  Baum  erreichen  kann,  besLmmt  die  Komplexität  der  OperaLonen,  
d.h.  ist  gleich  O(h).  
¤  Die  Einfügereihenfolge  der  Elemente  besLmmt  das  Aussehen  des  Baums,  d.h.  
dieselbe  Menge  von  Elementen  führt  bei  unterschiedlicher  Eingabereihenfolge  
zu  unterschiedlichen  Bäumen.  
Beispiel:    A,  C,  E,  F,  G,  H,  I      und      F,  C,  H,  A,  E,  G,  I  
 Komplexität  der  OperaLonen  2/2  
42  

o  Welche  Höhe  kann  ein  Baum  mit  n  Knoten  erreichen?  

o  Im  schlechtesten  Fall:  Baum  entartet  zu  einer  Liste  ⇒ h  =  n.  
o  Im  besten  Fall:  Jeder  innere  Knoten  hat  immer  2  Nachfolger  ⇒ auf  Level  0  gibt  es  
einen  Knoten,  auf  Level  1  gibt  es  2  Knoten,  auf  Level  2  gibt  es  4  Knoten  etc.  auf  
Level  k  gibt  es  2k  Knoten.  D.h.  ein  Baum  der  Höhe  k+1  (wenn  Level  =  k)  kann  1  +  2  
+  4  +  .  .  .  +  2k-­‐1  +  2k  Knoten  fassen.  Sind  n  Knoten  in  einem  solchen  Baum,  dann  ist  
die  Höhe  h  =  log2n.  
o  Suchbäume  mit  logarithmischer  Höhe  nennt  man  ausgeglichene  oder  balancierte  
Bäume.  
o  Ein  Baum  heißt  ausgeglichen,  wenn  bei  einer  gegebenen  Zahl  n  von  Elementen  die  
Höhe  möglichst  klein  ist.