000
29.10.2009, 20:30 Uhr
FloSoft
Medialer Over-Flow
(Administrator)
|
Hi Ihr, mal ne grundlegende Frage.
Ich hab momentan fürs Studium eine Projektarbeit, in dem ich u.A eine AVL-Baum DAtenstruktur implementieren muss.
Im moment schaut das ganze so aus:
| C++: |
class AVLTree : public BinarySearchTree { ... };
|
auf gut deutsch: ich hab bereits einen binären suchbaum "fertig".
Ich hab das einfügen von elementen nun so verändert, das es mir den einfügepfad mit speichert, so das ich ihn "rückwärts" wieder nach "oben" laufen kann, um die Balancefaktoren zu aktualisieren.
Nur: Dort habe ich nun das Problem.
Mal ein Beispiel: Ich füge in einen leeren Baum 10 Zahlen ein (von 1 bis 10)
Dann müsste sowas in der Richtung kommen:
1 2 3 l 4 5 l 6 7 l 8 ...
das "l" steht hierbei für "linksrotation".
bis zur 8 hatte ich bereits das korrekt hinbekommen. nur: dann wollte er mir den baum nach 8tens wieder links rotieren, obwohl das nicht stimmt.
(ich hab das ganze mal geprüft mit www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/avlbaum/ )
meine updateBalance funktion des TreeItems sieht (nach zig erfolglosen umbauten) nun so aus, nun funktioniert gar nichts mehr wirklich.
| C++: |
inline void updateBalance()
{
balance = 0;
if(right && !left)
{
if(right->getBalance() == 0)
balance = 1; // rechter überhang
else
balance = 2; // rechter überhang, muss rotiert werden
}
else if(!right && left)
{
if(left->getBalance() == 0)
balance = -1; // linker überhang
else
balance = -2;// linker überhang, muss rotiert werden
}
}
|
iwie krieg ichs grad nicht hin, ohne das jedes treeitem die komplette höhe des baumes kennt, die balancefaktoren korrekt auszurechnen.
Wo hab ich da den Denkfehler drin?
--
class God : public ChuckNorris { };
Dieser Post wurde am 29.10.2009 um 20:31 Uhr von FloSoft editiert. |
