Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Bäume

Bäume

In diesem Kapitel werden Bäume als kurzen Einschub behandelt behandelt. Ein Baumelement e ist ein Tupel $e=(v,\lbrace e_{1},...,e_{n}\rbrace )$ mit v vom Wert e und $\lbrace e_{1},...,e_{n}\rbrace$ sind die Nachfolger, bzw. Kinder von e. Ein Baum T ist ein Tupel $T=(r,\lbrace e_{1},...,e_{n}\rbrace )$ mit r als Wurzelknoten (ein Baumelement) und $\lbrace e_{1},...,e_{n}\rbrace$ als Knoten (Baumelemente) des Baumes mit $r\in \lbrace e_{1},...,e_{n}\rbrace$ und für alle $e_{i}=(v_{i},K_{i})~und~e_{j}=(v_{j},K_{j})\in \lbrace e_{1},...,e_{n}\rbrace ~gilt~K_{i}\bigcap K_{j}=\emptyset$

Man spricht von einem geordneten Baum, wenn die Reihenfolge der Kinder $\lbrace e_{1},..,e_{n}\rbrace$ eines jeden Elements $e=(v,\lbrace e_{1},...,e_{n}\rbrace )$ festgelegt ist (schreibe dann $(e_{1},...,e_{n})$ statt $\lbrace e_{1},...,e_{n}\rbrace ).$

Beispiel

$T=(v_{4},\lbrace v_{1},v_{2},v_{3},v_{4},v_{5}\rbrace )$

$v_{1}=(1,\lbrace \rbrace )$

$v_{2}=(2,\lbrace v_{1},v_{3}\rbrace )$

$v_{3}=(3,\lbrace \rbrace )$

$v_{4}=(4,\lbrace v_{2},v_{5}\rbrace )$

$v_{5}=(5,\lbrace \rbrace )$

$T'=(v_{4},\lbrace v_{2},v_{5}\rbrace )$

$v_{2}=(2,\lbrace v_{5}\rbrace )$

$v_{4}=(4,\lbrace v_{2},v_{5}\rbrace )$

$v_{5}=(5,\lbrace \rbrace )$

T' ist kein Baum, da $v_{4}~und~v_{2}$ ein gemeinsames Kind haben.

Begriffe

Ein Pfad folgt über Kanten zu verbundenen Knoten, dabei existiert zu jedem Knoten genau ein Pfad von der Wurzel. Ein Baum ist immer zusammenhängend und zyklenfrei.

Das Niveau der jeweiligen Ebene entspricht immer der jeweiligen Länge des Pfades. Die Höhe eines Baumes entspricht dem größten Niveau+1.

Anwendungen

Man benutzt Bäume beispielsweise zur Darstellung von Hierarchien, wie Taxonomien, oder für Entscheidungsbäume. Bäume werden oft genutzt um sortierte, dynamische oder lineare Datenstrukturen zu repräsentieren, da Einfüge-und Löschoperationen leicht so definiert werden können, dass die Sortierung beibehalten wird. Ein Baum kann auch als Datenindex genutzt werden und stellt so eine Alternative zu Listen und Arrays dar.

Hier wird beispielsweise nach der 5 gesucht und der Baum wird als Suchbaum genutzt.

Man kann auch einen Baum aus Termen bilden. Der Term (3+4) * 5 + 2 * 3 gibt folgenden Baum:

Atomare Operationen auf Bäumen

Zu den Operationen zählen lesen mit

root(): Wurzelknoten eines Baums
get(e): Wert eines Baumelements e
children(e): Kinderknoten eines Elements e
parent(e): Elternknoten eines Elements e

und schreiben mit

set(e,v): Wert des Elements e auf v setzen
addChild(e,e’): Füge Element e’ als Kind von e ein (falls geordneter Baum nutze addChild(e,e’,i) für Index i)
del(e): Lösche Element e (nur wenn e keine Kinder hat)

Spezialfall: Binärer Baum als Datentyp

 
class TreeNode<K extends Comparable<K>>{
          
       K key;
       TreeNode<K> left = null; 
       TreeNode<K> right = null;
         
       public TreeNode(K e) {key = e; }
       public TreeNode<K> getLeft() {return left; } 
       public TreeNode<K> getRight()  {return right; }
       public K getKey() {return key; }
         
       public void setLeft(TreeNode<K> n) {left = n;}
       public void setRight(TreeNode<K> n) {right = n;} 

         ...
         
 }

Beispiel

TreeNode<Character> root = new TreeNode<Character>(‘A‘);

TreeNode<Character> node1 = new TreeNode<Character>(‘B‘);

TreeNode<Character> node2 = new TreeNode<Character>(‘C‘);

TreeNode<Character> node3 = new TreeNode<Character>(‘D‘);

root.setLeft(node1);

root.setRight(node2);

node2.setLeft(node3);

Typische Problemstellungen

Als typische Problemstellung haben wir zum einen die Traversierung, zum Anderen das Löschen eines inneren Knotens und die daraus folgende Re-strukturierung des Baumes und das Suchen in Bäumen.

Traversierung

Bäume können visuell gut dargestellt werden. Manchmal ist jedoch eine Serialisierung der Elemente eines Baumes nötig. Man kann die Elemente eines Baumes durch Preorder-Aufzählung, Inorder-Aufzählung, Postorder-Aufzählung oder Levelorder-Aufzählung eindeutig aufzählen.

Bei der Traversierung werden systematisch alle Knoten des Baumes durchlaufen.

Preorder (W-L-R): $A\to B\to D\to E\to C\to F\to G$

Inorder (L-W-R): $D\to B\to E\to A\to F\to C\to G$

Postorder (L-R-W): $D\to E\to B\to F\to G\to C\to A$

