In der Informatik ist ein binärer Baum eine Baumdatenstruktur, in der jeder Knoten höchstens zwei Kinderknoten, gewöhnlich bemerkenswert, wie "verlassen", und "Recht" hat. Knoten mit Kindern sind Elternteilknoten, und Kinderknoten können Verweisungen auf ihre Eltern enthalten. Außerhalb des Baums gibt es häufig eine Verweisung auf den "Wurzel"-Knoten (der Vorfahr aller Knoten), wenn es besteht. Jeder Knoten in der Datenstruktur kann durch das Starten am Wurzelknoten und wiederholt im Anschluss an Verweisungen entweder auf den verlassenen oder auf das richtige Kind erreicht werden.

Binäre Bäume werden verwendet, um binäre Suchbäume und binäre Haufen durchzuführen.

Definitionen für eingewurzelte Bäume

• Ein geleiteter Rand bezieht sich auf die Verbindung vom Elternteil dem Kind (die Pfeile im Bild des Baums).
• Der Wurzelknoten eines Baums ist der Knoten ohne Eltern. Es gibt höchstens einen Wurzelknoten in einem eingewurzelten Baum.
• Ein Blatt-Knoten hat keine Kinder.
• Die Tiefe eines Knotens n ist die Länge des Pfads von der Wurzel bis den Knoten. Der Satz aller Knoten an einer gegebenen Tiefe wird manchmal ein Niveau des Baums genannt. Der Wurzelknoten ist an der Tiefe-Null.
• Die Tiefe (oder Höhe) eines Baums ist die Länge des Pfads von der Wurzel bis den tiefsten Knoten im Baum. Ein (eingewurzelter) Baum mit nur einem Knoten (die Wurzel) hat eine Tiefe der Null.
• Geschwister sind Knoten, die denselben Elternteilknoten teilen.
• Ein Knoten p ist ein Vorfahr eines Knotens q, wenn er auf dem Pfad von der Wurzel bis Knoten q besteht. Der Knoten q wird dann als ein Nachkomme von p genannt.
• Die Größe eines Knotens ist die Zahl von Nachkommen, die es einschließlich sich hat.
• Im Grad eines Knotens ist die Zahl von Rändern, diesen Knoten erreichend.
• Der-Grad eines Knotens ist die Zahl von Rändern, diesen Knoten verlassend.
• Die Wurzel ist der einzige Knoten im Baum mit dem im Grad = 0.
• Alle Blatt-Knoten haben-Grad = 0.

Typen von binären Bäumen

• Ein eingewurzelter binärer Baum ist ein Baum mit einem Wurzelknoten, in dem jeder Knoten höchstens zwei Kinder hat.
• Ein voller binärer Baum (manchmal richtiger binärer Baum oder ausschließlich binärer oder 2-Bäume-Baum) ist ein Baum, in dem jeder Knoten außer den Blättern zwei Kinder hat. Manchmal wird ein voller Baum als ein vollkommener Baum zweideutig definiert.
• Ein vollkommener binärer Baum ist ein voller binärer Baum, in dem alle Blätter an derselben Tiefe oder demselben Niveau sind, und in dem jeder Elternteil zwei Kinder hat. (Das wird zweideutig auch einen ganzen binären Baum genannt.)
• Ein ganzer binärer Baum ist ein binärer Baum, in dem jedes Niveau, außer vielleicht dem letzten, völlig gefüllt wird, und alle Knoten so weit verlassen werden wie möglich.
• Ein unendlicher ganzer binärer Baum ist ein Baum mit zählbar unendliche Zahl von Niveaus, in denen jeder Knoten zwei Kinder hat, so dass es 2 Knoten am Niveau d gibt. Der Satz aller Knoten ist zählbar unendlich, aber der Satz aller unendlichen Pfade von der Wurzel ist unzählbar: Es hat den cardinality des Kontinuums. Diese Pfade, die durch eine Ordnung entsprechend sind, die Bijektion zu den Punkten des Kantoren bewahrt, gehen oder (durch das Beispiel des Strengen-Brocot Baums) zum Satz von positiven irrationalen Zahlen unter.
• Ein erwogener binärer Baum wird als ein binärer Baum allgemein definiert, in dem sich die Tiefe der zwei Subbäume jedes Knotens nie durch mehr als 1 unterscheiden, obwohl im Allgemeinen es ein binärer Baum ist, wo kein Blatt viel weiter weg von der Wurzel ist als jedes andere Blatt. (Verschiedene balancierende Schemas erlauben verschiedene Definitionen "viel weiter"). Binäre Bäume, die gemäß dieser Definition erwogen werden, haben eine voraussagbare Tiefe (wie viele Knoten von der Wurzel bis ein Blatt, Wurzel überquert werden, als Knoten 0 und nachfolgend als 1, 2..., Tiefe zählend). Diese Tiefe ist dem Teil der ganzen Zahl dessen gleich, wo die Zahl von Knoten auf dem erwogenen Baum ist. Beispiel 1: erwogener Baum mit 1 Knoten, (Tiefe = 0). Beispiel 2: erwogener Baum mit 3 Knoten, (depth=1). Beispiel 3: Der erwogene Baum mit 5 Knoten, (ist die Tiefe des Baums 2 Knoten).
• Ein eingewurzelter ganzer binärer Baum kann mit einem freien Magma identifiziert werden.
• Ein degenerierter Baum ist ein Baum wo für jeden Elternteilknoten, es gibt nur einen verbundenen Kinderknoten. Das bedeutet, dass in einer Leistungsmessung sich der Baum wie eine verbundene Listendatenstruktur benehmen wird.

