Praktikum6-Rotation in Bezug auf die Höhe!

Platinum
DON'T PANIC
Beiträge: 42
Registriert: 27. Apr 2006 13:21

Praktikum6-Rotation in Bezug auf die Höhe!

Beitrag von Platinum »

Hallo Zusammen!,

ich hab mal eine allgemeine Frage:

Wie bzw. wann hab ihr eigenltich rotiert. Wo speichert ihr euch die Höhe des Knotens ab? Während dem Einfügen nach?
Habt ihr in euerem Knoten eine extra Variable, die ihr dafür benutzt. Hab irgendwie ein Black Out momentan! ;-)

Gruss+Danke!

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Rotieren musst du beim Einfügen und Löschen, wenn du auf einen Knoten stößt, dessen Balance +2 oder -2 ist.

Ich habe die Höhe in einem Extrafeld jedes Knotens gespeichert. Nach jedem Einfügen und Löschen muss man vom betreffenden Knoten hoch zur Wurzel, hierbei kann man die Höhen und Balancewerte gleich mit aktualisieren. Bei einer Rotation muss man anschließend von bestimmten Knoten Höhe und Balance neu berechnen, weil sich ihre Kinder ändern (Höhe und Balance folgt ja unmittelbar aus der Höhe der Kinder).

Es gibt glaub ich auch die Möglichkeit, gänzlich ohne Höhe auszukommen. Die entsprechenden Formeln waren mir aber nicht auf den ersten Blick einsichtig, und ich wollte damit dann keine Zeit vergeuden ;)

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

Beitrag von ^Lara^ »

auch nochmal die frage von mir:

speichert ihr die balance als variable in eurem knoten,
oder habt ihr euch ne funktion gebastelt, die jeweils die balance eines knoten berechnet?!

ich finde momentan eine funktion einfacher, weil ich da nichts nach rotieren und hinzufügen aktualisieren muss in meinen knoten.

Wie habt ihr es gelöst?

Vielen dank und lg Lara

Azadi
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 28. Sep 2006 09:51

Beitrag von Azadi »

Du brauchst eigentlich beides. Schreibe dir doch einfach eine Funktion, die dir den Balancefaktor berechnet und dann kannst du ja nach jedem einfügen bzw. entfernen eines Knotens die Funktion aufrufen und für jeden Knoten dann den Balancefaktor neu setzen. Ist sinnvoller, wenn der Knoten seinen Balancefaktor kennt.

Benutzeravatar
R|ng0
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 24. Dez 2006 19:17

Beitrag von R|ng0 »

Azadi hat geschrieben:Du brauchst eigentlich beides. Schreibe dir doch einfach eine Funktion, die dir den Balancefaktor berechnet und dann kannst du ja nach jedem einfügen bzw. entfernen eines Knotens die Funktion aufrufen und für jeden Knoten dann den Balancefaktor neu setzen. Ist sinnvoller, wenn der Knoten seinen Balancefaktor kennt.

Nein, brauchst du nicht!
Die haesslichste Loesung waere, dass du die einfach ueber die hoehen, die du auch berechnest, die balance auszurechnest und nichts speicherst!

Auch haesslich ist, wenn du sie jedes mal die Hoehe berechnest und dann speicherst, denn dann bringt dir das speicher nicht unbedingt viel.

Die schoenst, aber wohl auch aufwendigste Loesung ist, wenn du nur mit der balance arbeitest (ist auch glaube ich so gedacht).
Du brauchst KEINE Hoehe, sondern speicherst dir zu jedem Knoten die Blance und aktualisierst diese, FALLS noetig.
Dann kommst du mit einfachen Additionen von +1 bzw. -1 aus und das nur an bestimmt Knoten (am besten noch mal Folien lesen und nachdenken, wann du das machen musst).

Wenn sich jetzt einer denkt: ,,ohne Hoehe geht nicht", dann denkt daran, welche Balance ein Blatt hat und wie sich das ganze entwickelt.

Zwar hast du mit dem speichern jedes mal den Aufwand des aktualisierens, aber der Rechenaufwand fuer jedes Mal Hoehe berechnen ist wesentlich groeßer.

Viel Erfolg!

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

R|ng0 hat geschrieben: Die haesslichste Loesung waere, dass du die einfach ueber die hoehen, die du auch berechnest, die balance auszurechnest und nichts speicherst!
Bitte zunächst ohne irgendwelches Caching arbeiten und sich drum kümmern, dass der Rest läuft. Optimieren kann man das später immer noch. Nicht 20 Baustellen gleichzeitig anfangen ...

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

