Baum (Informatik)

Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in ungerichtete Bäume und gewurzelte Bäume, und für gewurzelte Bäume in Out-Trees, bei denen die Kanten von der Wurzel ausgehen, und In-Trees, bei denen Kanten in Richtung Wurzel zeigen.

Darstellung aller Bäume mit einer, zwei oder drei Kanten bei der ersten mathematischen Modellierung von Bäumen durch Arthur Cayley (1857)

In der Informatik werden Bäume häufig als Datenstruktur eingesetzt. In diesem Fall werden sie aber anders repräsentiert als allgemeine Graphen. Durch Entfernen einer Kante zerfällt ein Baum in zwei Teilbäume und bildet damit einen so genannten Wald.

Inhaltsverzeichnis

Spezielle Bäume

Es existiert eine Vielzahl von Begriffen, die Bäume näher spezifizieren. So gibt es zum Beispiel

Äquivalente Charakterisierungen von Bäumen

Für einen Graphen G = (V,E) mit | V | = n Knoten und | E | = m Kanten sind äquivalent:

  • G ist ein Baum.
  • Zwischen je zwei Knoten von G gibt es genau einen Weg.
  • G ist zusammenhängend und es gilt m = n − 1. (Es gibt immer eine Kante weniger als Knoten)
  • G enthält keinen Zyklus und es gilt m = n − 1.
  • G enthält keinen Zyklus und G + e enthält genau einen Zyklus (e \in {V \choose 2}\setminus E beliebig).
  • G ist zusammenhängend, G + e enthält genau einen Zyklus (e \in {V \choose 2} \setminus E beliebig).
  • G ist (minimal) zusammenhängend und (maximal) azyklisch.

Bäume als Datenstruktur

Gewurzelte Bäume, insbesondere Out-Trees, werden häufig als Datenstruktur verwendet. Bei beschränkter Ordnung können diese so implementiert werden, dass jeder Knoten einen festen Satz an Variablen oder ein Array für die Referenzen auf seine Kinder enthält. Häufig besitzen die Knoten auch eine Referenz auf ihren Elternknoten (back pointer). Ein Baum unbeschränkter Ordnung kann implementiert werden, indem man statt Arrays dynamische Listen verwendet. In Programmiersprachen ohne dynamische Listen hat sich auch ein Verfahren bewährt, bei dem ein allgemeiner Baum durch einen Binärbaum implementiert wird:

Die rötliche Linie zeigt dabei den realisierten allgemeinen Baum, während die Pfeile die tatsächlichen Zeigerstrukturen repräsentieren. Das Grundprinzip besteht darin, dass ein Zeiger jeweils auf den am weitesten links stehenden Sohn zeigt, während der andere auf den rechten Bruder verweist. Hierbei ist zwar ein direkter Zugriff auf einzelne bestimmte Sohn-Knoten nicht mehr möglich, da man sich über die Geschwister voranarbeiten muss. Dafür ist diese Implementierung sehr speichereffizient.

Zeichnen von Bäumen

Die grafische Ausgabe eines Baums ist ein nicht triviales Problem. Allgemein gilt, dass jeder Baum planar, das heißt ohne Überschneidungen der Kanten gezeichnet werden kann. Je nach Anwendungszweck gibt es weitere Wünsche an die Art der Ausgabe:

  • alle Kanten sind gerade Linien
  • alle Knoten haben ganzzahlige Koordinaten
  • möglichst kleiner Platzbedarf bei möglichst ästhetischem Ergebnis
  • alle Kanten von Vater zum Kind streng monoton fallend

Es gibt verschiedene Algorithmen, deren Ergebnisse recht verschieden aussehen. Meist lösen sie nur einige, aber nicht alle Wünsche an die Ausgabe. Bekannte Algorithmen sind die HV-Bäume (Horizontal-Vertikal) und der Algorithmus von Walker.

Siehe auch

Quellen


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Informatik — ist die „Wissenschaft von der systematischen Verarbeitung von Informationen, besonders der automatischen Verarbeitung mit Hilfe von Digitalrechnern“ [1]. Historisch hat sich die Informatik einerseits aus der Mathematik entwickelt, andererseits… …   Deutsch Wikipedia

  • Baum (Begriffsklärung) — Baum (westgermanisch boum „Baum“, „Baumstamm“) bezeichnet: Baum in der Botanik die Wuchsform einer Pflanze Baum (Familienname), Namensträger siehe dort. Baum (Graphentheorie), in der Graphentheorie einen speziellen Graphen und in der Informatik… …   Deutsch Wikipedia

  • Baum — azyklischer, zusammenhängender Graph * * * Baum [bau̮m], der; [e]s, Bäume [ bɔy̮mə]: großes Gewächs mit einem Stamm aus Holz, aus dem Äste wachsen, die sich in Zweige (mit Laub oder Nadeln) teilen: die Bäume schlagen aus, blühen, lassen ihre… …   Universal-Lexikon

  • Baum (Datenstruktur) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baum-Topologie — Topologien: Ring, Mesh, Stern, vollvermascht; Linie/Reihe, Baum, Bus Die Topologie bezeichnet bei einem Computernetz die Struktur der Verbindungen mehrerer Geräte untereinander, um einen gemeinsamen Datenaustausch zu gewährleisten. Die Topologie… …   Deutsch Wikipedia

  • Baum (Graphentheorie) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baum-Welch-Algorithmus — In der Informatik und in statistischen Berechnungsmodellen wird der Baum Welch Algorithmus benutzt, um die unbekannten Parameter eines Hidden Markov Models (HMM) zu finden. Er nutzt den Forward Backward Algorithmus zur Berechnung von… …   Deutsch Wikipedia

  • Und-Oder-Baum — Ein Und Oder Baum ist eine Art Entscheidungsbaum aus der Informatik und dient als Datenstruktur in der Künstlichen Intelligenz, insbesondere beim Minimax Algorithmus und der Means Ends Analysis. Generell findet er oft Einsatz bei… …   Deutsch Wikipedia

  • Binomial-Baum — In der Informatik ist ein Binomial Heap eine Datenstruktur, genauer ein Heap, der sich, ähnlich wie binäre Heaps, als Vorrangwarteschlange einsetzen lässt. Das heißt, dass in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in …   Deutsch Wikipedia

  • Bayer-Baum — Ein B Baum ist in der Informatik eine Daten oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B Baum ist ein immer vollständig balancierter Baum, der Daten sortiert nach Schlüsseln speichert. Das Einfügen,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”