Bemerken Sie, dass sich diese Fachsprache häufig in der Literatur, besonders in Bezug auf die Bedeutung "abgeschlossen" und "voll" ändert.

Eigenschaften von binären Bäumen

• Die Zahl von Knoten in einem vollkommenen binären Baum kann mit dieser Formel gefunden werden: Wo die Tiefe des Baums ist.
• Die Zahl von Knoten in einem ganzen binären Baum ist mindestens und höchstens, wo die Tiefe des Baums ist.
• Die Zahl von Blatt-Knoten in einem vollkommenen binären Baum kann mit dieser Formel gefunden werden: Wo die Tiefe des Baums ist.
• Die Zahl von Knoten in einem vollkommenen binären Baum kann auch mit dieser Formel gefunden werden: Wo die Zahl von Blatt-Knoten im Baum ist.
• Die Zahl von ungültigen Verbindungen (Kinder von Knoten fehlend), in einem ganzen binären Baum von n Knoten ist (n+1).
• Die Zahl n-L innerer Knoten (Nichtblatt-Knoten) in einem Ganzen Binären Baum von n Knoten ist .
• Für jeden nichtleeren binären Baum mit n Blatt-Knoten und n Knoten des Grads 2, n = n + 1.

:: Beweis:

::: Lassen Sie n = die Gesamtzahl von Knoten

::: B = Zahl von Zweigen

::: n, n, vertreten n die Zahl von Knoten ohne Kinder, ein einzelnes Kind und zwei Kinder beziehungsweise.

::: B = n - 1 (da alle Knoten außer dem Wurzelknoten aus einem einzelnen Zweig kommen)

::: B = n + 2*n

::: n = n + 2*n + 1

::: n = n + n + n

::: n + 2*n + 1 = n + n + n ==> n = n + 1

Allgemeine Operationen

Es gibt eine Vielfalt von verschiedenen Operationen, die auf binären Bäumen durchgeführt werden können. Einige sind mutator Operationen, während andere einfach nützliche Information über den Baum zurückgeben.

Einfügung

Knoten können in binäre Bäume zwischen zwei anderen Knoten eingefügt oder nach einem Außenknoten hinzugefügt werden. In binären Bäumen wird ein Knoten, der eingefügt wird, angegeben, betreffs dessen Kindes es ist.

Außenknoten

Sagen Sie, dass der Außenknoten, der dazu wird hinzufügt, Knoten A ist. Um einen neuen Knoten nach dem Knoten A hinzuzufügen, teilt A den neuen Knoten als eines seiner Kinder zu, und der neue Knoten teilt Knoten als sein Elternteil zu.

Innere Knoten

Die Einfügung auf inneren Knoten ist ein bisschen komplizierter als auf Außenknoten. Sagen Sie, dass der innere Knoten Knoten A ist, und dass Knoten B das Kind von A. ist (Wenn die Einfügung ein richtiges Kind einfügen soll, dann ist B das richtige Kind von A, und ähnlich mit einer linken Kindereinfügung.) Ein Zuteilen seines Kindes zum neuen Knoten und dem neuen Knoten teilt seinen Elternteil A zu. Dann teilt der neue Knoten sein Kind B zu, und B teilt seinen Elternteil als der neue Knoten zu.

