Vertauschen ohne Gestalt im Suchbaum zu verändern.

Question

1. Seien a₁, ..., a_n unterschiedliche Zahlen. Ist es möglich, zwei Zahlen untereinander
zu vertauschen, ohne dass sich die Gestalt des zugehörigen Suchbaumes verändert.

Ich habe die Aussage bereits verstanden anhand eines Beispiels mit der Reihenfolge

2,3,1 und 2,1,3. Kann mir vielleicht jemand einen Ansatz geben es allgemein zu formulieren.

Answer 1

Es gibt zwei Fälle, die beim Vertauschen von \(a_i\) und \(a_j\) im Suchbaum vorkommen können.

\(a_i\) und \(a_j\) befinden sich in unterschiedlichen Teilbaumen eines jüngsten gemeinsamen Vorfahren \(a_k\notin \{a_i, a_j\}\). Dann wecheln \(a_i\) und \(a_j\) durch Vertauschen die Teilbäume von \(a_k\) und der resultierende Baum ist kein Suchbaum mehr.

Es ist o.B.d.A. \(a_i\) Vorfahre von \(a_j\). Dann landet \(a_i\) durch Vertauschen im falschen Teilbaum von \(a_j\) und der resultierende Baum ist kein Suchbaum mehr.