while (stupidity > reason)

Heute mal keine Rocket Science, sondern ein bisschen Grundlagen. Als mich neulich ein Kollege danach fragte musste ich feststellen, doch tatsächlich noch nie eine Datenstruktur für Bäume in Java benötigt zu haben. Die Collections API enthält, obwohl sie intern durchaus Bäume nutzt, offensichtlich keine dedizierte Schnittstelle für sie. Und so schnell hatte ich eine kleine Kata.

Es geht hier lediglich um eine schnell erstellte, einfach zu nutzende Implementierung, die keine Sonderfälle wie Binär- oder balancierte Bäume berücksicht. Zur Verwaltung verwendet sie eine Standard-Liste aus dem util-Paket. Denn so gesehen ist ein Baum nichts anderes als ein Kompositorium aus Knoten; jeder Knoten kennt einen Datensatz, seinen Eltern-Knoten und eine Menge Kind-Knoten. Wenn wir von “dem Baum” sprechen, meinen wir letztendlich einen bestimmten Wurzelknoten.

Daraus folgend könnte der Rumpf einer Knoten-Klasse und ihre Felder so aussehen:

/**
 * Eine leichtgewichtige Baumstruktur.
 * @author kaeff
 *
 * @param  Datentyp des Baums
 */
public class Node<T> implements Iterable<T>{
	private List<Node<T>> childNodes = new ArrayList<Node<T>>();
	private T data;
	private Node parent;
}

Da wir es quasi mit einem Paradebeispiel für die Nutzung von Generics zu tun haben, bleibt auch die Bindung an einen konkreten Nutzdatentyp konfigurierbar.

Eine diskussionswürdige Frage entsteht im Zusammenhang mit der Verwaltung der Kindknoten: Ist der Baum eine Spezialisierung der Liste oder verwalten wir dafür eine interne Liste? Letzteres erscheint mehrfach sinnvoll:

• Eine Ableitung würde den Schnittstellenvertrag von der Liste brechen, denn Listen und Bäume sind unterschiedliche Entitäten
• Die Wahl der konkreten Listen-Realisierung bleibt konfigurierbar (Dies ist hier im Beispiel jedoch nicht explizit berücksichtigt)
• Durch die Komposition können wir die Komplexität der Liste verstecken

Nachteilig ist lediglich die Entstehung von Boilerplate-Code durch die nötigen Delegationen an das Listen-Feld. Konkret wären das die folgenden grundlegenden Operationen auf der Kindknoten-Menge:

/**
 * Nimmt einen Knoten als Kind auf, ohne childNodes hinzuzufügen
 * @param e Der neue Kind-Knoten
 */
protected void adopt(Node<T> e) {
  if (e.getParent() == this)
    e.setParent(this);
}

/**
 * Entlässt einen Knoten als Kind, ohne ihn aus childNodes zu entfernen
 * @param o Der freizugebende Kind-Knoten
 */
protected void orphan(Object o) {
  if ((o instanceof Node<?>) && (((Node<?>) o).getParent() == this))
    ((Node<?>) o).setParent(null);
}

public boolean add(Node<T> e) {
  adopt(e);
  return childNodes.add(e);
}

public Node<T> remove(int index) {
  orphan(childNodes.get(index));
  return childNodes.remove(index);
}

public boolean remove(Object o) {
  orphan(o);
  return childNodes.remove(o);
}

public boolean addAll(Collection<? extends Node<T>> c) {
  for (Node<T> n : c)
    adopt(n);
  return childNodes.addAll(c);
}

public boolean addAll(int index, Collection<? extends Node<T>> c) {
  for (Node<T> n : c)
    adopt(n);
  return childNodes.addAll(index, c);
}

public Iterator<Node<T>> iterator() {
  return childNodes.iterator();
}

Die Benennung der Methoden orientiert sich an denen des List-Interfaces; um genauer zu sein würden sich z.B. anstattt add und remove auch addChild bzw. removeChild anbieten. Die Methoden adopt bzw. orphan sind zum Aufnehmen bzw. Freigeben von Kindknoten vorgesehen, jedoch lediglich auf der Ebene der Baum-Logik und nicht auf Ebene der childNodes-Listenverwaltung. In ihnen wird lediglich die parent-Eigenschaft des neuen bzw. alten Kindknotens verwaltet. Das Iterable-Interface implementiert die Klasse aus Convenience-Gründen.

Folgende Testklasse demonstriert die Nutzung der Node-Klasse:

public class TreeTest {

    public static void main(String[] args) {
        Node<String> root = new Node<String>("Root");
        Node<String> n1 = new Node<String>("Hallo");
        Node<String> n2 = new Node<String>("Liebe");
        Node<String> n3 = new Node<String>("Welt");
        root.add(n1);
        n1.add(n2);
        root.add(n3);

        printTree(root);
    }

    private static void printTree(Node n1) {
        printTree(n1, 0);
    }

    private static void printTree(Node n1, int intend) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < intend; i++)
             sb.append(" ");
        sb.append("--> '" + n1.getData().toString() + "'");
        System.out.println(sb.toString());
        for (Node child : n1)
            printTree(child, intend + 2);
    }

}

Was man noch tun könnte:

• Interface extrahieren: Node wird NodeListImpl, die relevanten Methoden-Rümpfe kommen in die Schnittstelle Node
• Weitere Operationen auf der Kindknoten-Liste hinzufügen und delegieren

Den kompletten Quellcode gibt’s bei Bitbucket.