Das "Wachsen" eines binären Baumes

In einem binären Baum hat jeder Knoten höchstens zwei Nachfahren. Ein solcher Baum besitzt ähnliche positive Eigenschaften wie eine Liste und hat gegenüber dieser den Vorteil des effizienteren Findens eines gesuchten Elementes.

Dabei spielt es eine wesentliche Rolle, dass die Elemente eines Baumes geordnet werden können. Andernfalls macht ein binärer Baum keinen Sinn. Die ordnende Eigenschaft muss Bestandteil jedes Knotens sein.

Ein sehr einfaches Beispiel ist ein binärer Baum, dessen Knoten ganze Zahlen enthalten. Statt ganzer Zahlen können aber auch Strings oder komplexere zusammengesetzte Datentypen verwendet werden. Am Verfahren ändert das absolut nichts.
Sie wissen, wie ganze Zahlen geordnet werden? Entschuldigen Sie bitte meine Frage!

In diesem Beispiel sei der binäre Baum zu Beginn leer, es sei also "nur der Samen" vorhanden. Lassen wir also den Baum sprießen.
Angenommen, es treffen die folgenden Zahlen in der aufgeführten Reihenfolge ein.

Beobachten wir nun den wachsenden binären Baum: Animation starten

		Die 12 trifft ein. Weil der Baum leer ist, wird die 12 zur Wurzel.
		Die 5 trifft ein. 5 < 12. Deshalb wird 5 zum linken Nachfahren der 12.
		Die -8 trifft ein. -8 < 12. Deshalb geht es zum linken Nachfahren der 12, also zur 5. -8 < 5. Deshalb wird -8 zum linken Nachfahren der 5.
		Die 75 trifft ein. 75 > 12. Deshalb wird 75 zum rechten Nachfahren der 12.
		Die 46 trifft ein. 46 > 12. Deshalb geht es zum rechten Nachfahren der 12, also zur 75. 46 < 75. Deshalb wird 46 zum linken Nachfahren der 75.
		Die 3 trifft ein. 3 < 12, zum linken Nachfahren 3 < 5, zum linken Nachfahren 3 > -8. Also wird 3 zum rechten Nachfahren der -8.
		Die 9 trifft ein. 9 < 12, zum linken Nachfahren 9 > 5. Also wird 9 zum rechten Nachfahren der 5.

Es wird selbstverständlich nur dann ein Nachfahre eingesetzt, wenn an der entsprechenden Stelle noch keiner existiert.

Sie sehen, dass der Baum etwas "linkslastig" ist. Dieses Ungleichgewicht verstärkt sich noch, wenn nur noch Zahlen eintreffen, die kleiner als 12 sind. Dann gelangen diese nämlich alle unter den linken Nachfahren der 12.

Was können wir nun mit einem solchen binären Baum anfangen?