Blattknoten

Als Wald bezeichnet man in der Graphentheorie einen ungerichteten Graphen ohne Zyklus. Ist dieser zusammenhängend, so spricht man von einem (ungerichteten) Baum. Die Zusammenhangskomponenten eines Waldes stellen in diesem Sinne für sich einen Baum dar, so dass ein Wald aus einem oder mehreren Bäumen besteht.

Jeder ungerichtete Baum ist also auch ein Wald. Betrachtungen über Wälder lassen sich damit auch auf ungerichtete Bäume übertragen. Umgekehrt sind aber auch Betrachtungen über ungerichtete Bäume häufig leicht auf Wälder übertragbar.

Neben ungerichteten Bäumen betrachtet man auch gerichtete Bäume, die häufig auch als gewurzelte Bäume bezeichnet werden und sich weiter in In-Trees und Out-Trees unterscheiden lassen. Die Struktur entspricht im Wesentlichen der von ungerichteten Bäumen, jedoch gibt es einen ausgezeichneten Knoten, den man Wurzel nennt und für den die Eigenschaft gilt, dass alle Kanten von diesem wegzeigen (Out-Tree) oder zu diesem hinzeigen (In-Tree).

Inhaltsverzeichnis

Algorithmen auf Wäldern

Aufgrund ihrer einfachen Struktur kann die Komplexität von auf Bäumen arbeitenden Algorithmen meist gut abgeschätzt werden. Oft arbeiten die Algorithmen mit einem Baum als Datenstruktur schneller als andere Algorithmen für dasselbe Problem. Beispielsweise ist für das Problem Sortieren das auf Bäumen arbeitende Heapsort schneller als ein eher naives Insertionsort.

Sonderrolle innerhalb der Graphentheorie

Um alle Knoten eines Graphen effizient betrachten zu können, werden aus den bereits erwähnten Gründen gerne Bäume bzw. Wälder aus dem Graphen konstruiert. Dazu eignen sich Verfahren wie Breitensuche oder Tiefensuche auf den Graphen anzuwenden. Das Ergebnis ist ein Spannbaum. Ein minimaler Spannbaum wird unter gesonderter Betrachtung der Kantengewichte konstruiert, wie es durch den Algorithmus von Kruskal oder den Algorithmus von Prim geschieht. Dies dient beispielsweise als Grundlage für Algorithmen zum Problem des Handlungsreisenden.

Wichtige Aussagen und Sätze

Siehe auch


Wikimedia Foundation.

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

  • B-Baum — Ein B Baum (englisch B tree) 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… …   Deutsch Wikipedia

  • B-Tree — 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

  • B-tree — 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

  • BBaum — 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

  • 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

  • Bayerbaum — 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

  • Btree — 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

  • B+-Baum — Der B+ Baum ist eine in Datenbanken und Dateisystemen verwendete Daten oder Indexstruktur. Sie ist eine Erweiterung des B Baumes. Bei einem B+ Baum werden die eigentlichen Datenelemente nur in den Blattknoten gespeichert, während die inneren… …   Deutsch Wikipedia

  • B-Plus-Baum — Der B+ Baum ist eine Erweiterung des B Baumes. Bei einem B+ Baum werden die eigentlichen Datenelemente nur in den Blattknoten gespeichert, während die inneren Knoten lediglich Schlüssel enthalten. Ein einfaches Beispiel eines B+ Baumes welches… …   Deutsch Wikipedia

  • Blattsuchbaum — Der B+ Baum ist eine Erweiterung des B Baumes. Bei einem B+ Baum werden die eigentlichen Datenelemente nur in den Blattknoten gespeichert, während die inneren Knoten lediglich Schlüssel enthalten. Ein einfaches Beispiel eines B+ Baumes welches… …   Deutsch Wikipedia

Share the article and excerpts

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