Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Binäre Suchbäume Implementierung

Implementierung

Ein binärer Suchbaum ist eine häufig verwendete Hauptspeicherstruktur und ist besonders geeignet für Schlüssel fester Größe, z.B. numerische wie int, float und char[n]. Der Aufwand von O(log n) für Suchen, Einfügen und Löschen ist garantiert, vorausgesetzt der Baum ist balanciert. Später werden wir lernen, dass die Gewährleistung der Balancierung durch spezielle Algorithmen gesichert wird. Des weiteren sind größere, angepasste Knoten für Sekundärspeicher günstiger, diese nennt man B-Bäume. Für Zeichenketten benutzt man als Schlüssel variable Schlüsselgröße, sogenannte Tries.

public class   
      BinarySearchTree<K extends Comparable<K>>
           implements Iterable<K> {
         
          ...

    static class TreeNode<K extends Comparable<K>> {
         K key;
         TreeNode<K> left = null;
         TreeNode<K> right = null;
 
         ...
    
    }
 }

Die Schlüssel müssen Comparable-Interface, d.h. compareTo()-Methode, implementieren, da der Suchbaum auf Vergleichen der Schlüssel basiert. Der Baum selbst implementiert Iterable-Interface, d.h. iterator()-Methode, um Traversierung des Baums über Iterator zu erlauben (später Baumtraversierung).TreeNode und alles weitere werden als innere Klassen implementiert. Dadurch werden Zugriff auf Attribute und Methoden der Baumklasse erlaubt. Eine Besonderheit der Implementierung sind die „leeren“ Pseudoknoten head und nullNode zur Vereinfachung der Algorithmen (manchmal „Wächter“ / „sentinel“ genannt). Grundlegende Algorithmen sind

• Suchen
• Einfügen
• Löschen

Implementierung mit Pseudoknoten

Wir vereinbaren an dieser Stelle, dass man auf dem Kopf kein getRight() anwenden kann.

public class   
      BinarySearchTree<K extends Comparable<K>>
           implements Iterable<K> {
         
          ...

       pulic BinarySearchTree(){
            head = new TreeNode<K>(null);
            nullNode = new TreeNode<K>(null);
            nullNode.setLeft(nullNode);
            nullNode.setRight(nullNode);
            head.setRight(nullNode);
       }
         ...
    
    
 }

Das Ziel der Implementierung ist, die Reduzierung der Zahl an Sonderfällen. Im head würde das Einfügen oder Löschen des Wurzelknotens spezielle Behandlung in der Baum-Klasse erfordern. Der nullNode erspart den Test, ob zum linken oder zum rechten Teilknoten navigiert werden kann. Des weiteren ist im NullNode ein einfaches Beenden der Navigation (z.B. Beenden der Rekursion) möglich.

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.2.1 zu finden.