a)Mit max (Node node) wird der Knoten mit mit den maximalen value gesucht, allerdings nur entlang des linken sowie rechtes Fades.
Dieser Knoten wird dann zurück gegeben.
b)
Da es im Binärenbaum mit n Knoten maximal n linke bzw n rechte Knoten gibt und die beiden If (schleife) nicht verzweigt ist, kann maximal eine Laufzeit von O(n) sein.
c)
eine übergebenen knoten ohne left und right ergibt O(1)
besteht nun unser tree aus n knoten, die nur am linken faden von der wurzel hängen mit do(tree) wird als
T(n)=
1. max(tree) aufgrufuen ergibt O(n).
2. der if case ist O(1)
3. verschaltung von if schliefe mit do also T(n-1)
=> T(n)=n^2
gleiche Argumentation für den worstcase falls nur rechten faden.
neuling96 hat dieses Bild (verkleinerte Version) angehängt:
|