Auswischen

Auswischen ist der Prozess, wodurch ein Knoten vom Baum entfernt wird. Nur bestimmte Knoten in einem binären Baum können eindeutig entfernt werden.

Knoten mit der Null oder Kindern

Sagen Sie, dass der Knoten, um zu löschen, Knoten A ist. Wenn ein Knoten keine Kinder hat (Außenknoten), wird Auswischen durch das Setzen des Kindes des Elternteils von A zur Null vollbracht. Wenn es ein Kind hat, den Elternteil des Kindes von A dem Elternteil von A gesetzt hat und das Kind des Elternteils von A dem Kind von A gesetzt hat.

Knoten mit zwei Kindern

In einem binären Baum kann ein Knoten mit zwei Kindern nicht eindeutig gelöscht werden. Jedoch in bestimmten binären Bäumen können diese Knoten einschließlich binärer Suchbäume gelöscht werden.

Wiederholung

Häufig möchte man jeden der Knoten in einem Baum besuchen und den Wert dort, ein Prozess genannt Wiederholung oder Enumeration untersuchen. Es gibt mehrere allgemeine Ordnungen, in denen die Knoten besucht werden können, und jeder nützliche Eigenschaften hat, die in auf binären Bäumen gestützten Algorithmen ausgenutzt werden:

• Vorordnung: Wurzeln Sie zuerst, Linkes Kind, Richtiges Kind ein
• Postordnung: Verlassenes Kind, Richtiges Kind, lässt einwurzeln
• Um: Verlassenes Kind, Wurzel, richtiges Kind.

Vorordnung, um, und Postordnungstraversal

Vorordnung, um, und Postordnungstraversal jeden Knoten in einem Baum durch den rekursiven Besuch jedes Knotens im verlassenen und den richtigen Subbäumen der Wurzel besuchen.

Tiefe bestellt zuerst

In der Tiefe bestellen zuerst, wir versuchen immer, den von der Wurzel am weitesten Knoten zu besuchen, dass wir können, aber mit der Verwahrung, dass es ein Kind eines Knotens sein muss, den wir bereits besucht haben. Verschieden von einer Tiefensuche auf Graphen gibt es kein Bedürfnis, sich an alle Knoten zu erinnern, die wir besucht haben, weil ein Baum Zyklen nicht enthalten kann. Vorordnung ist ein spezieller Fall davon. Sieh Tiefensuche für mehr Information.

Breite bestellt zuerst

Das Kontrastieren mit der Tiefe die erste Ordnung ist Breite zuerst, bestellt, der immer versucht, den Knoten zu besuchen, der an der Wurzel am nächsten ist, die es nicht bereits besucht hat. Sieh Breitensuche für mehr Information. Auch genannt ein Traversal der Niveau-Ordnung.

Typ-Theorie

In der Typ-Theorie wird ein binärer Baum mit Knoten des Typs A induktiv als T = μα definiert. 1 + × α × α.

Definition in der Graph-Theorie

Für jede binäre Baumdatenstruktur gibt es gleichwertigen eingewurzelten binären Baum in der Graph-Theorie.

Graph-Theoretiker verwenden die folgende Definition: Ein binärer Baum ist ein verbundener acyclic solcher Graph, dass der Grad jedes Scheitelpunkts nicht mehr als drei ist. Es kann gezeigt werden, dass in jedem binären Baum von zwei oder mehr Knoten es genau noch zwei Knoten des Grads ein gibt als, gibt es des Grads drei, aber es kann jede Zahl von Knoten des Grads zwei geben. Ein eingewurzelter binärer Baum ist solch ein Graph, der einen seiner Scheitelpunkte des Grads nicht mehr als zwei ausgesuchte als die Wurzel hat.

Mit der so gewählten Wurzel wird jeder Scheitelpunkt einen einzigartig definierten Elternteil und bis zu zwei Kinder haben; jedoch bis jetzt gibt es ungenügende Information, um ein linkes oder richtiges Kind zu unterscheiden. Wenn wir die Zusammenhang-Voraussetzung fallen lassen, vielfache verbundene Bestandteile im Graphen erlaubend, nennen wir solch eine Struktur einen Wald.

