1. Baumparadigma

• Idee: baue einen balancierten Binärbaum über der Eingabe
• traversiere den Baum von und zur Wurzel
• Beispiel:
  • 
    
    Präfixsummenproblem
    • INPUT: Array A[1...n]; n=2^k
    • OUTPUT: Array C(0,j) der Präfixsummen; 1 ≤ j ≤ n
    • Beispiel:
      • A = a₁, a₂, a₃, a₄. a₅
      • Präfixsummen: a₁, a₁+a₂, a₁+a₂+a₃, ...

    • 1 for j := 1 to n pardo B[0,j]:=A[j] 2 for h := 1 to log(n) do // h = Höhe
      for j := 1 to	n	pardo
      	2h
      B(h,j):=B(h-1,2j-1)+B(h-1,2j) // Bearbeitung innerhalb eines Baum-Niveau
      3 for h := log(n) to 0 do
      for j:=1..	n	pardo // für jeden Knoten des Levels h
      	2h
      if (j gerade) then C(h,j):=C(h+1,j/2)
      elseif (j>1 ungerade) then C(h,j:=Ch+1,			j-1	) + B(h,j) else C(h,1):=B(h,1) // wenn j=1
      			2

      • Idee: Baum zweimal durchlaufen
        • erst nach oben
        • dann nach unten
      • in B werden die Informationen des ersten Baum-Durchganges gespeichert
      • in C werden die Informationen des zweitern Durchgangs gespeichert
      • 1) Speichern der Blätterwerte
      • 2) Durchlaufen des Baumes von unten nach oben, dabei werden Zwischenergebnisse erzeugt
      • 3) Durchlaufen des Baumes von oben nach unten, dabei werden die Zwischenergebnisse verarbeitet
      • C(0,j) enthält am Ende die Präfixsumme
    • Animation
      • 
        
        
    • Zeit:
      • sequentiell: O(n)

      • T(n) = T(	n	) + a = O(log n)
        	2

      • W(n) = W(	n	) + b· n = O(n)
        	2

      • → Algorithmus ist optimal
      • → Frage: ist er streng optimal?
• meist erhält bei diesem Prinzip ein innerer Knoten u dann die Informationen,
  die die Blätter des Teilbaumes von u aus betreffen
• funktioniert immer, wenn zu verarbeitende Operation assoziativ ist