In der Informatik ist ein Baum eine weit verwendete Datenstruktur, die eine hierarchische Baumstruktur mit einer Reihe von verbundenen Knoten vortäuscht.

Mathematisch ist es ein bestellter geleiteter Baum, mehr spezifisch ein arborescence: Ein acyclic hat Graphen verbunden, wo jeder Knoten Null oder mehr Kinderknoten und höchstens einen Elternteilknoten hat. Außerdem haben die Kinder jedes Knotens eine spezifische Ordnung.

Fachsprache

Ein Knoten ist eine Struktur, die einen Wert, eine Bedingung enthalten, oder eine getrennte Datenstruktur vertreten kann (der ein Baum seines eigenen sein konnte). Jeder Knoten in einem Baum hat Null oder mehr Kinderknoten, die darunter im Baum sind (durch die Tagung, werden Bäume gezogen, abwärts wachsend). Ein Knoten, der ein Kind hat, wird den Elternteilknoten des Kindes (oder Vorfahr-Knoten, oder höher) genannt. Ein Knoten hat höchstens einen Elternteil.

Ein innerer Knoten (auch bekannt als ein innerer Knoten oder Zweigknoten) sind jeder Knoten eines Baums, der Kinderknoten hat. Ähnlich sind ein Außenknoten (auch bekannt als ein Außenknoten, Blatt-Knoten oder Endknoten) jeder Knoten, der Kinderknoten nicht hat.

Der höchste Knoten in einem Baum wird den Wurzelknoten genannt. Der höchste Knoten seiend, wird der Wurzelknoten keinen Elternteil haben. Es ist der Knoten, an dem Operationen auf dem Baum allgemein beginnen (obwohl einige Algorithmen mit den Blatt-Knoten beginnen und Ende an der Wurzel verarbeiten). Alle anderen Knoten können davon durch folgende Ränder oder Verbindungen erreicht werden. (In der formellen Definition ist jeder solcher Pfad auch einzigartig). In Diagrammen wird es normalerweise oben gezogen. In einigen Bäumen, wie Haufen, hat der Wurzelknoten spezielle Eigenschaften. Jeder Knoten in einem Baum kann als der Wurzelknoten des an diesem Knoten eingewurzelten Subbaums gesehen werden. Ein freier Baum ist ein Baum, der nicht eingewurzelt wird.

Die Höhe eines Knotens ist die Länge des längsten Pfads nach unten zu einem Blatt von diesem Knoten. Die Höhe der Wurzel ist die Höhe des Baums. Die Tiefe eines Knotens ist die Länge des Pfads zu seiner Wurzel (d. h., seines Wurzelpfads). Das ist in der Manipulation des verschiedenen selbst balancierende Bäume, AVL Bäume allgemein erforderlich insbesondere. Herkömmlich entspricht der Wert 1 einem Subbaum ohne Knoten, wohingegen Null einem Subbaum mit einem Knoten entspricht.

Ein Subbaum eines Baums T ist ein Baum, der aus einem Knoten in T und allen seinen Nachkommen in T. besteht (Das ist von der formellen Definition des in der Graph-Theorie verwendeten Subbaums verschieden.) Der Subbaum entsprechend dem Wurzelknoten ist der komplette Baum; der Subbaum entsprechend jedem anderen Knoten wird einen richtigen Subbaum (in der Analogie zum Begriff richtige Teilmenge) genannt.

Darstellungen

Es gibt viele verschiedene Weisen, Bäume zu vertreten; allgemeine Darstellungen vertreten die Knoten als dynamisch zugeteilte Aufzeichnungen mit Zeigestöcken ihren Kindern, ihren Eltern oder beiden, oder als Sachen in einer Reihe, mit Beziehungen zwischen ihnen bestimmt durch ihre Positionen in der Reihe (z.B, binärer Haufen).

Bäume und Graphen

Die Baumdatenstruktur kann verallgemeinert werden, um geleitete Graphen durch das Entfernen der Einschränkungen zu vertreten, dass ein Knoten höchstens einen Elternteil haben kann, und dass keinen Zyklen erlaubt wird. Ränder werden noch als Paare von Knoten jedoch abstrakt betrachtet, die Begriffe Elternteil und Kind werden gewöhnlich durch die verschiedene Fachsprache (zum Beispiel, Quelle und Ziel) ersetzt. Verschiedene Durchführungsstrategien, bestehen zum Beispiel Angrenzen-Listen.