Eine andere Weise, binäre Bäume zu definieren, ist eine rekursive Definition auf geleiteten Graphen. Ein binärer Baum ist auch:

• Ein einzelner Scheitelpunkt.
• Ein gebildeter Graph durch die Einnahme zwei binärer Bäume, das Hinzufügen eines Scheitelpunkts und das Hinzufügen eines Randes hat vom neuen Scheitelpunkt bis die Wurzel jedes binären Baums befohlen.

Das gründet auch die Ordnung von Kindern nicht, aber befestigt wirklich einen spezifischen Wurzelknoten.

Combinatorics

In combinatorics denkt man das Problem, die Zahl von vollen binären Bäumen einer gegebenen Größe aufzuzählen. Hier haben die Bäume keine Werte, die ihren Knoten beigefügt sind (das würde gerade die Zahl von möglichen Bäumen durch einen leicht entschlossenen Faktor multiplizieren), und Bäume sind nur durch ihre Struktur bemerkenswert; jedoch sind der verlassene und das richtige Kind jedes Knotens bemerkenswert (wenn sie verschiedene Bäume sind, dann wird das Auswechseln von ihnen einen Baum erzeugen, der vom ursprünglichen verschieden ist). Die Größe des Baums wird genommen, um die Nummer n von inneren Knoten (diejenigen mit zwei Kindern) zu sein; die anderen Knoten sind Blatt-Knoten, und es gibt ihrer. Die Zahl solcher binären Bäume der Größe n ist der Zahl von Wegen völlig parenthesizing eine Reihe von Symbolen gleich (Blätter vertretend), getrennt von n binären Maschinenbedienern (innere Knoten vertretend), um die Argument-Subausdrücke jedes Maschinenbedieners zu bestimmen. Zum Beispiel für hat man zu parenthesize eine Schnur wie, der auf fünf Weisen möglich ist:

:

Die Ähnlichkeit zu binären Bäumen sollte offensichtlich sein, und die Hinzufügung überflüssiger Parenthesen (ringsherum bereits parenthesized Ausdruck oder um den vollen Ausdruck) wird zurückgewiesen (oder mindestens als das Produzieren einer neuen Möglichkeit nicht aufgezählt).

Es gibt einen einzigartigen binären Baum der Größe 0 (aus einem einzelnen Blatt bestehend), und jeder andere binäre Baum wird vom Paar seiner linken und richtigen Kinder charakterisiert; wenn diese Größen i und j beziehungsweise haben, hat der volle Baum Größe. Deshalb hat die Zahl von binären Bäumen der Größe n die folgende rekursive Beschreibung, und für jede positive ganze Zahl n. Hieraus folgt dass die katalanische Zahl des Index n ist.

Der obengenannte parenthesized Schnuren sollte mit dem Satz von Wörtern der Länge 2n auf der Sprache von Dyck nicht verwirrt sein, die nur aus Parenthesen auf solche Art und Weise bestehen, dass sie richtig erwogen werden. Die Zahl solcher Schnuren befriedigt dieselbe rekursive Beschreibung (jedes Wort von Dyck der Länge 2n wird durch das Subwort von Dyck bestimmt, das durch die Initiale' (' und sein Zusammenbringen')' zusammen mit dem Subwort von Dyck eingeschlossen ist, das nach dieser Schlussparenthese bleibt, deren Längen 2i und 2j befriedigen); diese Zahl ist deshalb auch die katalanische Zahl. Also gibt es auch fünf Wörter von Dyck der Länge 10:

:.

Diese Dyck Wörter entsprechen auf eine offensichtliche Weise zu binären Bäumen nicht. Eine bijektive Ähnlichkeit kann dennoch wie folgt definiert werden: Schließen Sie das Wort von Dyck in einem Extrapaar von Parenthesen ein, so dass das Ergebnis als ein Lispeln-Listenausdruck (mit der leeren Liste als nur vorkommendes Atom) interpretiert werden kann; dann der Ausdruck des punktierten Paares, für den richtige Liste völlig parenthesized Ausdruck (mit der NULL als Symbol und'.' als Maschinenbediener) das Beschreiben des entsprechenden binären Baums ist (der tatsächlich die innere Darstellung der richtigen Liste ist).

Die Fähigkeit, binäre Bäume als Reihen von Symbolen und Parenthesen zu vertreten, deutet an, dass binäre Bäume die Elemente eines freien Magmas auf einem Singleton-Satz vertreten können.

