Binärer Suchbaum und seine Merkmale?
Wir haben einen binären Suchbaum und eine Suche, die bei einem Blatt y enden soll.
Der Pfad von der Wurzel bis y teilt die Menge aller Schlüssel in folgende 3 disjunkte Mengen X,Y,Z
Dabei enthält X alle Schlüssel die links vom Suchpfad liegen, Y ist der Suchpfad und Z enthält alle, die rechts vom Pfad liegen.
nun sollen wir ein Gegenbeispiel für diese Behauptung suchen: Für jede Wah von x in X, y in Y und z in Z gilt x<=y<=z.
Nur leider fällt mir keins ein, weil es für mich komplett logisch klingt.
ein binärer Suchbaum ist ja bekannt dafür, links immer Schlüssel zu haben, die kleiner sind und rechts immer welche zu haben, die größer sind.
2 Antworten
10
/ \
1 40
\ / \
7 30 100
/ \ / \
2 8 20 (35)
/
15
Es sei 35 das betrachtete Blatt, nun sind 10,40,30,35 in Y, sowie 20 und 15 in X jedoch beide größer als 10 (aus Y).
Hoffentlich habe ich diesmal keinen Fehler drin ...
Auf der linken Seite, wenn 2 Das Blatt wäre läge 8 in Z ist aber nicht größer als 10 aus Y.
-------
Die Grundidee ist einen Teil der Blätter rechts oder links vom Pfad so zu legen, daß sie größer (kleiner) als mindestens 1 Element im Pfad sind. Dafür brauchst Du Zick-Zack bzw. Zack-Zick Abschnitte im Pfad.
Beispiel:
x = 1, y = 8, z = 5
