Kurs:Algorithmen und Datenstrukturen/Vorlesung/Bäume

From Wikiversity
Jump to navigation Jump to search




Bäume[edit]

In diesem Kapitel werden Bäume als kurzen Einschub behandelt. Ein Baumelement e ist ein Tupel mit v vom Wert e und sind die Nachfolger, bzw. Kinder von e. Ein Baum T ist ein Tupel mit r als Wurzelknoten (ein Baumelement) und als Knoten (Baumelemente) des Baumes mit und für alle

Man spricht von einem geordneten Baum, wenn die Reihenfolge der Kinder eines jeden Elements festgelegt ist (schreibe dann statt

Beispiel[edit]

Binärbaum Beispiel 1

Binärbaum Beispiel 2

T' ist kein Baum, da ein gemeinsames Kind haben.

Begriffe[edit]

BinärBaum Beschriftung

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.

BinärBaum Niveau

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[edit]

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.

Suchbaum

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:

Termbaum

Atomare Operationen auf Bäumen[edit]

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[edit]

 
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[edit]

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);

Beispiel Tree

Typische Problemstellungen[edit]

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[edit]

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.

Traversierung


Preorder (W-L-R):

Inorder (L-W-R):

Postorder (L-R-W):

Levelorder:

Traversierung mit Iteratoren[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg