In der Informatik ist ein Baum einen 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 so einen sog. Elternknoten und hat entweder keinen, einen oder mehrere Kindknoten sowie keinen, einen oder mehrere Geschwisterknoten. Weisst ein Knoten keinen Elternknoten auf, so spricht man auch vom Wurzelknoten des Baumes, im umgekehrten Fall, wenn ein Knoten keine Kinder hat, spricht man von einem Blattknoten. Knoten, die weder Wurzel noch Blatt sind, sind innere Knoten. Das 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, 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
- ein spezieller Knoten existiert, der die Wurzel genannt wird,
- die verbleibenden Knoten in disjunkte Mengen aufgeteilt werden, die jeweils wiederum Bäume sind.
Es existiert eine Vielzahl von Begriffen, mit denen Bäume mit speziellen Eigenschaften bezeichnet werden:
- Binärbaum: Jeder Knoten hat höchstens zwei Kindknoten
- 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.