Höhe Berechnen? < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Fügen sie in einen AVL-Baum der Reihe nach diese Werte ein:5,6,9,12,13,4,8,10,11,16,15,14,6,4,2,1. |
Hi Leute!
Ich hab hier eine Frage wie ich erkenne wann ich eine Links- oder Rechtsrotation machen muss. Soweit bin ich aber schon mal gekommen wie ich in diesem Bild hier zeige:
![[a]](/images/paperclip.gif "Dateianhänge") AVL-Baum
Bis zum Wert 11 hat noch alles geklappt aber nun hab ich ein Problem:
In meinen Folien steht, dass die Höhe eines Knotens die maximale Distanz nach unten zu den Blättern ist.
Heißt das also, dass der Knoten 12 drei verschiedene Höhen hat? Und zwar je nachdem welchen Teilbaum man ansieht? Wenn ich den Teilbaum 12-13 ansehe hat der Knoten 12 die Höhe 1, richtig?
Wenn ich mir den Teilbaum 12-9-8 ansehe hat dann der Knoten 12 die Höhe 2. Wenn ich nun den Teilbaum 12-13 mit 12-9-8 vergleiche habe ich einen Unterschied von 1. Er ist also noch nicht entartet.
Wenn ich nun aber den Teilbaum 12-9-10-11 anschaue, hat der Knoten 12 eine Höhe 3. Dieser Teilbaum in Vergleich mit Teilbaum 12-13 ergibt mir einen Unterschied von 2 und ist somit entartet.
Bin ich mit meiner Schlussfolgerung noch richtig? Wie aber erkenne ich nun, um welche Knoten ich wann drehen muss, um der Entartung des Baums entgegen zu wirken?
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 So 13.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[a]](uploads/forum/00941897/forum-i00941897-n001.JPG "Dateianhänge"){kind=small}
AVL-Baum