From joe Fri Nov 26 08:40:18 1999
Subject: Re: FADS-AVL-Aufgabe
To: ***@studserv.uni-leipzig.de
Date: Fri, 26 Nov 1999 08:40:18 +0100 (MET)
X-Mailer: ELM [version 2.4ME+ PL40 (25)]
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Content-Length:  2061
Status: RO

> Wenn ich die Aufgabe diese Woche aus FADS richtig verstanden habe, so
> sollten wir ein Programm schreiben, das einen beliebigen AVL-Baum in einen
> (2,3)-Baum überführt.
> 
> Dies ist meiner Ansicht nach im allgemeinen nicht möglich.
> 
> Betrachten Sie folgendes Gegenbeispiel:
> 
> AVL-Baum, der unter sukzessivem Einfügen der Schlüssel
> 
> 22,1,35,9,31,38,30,32
> 
> entsteht: (keine Rotationen nötig; Balance in Klammern, falls <>0)
> 
>   	22 (-1)
>        /    \
>      1 (-1)   35 (+1)
> 	\       /  \
>          9     31   28
>               /  \
>              30   9
> 
> 
> Ich sehe keine Möglichkeit, diesen Baum zu einem (2,3)-Baum
> "zusammenzukringeln".
> 
> Der entsprechende (2,3)-Baum (sukzessives Einfügen) sieht so aus:
> 
> 	  31
>        /     \
>       22      35
>      /  \    /  \
>    1,9  30  32   38
> 
> 
> Hier ist die 31 in der Wurzel (Tiefe 1), beim AVL ist sie bei Tiefe 3
> und eine
> Tiefendifferenz von mehr als 1 kann man durch "zusammenkringeln" nicht
> ausbügeln.
> Alle (2,3)-Bäume der Tiefe 3 mit diesen Schlüsseln haben entweder die 30
> oder
> die 31 in der Wurzel, der einzig mögliche (2,3)-Baum mit Tiefe 2 hat die
> Knoten 22 und 32 in der Wurzel, diese sind aber nicht "direkt
> verbunden".

OK, sehr schön gesehen. 

> Die Triviallösung, einfach aus dem AVL alle Schlüssel auszulesen und in einen
> anfangs leeren (2,3)-Baum einzufügen, kanns wohl auch nicht sein.

Nein. Ich dachte wirklich, daß es geht, aber das war eine vorschnelle
Verallgemeinerung. Die Aufgabe ist mir auch erst an der Tafel eingefallen,
im Skript stehts nicht (dafür hätte ich es hoffentlich genauer getestet).

> enttäuscht nach Stunden der Arbeit

das tut mir aber leid. Wenn es Sie tröstet, bekommen Sie für das
Gegenbeispiel einen Schein. 

Mit (2,4)-Bäumen (bzw. Rot-Schwarz-Bäumen) sollte aber alles funktionieren.
Ich denke, Herr Hinze erwähnt das auch in seinem Vortrag.

MfG
-- 
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
-- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/209 --