Heute muss ich leider auf einen nicht ganz so super spannenden Artikel zurückgreifen. Nachdem ich gestern gemerkt hatte, dass die neuen Beiträge nicht mehr bei Twitter auftauchen, musste ich dem Problem auf den Grund gehen und hoffe, meine Follower wieder „nerven“ zu können.
Nun aber zum eigentlichen Thema: Binary Trees. Vor kurzem haben wir uns im Kreis der Kollegen über kleinere Performance-Probleme unterhalten und sind zu den Binärbäumen gekommen. Ich dachte mir, so eine Datenstruktur kann man sicher auch mit PHP basteln und bin eine Beispielimplementierung angegangen.
Die Implementierung sollte objektorientiert sein und so war die Überlegung ein Objekt BinaryTree zu erstellen. Ein Baum besteht aus vielen Knoten, die dann sinnigerweise vom Node-Objekt bereitgestellt werden.
Da wir mit einem Binär-Baum arbeiten, hat jeder Knoten zwei Kinder. Ein solches Kind kann null oder wiederum ein Node-Objekt mit einem Datum sein. Somit ist die Implementierung folgende:
class Node {
public $left;
public $right;
public $data;
public function __construct($newData) {
$this->left = null;
$this->right = null;
$this->data = $newData;
}
}
Die Getter/Setter habe ich mir geschenkt, würden die Programmierung aber nicht wesentlich ändern. Nun benötigt man ein BinaryTree-Objekt. Dieses hat eine Wurzel, die aus null oder einem Node bestehen kann und stellt dann Methoden bereit, um Daten in diesem Baum abzulegen. Lassen wir die Methoden außen vor und erstellen erst einmal das Gerüst.
class BinaryTree {
private $root;
public function __construct() {
$this->node = null;
}
}
Nun implementieren wir eine Methode, um ein Datum (in unserem Fall ein Integer) im Baum abzulegen.
public function insert($data) {
$this->root = $this->_insert($this->root, $data);
}
private function _insert( $node, $data) {
if ($node === null) {
$node = new Node($data);
}
else {
if ($data <= $node->data) {
$node->left = $this->_insert($node->left, $data);
}
else {
$node->right = $this->_insert($node->right, $data);
}
}
return $node;
}
Man sieht 2 Methoden. Eine öffentliche, die den eigentlichen Aufruf iniziiert. Die private Methode wird rekursiv aufgerufen und abhängig vom Datum, wird dieses einsortiert, nachdem ein neuer Knoten erstellt wurde. Wenn man den Baum aufzeichnet, so sieht man, dass die Knoten links immer kleiner als die rechten sind. Dies trifft für jede Ebene (oder Tiefe) zu. Dieser Mehraufwand beim Erstellen der Datenstruktur lohnt bei der Suche nach dem Datum und dem späteren Zugriff. Also implementieren wir die entsprechende lookup-Methode, die ebenfalls rekursiv aufgebaut ist.
public function lookup($data) {
return($this->_lookup($this->root, $data));
}
private function _lookup( $node, $data) {
if ( $node === null) {
return false;
}
if ($data === $node->data) {
return true;
}
else if ($data<$node->data) {
return($this->_lookup($node->left, $data));
}
else {
return($this->_lookup($node->right, $data));
}
}
Die lookup-Methode hat auch wieder einen öffentlichen Teil und einen privaten, der rekursiv aufgerufen wird. Das Vorgehen bei der Suche ist relativ simpel. Ich suche im linken Teilbaum, wenn der angegebene Wert kleiner als der gefundene ist. Ist er größer, suche ich im rechten Teilbaum weiter. Habe ich den Wert gefunden geben ich true zurück. Bin ich den Baum korrekt durchlaufen und stoße nur noch auf null, so ist das Datum nicht im Baum vorhanden und ich gebe false zurück. Vorteil ist, dass man nur soviele Schritte benötigt, wie die Tiefe des Baums ist. Sind die Daten relativ wild gemischt haben benötigt man genau log(n) Schritte (wobei n die Anzahl der Elemente ist). Im schlimmsten Fall (wenn die Daten geordnet ankommen) benötigt man genau n Schritte.
Die Datenstruktur lässt sich nun auch noch um weitere Methoden ergänzen, wie bspw size (was die Anzahl der Daten liefert).
Nachdem alle brav die ganze Beschreibung gelesen haben, nun die Überraschung. Ich würde in PHP ein Array benutzen und mit isset oder array_key_exists arbeiten. Bei Zahlen funktioniert das bereits so, bei anderen Objekten, würde ich versuchen diese eindeutig identifizierbar zu gestalten und über diesen Key das Objekt im Array abzulegen. Somit sollte ich die PHP internen Funktionen nutzen können und schneller an ein Ergebnis kommen. Den Beweis bleibe ich an dieser Stelle schuldig, aber vielleicht gibt es nette Anregungen in den Kommentaren 🙂