Methoden, um binäre Bäume zu versorgen

Binäre Bäume können von Programmiersprache-Primitiven auf mehrere Weisen gebaut werden.

Knoten und Verweisungen

Auf einer Sprache mit Aufzeichnungen und Verweisungen werden binäre Bäume normalerweise gebaut, indem sie eine Baumknotenstruktur gehabt wird, die einige Daten und Verweisungen auf sein linkes Kind und sein richtiges Kind enthält. Manchmal enthält es auch eine Verweisung auf seinen einzigartigen Elternteil. Wenn ein Knoten weniger als zwei Kinder hat, können einige der Kinderzeigestöcke auf einen speziellen ungültigen Wert, oder auf einen speziellen Wächter-Knoten gesetzt werden.

Auf Sprachen mit markierten Vereinigungen wie ML ist ein Baumknoten häufig eine markierte Vereinigung von zwei Typen von Knoten, von denen einer ein 3-Tupel-von Daten, verlassen Kind und richtiges Kind ist, und von denen die anderen ein "Blatt"-Knoten sind, der keine Daten enthält und viel wie der ungültige Wert auf einer Sprache mit Zeigestöcken fungiert.

Reihe

Binäre Bäume können auch in der Breite versorgt werden zuerst bestellen als eine implizite Datenstruktur in der Reihe, und wenn der Baum ein ganzer binärer Baum ist, vergeudet diese Methode keinen Raum. In dieser Kompakteinordnung, wenn ein Knoten einen Index i hat, werden seine Kinder an Indizes (für das linke Kind) gefunden und (für das Recht), während sein Elternteil (wenn irgendwelcher) am Index gefunden wird (das Annehmen, dass die Wurzel Index-Null hat). Diese Methode zieht aus kompakterer Lagerung und besserer Gegend der Verweisung besonders während eines Vorordnungstraversals einen Nutzen. Jedoch ist es teuer zu wachsen und vergeudet Raum, der zu 2 - n für einen Baum der Tiefe h mit n Knoten proportional ist.

Diese Methode der Lagerung wird häufig für binäre Haufen verwendet. Kein Raum wird vergeudet, weil Knoten in der Breite hinzugefügt werden, zuerst bestellen.

Encodings

Kurz gefasster encodings

Eine kurz gefasste Datenstruktur ist diejenige, die den absoluten minimalen möglichen Raum, wie gegründet, durch die Information theoretische niedrigere Grenzen nimmt. Die Zahl von verschiedenen binären Bäumen auf Knoten, ist die th katalanische Zahl (das Annehmen, dass wir Bäume mit der identischen Struktur als identisch ansehen). Für den großen ist das darüber; so müssen wir mindestens über Bit es verschlüsseln. Ein kurz gefasster binärer Baum würde deshalb nur 2 Bit pro Knoten besetzen.

Eine einfache Darstellung, die das entspricht, hat gebunden soll die Knoten des Baums in der Vorordnung, outputting "1" für einen inneren Knoten und "0" für ein Blatt besuchen. http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L12/lecture12.pdf, Wenn der Baum Daten enthält, können wir ihn einfach gleichzeitig in einer Konsekutivreihe in der Vorordnung versorgen. Diese Funktion vollbringt das:

fungieren Sie EncodeSuccinct (Knoten n, bitstring Struktur, Reihe-Daten) {\

wenn n = Null dann

hängen Sie 0 an, um zu strukturieren;

sonst

hängen Sie 1 an der Struktur an;

hängen Sie n.data an Daten an;

EncodeSuccinct (n.left, Struktur, Daten);

EncodeSuccinct (n.right, Struktur, Daten);

}\

Die Schnur-Struktur hat nur Bit schließlich, wo die Zahl von (inneren) Knoten ist; wir müssen seine Länge nicht sogar versorgen. Um zu zeigen, dass keine Information verloren wird, können wir die Produktion zurück zum ursprünglichen Baum wie das umwandeln:

fungieren Sie DecodeSuccinct (bitstring Struktur, Reihe-Daten) {\

entfernen Sie das erste Bit der Struktur und stellen Sie es in b

wenn b = 1 dann

schaffen Sie einen neuen Knoten n

entfernen Sie das erste Element von Daten und stellen Sie es in n.data

n.left = DecodeSuccinct (Struktur, Daten)

n.right = DecodeSuccinct (Struktur, Daten)

geben Sie n zurück

sonst

geben Sie Null zurück

}\