R|ng0 hat geschrieben: Die schoenst, aber wohl auch aufwendigste Loesung ist, wenn du nur mit der balance arbeitest (ist auch glaube ich so gedacht).
Du brauchst KEINE Hoehe, sondern speicherst dir zu jedem Knoten die Blance und aktualisierst diese, FALLS noetig.
Dann kommst du mit einfachen Additionen von +1 bzw. -1 aus und das nur an bestimmt Knoten (am besten noch mal Folien lesen und nachdenken, wann du das machen musst).

Wenn sich jetzt einer denkt: ,,ohne Hoehe geht nicht", dann denkt daran, welche Balance ein Blatt hat und wie sich das ganze entwickelt.
Schönste Lösung? Ich weiß nicht ob es die schönste ist ^^. Ich finde es ehrlich gesagt eher hässlich, wenn man Informationen mitschleppen muss, die man eigentlich jederzeit dynamisch berechnen kann. Laufzeittechnisch ist es natürlich ineffizient, wie du schon sagtest, die Werte nicht zu cachen.
Schönheit ist hier wohl Ansichtssache, v.a. ist m.E. Effizienz i.A. ungleich Schönheit. (Diese Abkürzungen da vorne sind zum Beispiel effizient, aber nicht unbedingt schön ^^.)

Nochmal zur Höhe: Ohne Höhe geht's aber wirklich net, weil sich die Balance direkt aus der Höhe berechnet. Wie willst du denn den Balancefaktor berechnen, wenn du nicht die Höhe der Unterbäume kennst?*) Wahrscheinlich meinst du, dass du keine Höhe /speichern/ musst... das könnte ich nachvollziehen.

Gruß, Red

*) HolgerF hat ja schon geschrieben, dass das angeblich ginge. Weiß jemand wie? BFs aufaddieren kann es nicht sein.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

RomanSoldier
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 1. Dez 2005 20:32

Beitrag von RomanSoldier »

ich habe es ohne Höhe versucht und bin gescheitert; Es geht nicht, ich könnte ein Gegenbeispiel geben, falls unbedingt gewünscht, aber macht euch selbst Gedanken drüber.
Die Höhe zu speichern ist laufzeittechnisch gut aber speichertechnisch Miserabel. Die Blanace zu speichern hat laufzeittechnisch keinen Einfluss, speichertechnisch ist es nicht besser, als die Höhe zu speichern; Da es eine getBalance gibt, kann es die Laufzeit u.U. doch verbessern.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Es geht definitiv ohne. Bzw. kommt es darauf an, wie streng man "ohne" definiert. Man muss beim Einfügen oder Löschen eines Knotens die Änderung der Höhe natürlich nach oben durchgeben, um damit die Balancefaktoren der Knoten anzupassen. Dazu muss man die Höhe aber nicht speichern, und da man sowieso schrittweise vom Knoten zur Wurzel muss, um auf Rotationen zu prüfen, gibt man hier im Prinzip auch einfach nur einen Parameter weiter (entweder, die Höhe des Unterbaums ändert sich um +/- 1, oder sie tut es nicht).
Für die Balanceänderung der Knoten bei einer Rotation gibt es Formeln bzw. sogar feste Fälle, für die man die Höhen nicht braucht. Die stehen z. B. hier: http://www.cmcrossroads.com/bradapp/ftp ... Trees.html

Trotzdem ist es wesentlich einfacher, mit Höhen zu arbeiten, weil das wesentlich intuitiver ist. Obige Methode würde ich höchstens für die Freizeit und den Spaß an der Freude empfehlen ;)

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

Ahahah.... ok, also wenn ich bei diesem Wetter die Wahl zwischen Höhenberechnung eines AVLBaumes und Fahrradtour entlang eine Allee aus organischen Bäumen habe, dann wähle ich doch lieber letzteres :D

Trotzdem danke, HolgerF. So sollte es auch funktionieren.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

ich wette die bemerkung fährt dir ne rosa login-seite ein :D

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

Nein, sie ist noch blau ^^. Außerdem, wenn C. Wach das wagt, dann muss ich mich wohl nochmal mit ihm zum Tee treffen. Und dann, und dann... dann bring ich meinen eigenen mit, jawoll! :D jk
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Antworten

Zurück zu „Archiv“