Baum (Datenstruktur)

In der Informatik ist ein Baum eine Datenstruktur, die der Struktur eines (biologischen) Baumes nachempfunden ist, der sich ausgehend vom Stamm immer weiter verzweigt. Ein Baum besteht aus Knoten, die untereinander hierarchisch verbunden sind. Jeder Knoten kann einen sog. Elternknoten haben und hat entweder keinen, einen oder mehrere Kindknoten sowie keinen, einen oder mehrere Geschwisterknoten. Weist ein Knoten keinen Elternknoten auf, so spricht man auch vom Wurzelknoten oder der Wurzel des Baumes, im umgekehrten Fall, wenn ein Knoten keine Kinder hat, spricht man von einem Blattknoten oder einem Blatt. Knoten, die weder Wurzel noch Blatt sind, sind innere Knoten. Die maximale Anzahl der Kindknoten eines Baumes ist die Ordnung. Die Anzahl der Knoten, die man von der Wurzel aus durchwandern muss, bis man einen Blattknoten erreicht, ist die Höhe dieses Astes.

Graphentheoretisch betrachtet ist ein Baum ein zusammenhaengender, nicht unbedingt gerichteter, nicht-zyklischer Graph, mehr dazu siehe: Wälder und Bäume in der Graphentheorie.

Donald E. Knuth definiert einen Baum rekursiv: Ein Baum ist eine Menge T, die aus einem oder mehreren Knoten besteht, sodass

1. ein spezieller Knoten existiert, der die Wurzel genannt wird,
2. die verbleibenden Knoten in disjunkte Mengen aufgeteilt werden, die jeweils wiederum Bäume sind.

• Binärbaum: Jeder Knoten hat höchstens zwei Kindknoten, diese sind nach linkem Kindknoten und rechtem Kindknoten unterschieden.

  RB-Baum: Ein Implementierung eines 2-3-4-Baums.

• Balancierter Baum: Nach Möglichkeit haben alle (Teil-)Äste dieses Baums die gleiche Höhe (d.h. zwischen einem Blatt und der Wurzel sind gleich viele innere Knoten, bzw. falls eine Abweichung vorhanden ist, weil der Baum nicht vollständig ist, ist die die Aweichnung nur 1.

  AVL-Baum: An jedem Knoten dieses binären Baumes ist der Unterschied in der Höhe der beiden Teilbäume maximal 1

  B-Baum: ein Baum höherer Ordnung (durchaus im Bereich von 1000), der sich aufgrund seiner Eigenschaften schnell durchsuchen laesst.

  2-3-4-Baum: ein B-Baum der Ordnung 4

• Trie: Ein Baum zur Speicherung von mehreren Zeichenketten.

Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste"). Der Text steht unter der GNU Freie Dokumentation Lizenz.