Levelorder: $A\to B\to C\to D\to E\to F\to G$

Traversierung mit Iteratoren

Bei der Traversierung sind Iteratoren erlaubt. Diese werden schrittweise abgearbeitet und es werden Standardschleifen für die Baumdurchläufe verwendet.

 for  (Integer i : tree) 
              System.out.print(i);

Dabei ist es allerdings notwendig, dass der Bearbeitungszustand zwischengespeichert wird.

public class BinarySearchTree<K extends Comparable<K>>
      implement Iterable<K> {

   public static final int INORDER = 1;  
   public static final int PREORDER = 2;
   public static final int POSTORDER = 3;
   public static final int LEVELORDER = 4;

   private int iteratorOrder;
    ...

  public void setIterationOrder(int io) {
      if (io < i || io > 4)
          return;
      iteratorOrder = io;
  }
 public Iterator<K> iterator() {
     switch (iterationOrder) { 
         case INORDER:
            return new InorderIterator<K>(this);
         case PRORDER:
            return new PreorderIterator<K>(this);
         case POSTORDER:
            return new PostorderIterator<K>(this);
         case LEVELORDER:
            return new LevelorderIterator<K>(this);
         default:
            return new InorderIterator<K>(this);
     }
 }

Preorder Traversierung

Bei der Preorder Traversierung wird der aktuelle Knoten zuerst behandelt und dann der linke oder rechte Teilbaum.

static class TreeNode<K extends Comparable<K>> {
  ...
  public void traverse() {
      if (key==null)
          return;
      System.out.print(” ” + key);
      left.traverse();
      right.traverse();   
  }

Preorder Iteratoren

Der Wurzelknoten wird auf den Stack gelegt, anschließend der rechte Knoten und dann der linke Knoten.

 class PreorderIterator<K extends Comparable <K>>
         implements Iterator<K> {

     java.util.Stack<TreeNode<K>> st =
         new java.util.Stack<TreeNode<K>>();

     public PreorderIterator(BinarySearchTree<K> tree){
           if (tree.head.getRight() != nullNode)
                st.push(tree.head.getRight());
                
     }
  public boolean hasNext() { 
          return !st.isEmpty();
  } 
  
   public K next(){ 
       TreeNode<K> node = st.pop();
       K obj = node.getKey(); 
       node = node.getRight();
       if(node != nullNode) {
          st.push(node);  //rechten Knoten auf den Stack
       }
       node = node.getLeft(); 
       if(node != nullNode) {
          st.push(node);  //linken Knoten auf den Stack
       } 
       return obj;
   } 
}

Inorder Traversierung

Bei der Inorder Traversierung wird zuerst der linke Teilbaum behandelt, dann der aktuelle Knoten und dann der rechte Teilbaum. Als Ergebnis erhält man den Baum in sortierter Reihenfolge.

static class TreeNode<K extends Comparable<K>> {
  ...
  public void traverse() {
      if (key==null)
          return;
      left.traverse();
      System.out.print(” ” + key);
      right.traverse();   
  }

Inorder Iteratoren

Der Knoten head hat immer einen rechten Nachfolger. Es wird vom Wurzelknoten begonnen alle linken Knoten auf den Stack zu legen.

 class InorderIterator<K extends Comparable <K>>
         implements Iterator<K> {

     java.util.Stack<TreeNode<K>> st =
         new java.util.Stack<TreeNode<K>>();

     public InorderIterator(BinarySearchTree<K> tree) {
           TreeNode<K> node = tree.head.getRight();
           while (node != nullNode) {
                st.push(node);
                node = node.getLeft();
           }
    }
  public boolean hasNext() {
          return !st.isEmpty();
  }
  
   public K next(){
       TreeNode<K> node = st.pop();
       K obj = node.getKey();
       node = node.getRight();  //rechten Knoten holen
       while (node != nullNode) {
          st.push(node);
          node = node.getLeft();  //linken Knoten auf den Stack
       }
       return obj;
   }

}

Postorder Traversierung

Bei der Postorder Traversierung wird zuerst der linke und der rechte Teilbaum behandelt und dann der aktuelle Knoten. Dies kann beispielsweise genutzt werden, um einen Baum aus Termen, entsprechend der Priorität der Operatoren, auszuwerten.

static class TreeNode<K extends Comparable<K>> {
  ...
  public void traverse() {
      if (key==null)
          return;
      left.traverse();
      right.traverse();   
      System.out.print(” ” + key);
  }

Levelorder Iteratoren

Der Wurzelknoten wird in der Warteschlange eingefügt. Dann wird zuerst der linke und dann der rechte Knoten in die Warteschlange eingefügt. In dieser Implementierung wird die queue als LinkedList repräsentiert. Dies ist jedoch beliebig.

 class LevelorderIterator<K extends Comparable <K>>
         implements Iterator<K> {

   //Wurzelknoten in die Warteschlange (queue) einfügen
   java.util.Queue<TreeNode<K>> q =
         new java.util.LinkedList<TreeNode<K>>();

   public LevelorderIterator(BinarySearchTree<K> tree){
         TreeNode<K> node = tree.head.getRight();
         if (node != nullNode)
                q.addLast(node);}
  
   public K next(){
       TreeNode<K> node = q.getFirst();
       K obj = node.getKey();
       if (node.getLeft() != nullNode)
            q.addLast(node.getLeft());
       if (node.getRight() != nullNode)
            q.addLast(node.getRight());
       return obj;
   }
}

Bäume in Java

In Java gibt es keine hauseigene Implementierung für allgemeine Bäume. Einige Klassen (TreeMap, TreeSet) benutzen Bäume zur Realisierung anderer Datenstrukturen. Andere Klassen (JTree) benutzen Bäume als Datenmodell zur Visualisierung.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 14 zu finden.