Hoch entwickeltere kurz gefasste Darstellungen erlauben nicht nur Kompaktlagerung von Bäumen, aber sogar nützliche Operationen auf jenen Bäumen direkt, während sie noch in ihrer kurz gefassten Form sind.

Die Verschlüsselung allgemeiner Bäume als binäre Bäume

Es gibt zwischen allgemeinen geordneten Bäumen und binären Bäumen isomorph kartografisch darzustellen, der insbesondere durch das Lispeln verwendet wird, um allgemeine geordnete Bäume als binäre Bäume zu vertreten. Um einen allgemeinen geordneten Baum zum binären Baum umzuwandeln, müssen wir nur den allgemeinen Baum im linken Kinder-Geschwister Weg vertreten. Das Ergebnis dieser Darstellung wird automatisch binärer Baum, wenn angesehen, von einer verschiedenen Perspektive sein. Jeder Knoten N im geordneten Baum entspricht einem Knoten N' im binären Baum; das linke Kind von N' ist der Knoten entsprechend dem ersten Kind von N, und das richtige Kind von N' ist der Knoten entsprechend N 's folgende Geschwister---d. h. der folgende Knoten in der Ordnung unter den Kindern des Elternteils von N. Diese binäre Baumdarstellung eines allgemeinen Ordnungsbaums wird manchmal auch linke kinderrichtige Geschwister binärer Baum (LCRS Baum), oder ein doppelt verketteter Baum oder eine Kindeserbe-Kette genannt.

Eine Denkart darüber besteht darin, dass die Kinder jedes Knotens in einer verbundenen Liste, gekettet zusammen mit ihren richtigen Feldern sind, und der Knoten nur einen Zeigestock zum Anfang oder Kopf dieser Liste durch sein linkes Feld hat.

Zum Beispiel, im Baum links, hat A die 6 Kinder {B, C, D, E, F, G}. Es kann in den binären Baum rechts umgewandelt werden.

</Zentrum>

Vom binären Baum kann als der ursprüngliche Baum gekippt seitwärts mit den schwarzen linken Rändern gedacht werden, die das erste Kind und die blauen richtigen Ränder vertreten, die folgende Geschwister vertreten. Die Blätter des Baums würden links im Lispeln als geschrieben:

: (((N O) ICH J) C D ((P) (Q)) F (M))

der im Gedächtnis als der binäre Baum rechts ohne irgendwelche Briefe auf jenen Knoten durchgeführt würde, die ein linkes Kind haben.

Siehe auch

• 2-3 Baum
• 2-3-4 Baum
• AA Baum
• B-Baum
• Binärer Raum, der verteilt
• Elastischer binärer Baum
• Baum von Huffman
• Die Ungleichheit von Kraft
• Zufälliger binärer Baum
• Recursion (Informatik)
• Rot-schwarzer Baum
• Tau (Informatik)
• Das Selbstausgleichen binären Suchbaums
• Zahl von Strahler
• Binärer Gewinde-
• Baum des primitiven Pythagoreers triples#Alternative Methoden, den Baum zu erzeugen
• Uneingewurzelter binärer Baum

Referenzen

• Donald Knuth. Die Kunst des Computers, vol 1 programmierend. Grundsätzliche Algorithmen, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89683-4. Abschnitt 2.3, besonders Paragraphe 2.3.1-2.3.2 (Seiten 318-348).
• Kenneth A Berman, Jerome L Paul. Algorithmen: Parallel, Folgend und Verteilt. Kurs-Technologie, 2005. Internationale Standardbuchnummer 0-534-42057-5. Kapitel 4. (Seiten 113-166).

Links

• lassen Sie actionscript 3 opensource Durchführung des binären Baums - opensource Bibliothek aufblitzen
• Artikel http://www.gamedev.net/reference/programming/features/trees2/ - GameDev.net über binäre Bäume
• http://www.brpreiss.com/books/opus4/html/page355.html - binärer Baumbeweis durch die Induktion
• Der erwogene binäre Suchbaum auf der Reihe, Wie man von unten nach oben eine Liste von Ahnentafel oder einen erwogenen binären Suchbaum auf der Reihe schafft