In der Graph-Theorie ist ein Baum ein verbundener acyclic Graph; wenn nicht festgesetzt, sonst sind Bäume und Graphen ungeleitet. Es gibt keine isomorphe Ähnlichkeit zwischen solchen Bäumen und Bäumen als Datenstruktur. Wir können einen willkürlichen ungeleiteten Baum nehmen, willkürlich einen seiner Scheitelpunkte als die Wurzel aufzupicken, alle seine Ränder geleitet zu machen, indem wir sie weg vom Wurzelknoten - dem Produzieren eines arborescence hinweisen - und eine Ordnung allen Knoten zuteilen lassen. Das Ergebnis entspricht einer Baumdatenstruktur. Die Auswahl einer verschiedenen Wurzel oder verschiedener Einrichtung erzeugt eine verschiedene.

Überquerende Methoden

Das Treten durch die Sachen eines Baums, mittels der Verbindungen zwischen Eltern und Kindern, wird genannt, der Baum spazieren gehend, und die Handlung ist ein Spaziergang des Baums. Häufig könnte eine Operation durchgeführt werden, wenn ein Zeigestock einen besonderen Knoten erreicht. Ein Spaziergang, in dem jeder Elternteilknoten vor seinen Kindern überquert wird, wird einen Vorordnungsspaziergang genannt; ein Spaziergang, in dem die Kinder vor ihren jeweiligen Eltern überquert werden, wird überquert wird einen Postordnungsspaziergang genannt; ein Spaziergang, in dem ein linker Subbaum eines Knotens, dann der Knoten selbst, und dann schließlich sein richtiger U-Boot-Baum überquert werden, wird um Traversal genannt. (Dieses letzte Drehbuch, sich auf genau zwei Subbäume, einen linken Subbaum und einen richtigen Subbaum beziehend, nimmt spezifisch einen binären Baum an.)

Ein Spaziergang der Niveau-Ordnung führt effektiv eine Breitensuche-Suche über die Gesamtheit eines Baums durch; Knoten sind überquertes Niveau durch das Niveau, wo der Wurzelknoten zuerst besucht, von seinen direkten Kinderknoten und ihren Geschwister gefolgt wird, die von seinen Enkelkind-Knoten und ihren Geschwister usw. gefolgt sind, bis alle Knoten im Baum überquert worden sind.

Allgemeine Operationen

• Das Aufzählen aller Sachen
• Das Aufzählen einer Abteilung eines Baums
• Das Suchen nach einem Artikel
• Das Hinzufügen eines neuen Artikels an einer bestimmten Position auf dem Baum
• Das Löschen eines Artikels
• Beschneidung: Das Entfernen einer ganzen Abteilung eines Baums
• Das Verpflanzen: Das Hinzufügen einer ganzen Abteilung zu einem Baum
• Die Entdeckung der Wurzel für jeden Knoten

Allgemeiner Gebrauch

• Das Darstellen hierarchischer Daten
• Die Speicherung von Daten in einem Weg, der es leicht auffindbar macht (sieh binäres Suchbaum- und Baumtraversal)
• Das Darstellen von sortierten Listen von Daten
• Als ein Arbeitsablauf für compositing Digitalimages für Seheffekten
• Routenplanungsalgorithmen

Siehe auch

• Baumstruktur
• Baum (Graph-Theorie)
• Baum (Mengenlehre)
• Hierarchie (Mathematik)
• Dialog-Baum

Andere Bäume

• DSW Algorithmus
• Flankenfeuer
• Verlassene kinderrichtige Geschwister binärer Baum

Referenzen

• Donald Knuth. Die Kunst der Computerprogrammierung: Grundsätzliche Algorithmen, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89683-4. Abschnitt 2.3: Bäume, Seiten 308-423.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 10.4: Eingewurzelte Bäume, Seiten 214-217 vertretend. Kapitel 12-14 (Binäre Suchbäume, Rot-schwarze Bäume, Datenstrukturen Vermehrend), Seiten 253-320.

Links

• Beschreibung aus dem Wörterbuch von Algorithmen und Datenstrukturen
• STL ähnlicher C ++ Baumklasse
• Beschreibung von Baumdatenstrukturen von ideainfo.8m.com
• lassen Sie actionscript 3 opensource Durchführung des Baums und binären Baums — opensource Bibliothek aufblitzen
• WormWeb.org: Die Interaktive Vergegenwärtigung des C. elegans Zellbaum - Vergegenwärtigt Sich den kompletten Zellabstammungsbaum des Fadenwurmes C. elegans (javascript)