Balancierter Baum

[Informatik]

hi^^

Ich muss Zahlen wie z.B:

35, 8, 43, 89, 92, 33, 15, 2, 3, 70, 6, 74, 23, 49, 12, 66, 17, 73, 65

in ein balancierten Baum 2. Ordnung einfügen (nacheinander einfügen) aber ich habe keine ahnung wie das geht, kann mir vielleicht jemand weiter helfen?

 

[CPoly]

Ich habe das Rotieren der Bäume gehasst. Vielleicht hilft dir das weiter: http://de.wikipedia.org/wiki/AVL-Baum#Rebalancierung

 

[Technoblade]

Erstmal herzlichen willkommen im Forum.

Ich habe mir mal ein wenig Gedanken gemacht, ob mein Ansatz richtig ist oder nicht weiß ich nicht. Aber hier meine Idee:

In deiner Aufgabenstellung steht, dass der Baum balanciert ist. Ergo kann der Höhenunterschied zwischen den verschiedenen "Enden" des Baums, also der Knoten die keine Kindknoten mehr haben, maximal eins sein. Weiterhin gibt es drei Fälle zu unterscheiden: ein Knoten hat keine Kindknoten, er hat nur einen linken, oder er hat zwei Kindknoten. In letzten Fall ist beim Durchlauf natürlich einfach normal fortzufahren. Die andere Fälle erläutere ich unten noch.

Ich würde jetzt den Baum zu durchlaufen beginnen. Sollte ein Konten nur einen linken Kindknoten haben wird der einzufügende Wert direkt an der rechten Seite eingefügt. Und wir sind fertig.
Sollte der Knoten keine Kindknoten haben wird es schon schwieriger. An solchen Stellen brauchen wir die Höhe in der wir uns Momentan befinden, weiterhin speichern wir jedes Mal die maximale Höhe die wir bisher gemessen haben und zu dieser ebenfalls den Knoten an dem diese gemessen wurde.
Liegt die momentane Höhe über der maximal gemessenen, so wird der Wert auf der linken Seite des gespeicherten Knoten mit der vorherigen maximalen Höhe eingefügt. (Wird der gesamte Baum mit diesem Algorithmus erstellt kann dieser Fall nicht eintreten, wenn der Baum von links nachts rechts durchlaufen wird). Liegt die momentane Höhe darunter wird der Wert natürlich auf der linken Seite des aktuellen Knotens eingefügt.
Sollte sich der aktuelle Knoten auf der selben Höhe befinden geschieht nichts.
In dem Fall, dass der Wert so nicht eingefügt wird (da sich alle Knoten auf der selben Höhe befinden), fügt man den Wert auf der linken Seite des gespeicherten Knotens ein.

Phu, ich hoffe das war jetzt so verständlich. Ansonsten frag ruhig nochmal nach. Über Rückmeldung ob das so richtig ist würde ich mich auch sehr freuen da ich zum Wintersemester mit einem Informatikstudium anfangen will.

 

[Technoblade]

Hi miteinander. Ich muss hier nochmal ein wenig "Threadnecrophiler" spielen, denn wir sind mittlerweile in unseren Vorlesungen so weit, dass wir bei AVL-Bäumen angekommen sind, und da wüsste ich jetzt schon gerne, ob mein Algorithmus von vor knapp einem Jahr korrekt ist, auch wenn ich mir mittlerweile selbst relativ sicher bin

 

[Bullet1990]

Wenn du nach "B-Baum Java Applet" googlest, dann findest du viele gut verständliche und einfache Animationen, die dir zeigen, wie so ein B-Baum funktioniert

Hier hab ich mal eine Java-App gefunden.
Sie beinhalten das einfügen, löschen und suchen im B-Baum.

http://slady.net/java/bt/view.php

Das gute daran ist, dass du die Bewegungen siehst, wie sich ein Knoten beim aufspalten verhält.

Ein kleiner Tipp:
Wenn du so einen balancierten Baum zeichnest, dann zeichne ihn nach jedem Schritt neu, wenn du ihn nämlich an einem Stück versuchst zu zeichnen, wird es ziemlich Fehleranfällig, wenn man noch nicht so viel Übung darin hat

Ich hab das selbst lieber mit Applets gelernt, in den Vorlesungsskripten war das oft verwirrend und ungenau beschrieben.
Bei denen kann man sich wenigstens sicher sein, dass man es richtig gemacht hat