+1 Daumen
858 Aufrufe
Ich habe obige Frage in einem Test gehabt. Komischerweise war die richtige Antwort "nein". Warum?
Ich dachte, dass die Symmetrie eines Binärbaums an die Höhe der einzelnen Blätter gebunden wäre, in Form von

Symmetrisch bei Höhe 1,0 und -1, sonst nicht.

Im Internet habe ich leider keine wirkliche Erklärung gefunden, außer diverse Wikipedia Artikel, die eigentlich meine Definition bestätigen (es sei denn, ich verstehe sie falsch ;) ).
Vielen  für die Hilfe.
Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

Gemäss Definition in

https://de.wikipedia.org/wiki/Binärbaum

muss ein Binärbaum nicht symmetrisch sein.

Ist allerdings die Tiefe 3 und 7 Knoten vorgegeben, so sieht dieser Graph ja symmetrisch aus.

Allerdings bezieht sich 'symmetrisch' meist auf eine Verknüpfungstabelle und ihre Hauptdiagonale.

Bei Bäumen haben die Kanten (nur) eine Richtung. Die Verknüpfungstabelle ist daher nicht symmetrisch.

Symmetrisch bei Höhe 1,0 und -1, sonst nicht.

Höhe -1 kann ich mir absolut nicht vorstellen.

Avatar von 162 k 🚀

Ach okay, dann hatte ich nur eine andere Definition im Kopf. Das was ich als symmetrisch kenne, wird eigentlich ausbalanciert genannt (Rotation von Bäumen etc.). 

Höhe -1 kann ich mir absolut nicht vorstellen.

Eine negative Höhe gibt es tatsächlich (auch bei der Rotation der Bäume wichtig): https://de.wikipedia.org/wiki/Bin%C3%A4rbaum unter dem Abschnitt "Rotation von binären Bäumen". 
Dabei spricht man eigentlich von der Höhe der Teilbäume bzw. deren Blätter. Man zieht im Prinzip die Höhe des einen Teilbaums vom anderen ab (dabei kann wie gesagt auch -1 zustande kommen). Damit kann man dann die Balance der Wurzel an der die Teilbäume hängen bestimmen.

Ich hatte da wohl was durcheinander gebracht.

Vielen Dank für die Hilfe :)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community