Binärer Baum - Höhe bestimmen in linearer Laufzeit |
| 24.04.2015, 20:57 | Heino | Auf diesen Beitrag antworten » |
| Binärer Baum - Höhe bestimmen in linearer Laufzeit Ich präsentiere hier auch mal den Aufgabentext, damit keine Missverständnisse aufkommen: Sei v ein Knoten des Baumes T, dann gilt: - depth(v) := Länge des Pfads von der Wurzel zu v - height(v) := Länge des längsten Pfads von v zu einem Blatt - height(T) := height(root(T)) - level(v) := height(T) - depth(v) Zeigen Sie, dass das Level eines jeden Knotens in einem binären Baum in Linearzeit bestimmt werden kann. Geben Sie dazu einen geeigneten Algorithmus an und zeigen Sie dessen Korrektheit und Laufzeit. Nun, soweit ja nicht so kompliziert. Wegen den Tipps hab ich einfach mal beschlossen, erstmal height(T) und depth(v) zu bestimmen - die Subtraktion danach "verbraucht" ja keine Laufzeit. Und da stoß ich schon auf erste Probleme: Ich würde beide rein intuitiv erstmal rekursiv lösen. height zB ist die größere height der beiden Kinder + 1. Aber bin ich dann nicht schon runter von der Linearzeit? Mit dieser Zeitbestimmung hab ich eh noch so meine Probleme... angenommen, height(Blatt) braucht konstante Zeit c (was ja ausreicht, da keine weitere Rekursionsstufe vorhanden) und height(kein Blatt) braucht konstante Zeit d (für Vergleiche, Arrayaufrufe etc.) + die Zeit der beiden Kinder-heights. Sagt man grob c = d da eh beides konstant ist, verdreifacht sich also die Laufzeit auf jeder Ebene des Baums, ist also definitiv nicht mehr linear. Wozu überhaupt linear? Der Aufgabentext ist so schwammig dass es alles mögliche sein könnte... Anzahl Knoten, Höhe des Baums? Mir fällt leider keine Möglichkeit ein, die es schneller macht... man muss ja jeden Knoten/Blatt zumindest mal untersuchen, da man keinen auslassen kann (sonst übersieht man ausgerechnet den längsten Pfad)... Bei depth ists das gleiche Problem, rekursiv wird die Laufzeit zu groß... |
||
| 24.04.2015, 22:47 | Heino | Auf diesen Beitrag antworten » |
PS: Scheinbar hab ich das mit der Laufzeit einfach noch nicht kapiert, denn offenbar ist die rekursive Lösung schon richtig so. Wie bestimmt man die Laufzeit denn dann korrekt? Ich hatte Zuweisungen, Vergleiche, Arrayaufrufe und solche Elementaroperationen gezählt. Diese sind natürlich konstant, aber die vergrößert sich ja auf dem "Rekursions-Rückweg" nach oben wieder. Kann man die Konstante einfach O(1) nennen und dann 3n*O(1) = O(n) -> linear sagen? Da man in einem Baum mit n Knoten höchstens alle n Knoten nach oben durchgehen muss (nämlich wenn der Baum zur Liste degeneriert ist). So würde ich vielleicht tatsächlich auf ne lineare Zeit kommen. So richtig sicher bin ich mir da aber noch nicht mit... |
||
| 24.04.2015, 23:57 | RavenOnJ | Auf diesen Beitrag antworten » |
| RE: Binärer Baum - Höhe bestimmen in linearer Laufzeit Du wirst in jedem Fall auf O(n) kommen, da jeder Knoten einmal besucht werden muss, egal, ob der Baum ausbalanciert ist oder nicht. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
