Binärer Suchbaum - gesuchter Weg und mögliche Pfade

Question

Aufgabe:

Gegeben: binärer Suchbaum mit Einträgen zwischen 1 - 1000.

Gesucht: Eintrag mit dem Wert 363.

Welche der Zahlenfolgen kann nicht die Reihenfolge der betrachteten Schlüssel sein?

a) 2; 252; 401; 398; 330; 363
b) 399; 387; 219; 266; 382; 381; 278; 363
c) 3; 923; 220; 911; 244; 898; 258; 362; 363
d) 4; 924; 278; 347; 621; 299; 392; 358; 363
e) 5; 925; 202; 910; 245; 363

Problem/Ansatz:

Zuerst einmal ist etwas irritierend, dass die Wurzel in 4 von 5 Fällen einen so kleinen Wert hat, was den Baum ab einer bestimmten Anzahl an Werten extrem unbalanciert macht, allerdings ist von keinem AVL-Baum die Rede, also sollte das hier kein Problem sein, auch wenn die Suche extrem kostspielig werden kann.

Ich bin so vorgegangen: bei jedem Wert x in der gegebenen Reihenfolge ( a) - e) ) habe ich gefragt: Ist 363 größer oder kleiner x? Die entsprechende Antwort muss auch auf den Nachfolger von x zutreffen, sonst nimmt man den falschen Pfad. Mein Ergebnis ist jedoch, dass alle Reihenfolgen möglich sind - habe ich irgendwo einen Denkfehler?

Answer 1

a) 2; 252; 401; 398; 330; 363

2
\
252
  \
   -------------
                \
                401
                /
            398
            /
          /
        /
    330
        \
        363

Ersetze die 398 durch 360. Dann kann die Zahlenfolgen nicht die Reihenfolge der betrachteten Schlüssel sein, weil schon bei der 360 rechts abgebogen hätte werden müssen um zur 363 zu kommen.

Ersetze die 252 durch 360. Dann kann die Zahlenfolgen ebenfalls nicht die Reihenfolge der betrachteten Schlüssel sein, weil die 330 im linken Teilbaum der 360 liegen muss.

Die entsprechende Antwort muss auch auf den Nachfolger von x zutreffen

Das ergibt keinen Sinn. Der Nachfolger von x ist weder größer, noch kleiner.

Größer und Kleiner sind Beziehungen zwischen Zahlen und nicht Eigenschaften einzelner Zahlen. Du solltest deshalb angeben, welche Zahl größer oder kleiner als welche andere Zahl ist.