Zitat:
Hast du sowas mal geschrieben? Wenn ja kannst du es mal posten oder direkt Email??
Ja, ich habe irgendwie schon alles mal programmiert
AVL und RB Trees und verlinkte Listen auf jeden Fall, allerdings noch nie eine solche Kombination wie ich sie oben beschrieben habe. Gehen tut das auf alle Fälle, davon bin ich überzeugt, und die Abschätzung der Komplexität eines solchen Mischalgos. kann man auch trocken auf rein theoretischer Basis machen.
Hier im Forum, meine ich mich erinnern zu können, muß es auch ein Source von mir für einen AVL Tree geben. Kann mich halt nicht erinnern im welchen Zusammenhang, eventuell war das der Thread mit dem DoubleChecker/Doppelte Dateienfinder oder sä.
Zum Verständnis nochmal:
Du hast eine doppelt verlinkte Liste. Jedes Element dieser Liste nenne ich mal Node. Eine Node hat zwei Felder/Member mit Namen Prev: PNode und Next: PNode. Über diese beiden Zeiger wird das Element mit seinem Vorgänger und Nachfolger verlinkt. Die doppelte Verlinkung macht es möglich diese Node sehr schnell aus der Liste zu entfernen, oder die List vorwärts und rückwärts zu iterieren.
Ein binärer Baum hat auch Elemente, nenn sie mal Node. Jede Node in einem binären Baum hat auch zwei Zeiger vom Typ PNode, allerdings benennt man sie meisten Right und Left. Zusätzlich enthält sie noch die Daten. Das die Node nur zwei untergeordnete Nodes enthalten kann kann nur ein binärer Baum entstehen. Die Art und Weise wie nun der Baum ausbalanciert wird, sprich ob die Anzahl der untergeordneten Node in Right und Left immer nur um +-1 differieren kann bestimmt den Typ des Baumes. Können sich diese Anzahlen stark unterscheiden dann ist der Baum nicht ausbalanciert, er wäre ein stinknormaler binärer Baum. Solche Bäume haben keinen Suchvorteil, d.h. deren Komplexität ist im schlechtesten Falle genauso schlecht wie eine lineare Liste. Ist die Anzahl der Linke und Rechten Hälten der Node aber immer fast identisch dann ist der Baum ausbalanciert. Die Art und Weise wie man nun effizient erreicht WIE dieses ausbalancieren funktioniert bestimmt den "Namen" des Trees. Die meistbekannten Vertreter sind die AVL und Red Black Trees. (frag mich jetzt nicht was AVL genau bedeutet, müsste ich erst nachschlagen). Gut, beide Trees balancieren ihre Nodes direkt beim Einfügen und auch Löschen einer Node in den Baum aus.
So, nun muß man noch eine Frage beantworten: Gibt es in deiner Liste Duplikate ? Das ist wichtig da es in einem normalen binären Baum niemals direkt die Möglichkeit gibt Duplikate zu speichern. In jedem Falle müsste man entweder zu einer Node eine weitere verlinkte Liste einführen in die dann alle Duplikate verwaltet werden, oder aber die Ausbalancierung würde nicht mehr korrekt funktionieren.
Ich gehe mal von Listen ohne Duplikate aus. Was passiert nun beim Umsortieren ?
Man entfernt die erste Node aus der Liste und fügt sie in die Rootnode des Tree sortiert ein. Dabei wird sie vorerst einfach Left in Root. Nun nimmt man die zweite Node aus der Liste und macht sie zu Right der Root. Anschliesend vergleicht man Left mit Right und eventuell müssen sie die Plätze tauschen, weil Left größer Right ist. Das geht nun so lange weiter bis die Liste leer ist. Auf der anderen Seite entsteht ein binärer Baum der ansich sortiert ist. Ganz ganz unten Links in diesem Baum steht die Node mit dem kleinsten Wert, ganz unten Rechts diemit dem größten Wertund gleich unterhalb der Root stehen die zwei Nodes die exakt in der Mitte aller Wertigkeiten stehen. Man kann nun sehr leicht rekursiv diesen Baum von Links nach Rechts auflösen und alle Nodes wie eine normale Liste doppelt verlinken. Schwups wurde die Liste mit der bestmöglichen Komplexität und geringstmöglichen Overhead und fast 0 Bytes zusätzlichen Speicher umsortiert.
Auf Grund der direkten binären Suche im Baum benötigt man bei zb. 1024 Nodes maximal 10 Vergleiche um deren Einfügeposition zu finden. Pro Node fällt immer nur das Umsetzen der Zeiger als Speicheroperation an, es müssen also keine großen Speicherbereich umkopiert werden. Die Neuverlinkung hat nur lineare Komplexität.
Gruß Hagen