- arithmetische Ausdrücke können als Baum dargestellt werden
- Blätter = Werte
- innere Knoten = Operationen
- man will parallele Auswertung ermöglichen
- Harke (Rake):
- nehme Blatt + zugehörigen Vater
- entferne diese
- verbinde Großvater mit Rest
- mehrfache Anwendung Þ Baumkontraktion
- Zielstellung:
komplizierten Baum durch fortwährende Anwendung reduzieren auf Wurzel und 2 Söhne
Auswertung soll möglich bleiben
Ziel
Problem
- sei A ein Array
- dann soll Aodd = (a1, a3, a5, ...) das zugehörige Array der Elemente mit ungeradzahligem Index sein
- dann soll Aeven = (a2, a4, a6,...) das zugehörige Array der Elemente mit geradzahligem Index sein
- Aodd und Aeven können parallel aus A erzeugt werden
- O(1) Zeit
- O(n) Work
- zunächst entfernen der ungeradzahligen Blätter, die linke Söhne sind
- INPUT
- Wurzelbaum, innere Knoten haben o.B.d.A. genau 2 Söhne
- "v ≠ root: p(v), brother(v)
- OUTPUT
kontrahierter Baum
(mit nur noch 3 Knoten)
- begin
1. Markiere die Blätter, außer dem ganz linken und dem ganz rechten;
Packe sie in ein Array der Länge n // im Beispiel die Blätter 1-7- // A = Aodd + Aeven
- kann realisiert werden mit
- Eulertour-Technik
- 2. for i=1..\ceil{log (n+1)} do
- wende Rake parallel auf Blätter an, die linke Söhne sind (Aodd)
- wende Rake parallel auf Blätter an, die rechte Söhne sind (Aodd)
- A:=Aeven
- end
- Ablauf
- Beispiel 1
Beispiel 2 (animiert)
- Beispiel 1
- Analyse:
- läuft in O(log n) Zeit auf der EREW
- O(n) WOrk
- Beweis:
nach jedem Schleifendurchlauf verringert sich die Zahl der Blätter von m zu \floor{ m } 2 - Þ nach \ceil{log (n+1)} Iterationen sind alle Blätter bis auf die äußeren weg
- Repräsentation & Auswertung
arithmetischer Ausdrücke- wir ordnen jedem Knoten v eine Marke (av,bv) zu
- repräsentiert den Ausdruck av·X+bv
- X steht für den unbekannten Wert, der dem Teilausdruck im Knoten v entspricht
- während der Baumkontraktion erhalten wir die folgende Invariante I:
- sei u innerer Knoten
- enthält Operationszeichen £ Î {"+","·"}
- habe die Söhne v (links), w (rechts)
- mit den Marken (av,bv) und (aw,bw)
- dann wird der Wert des dem Knoten u entsprechenden Teilausdrucks durch berechnet durch
val(u) = (av·val(v)+bv) £ (aw·val(w)+bw) gegeben
- sei u innerer Knoten
- Vorgehen
- es sei "v Î V: Marke(1,0)
- // Invariante I gilt (trivial)
- durch Baumkontraktion soll der Baum T zum drei-Knoten-Baum T' reduziert werden
- dabei soll gelten: val(T') := val(T)
- es sei v ein linkes Blatt mit
- dem Bruder w
- dem Wert cv
- dem Vater u mit dem Operator £Î{+, · }
- bei der Anwendung der Rake-Operation auf v
- werden v und u entfernt
- Þ ihr Beitrag zum Teilausdruck des Teilbaums muss in den Werten (aw, bw)
der Marke von w gespeichert werden
- Þ der Wert von u ist gegeben als val(u) = (avcv + bv) £ (awX+bw)
- X = unbekannter Wert des Knoten w
- cv = Wert des Blattes v
- Þ Beitrag des Wertes von u zu seinem Vater ist:
E = auvalu + bu - für linksrake
- im Falle, dass £u = "+":
- E = au[(avcv+bv)+ (awX+bw)] + bu
- E = au(avcv+bv) + au(awX+bw) + bu
- E = au(avcv+bv) + auawX+aubw + bu
- E = auawX+au(avcv+bv+bw) + bu
- Þ ist linear in X
- da v und u entfernt werden, muss dieser Beitrag zur Marke von w geschrieben werden:
- aw' := auaw
- bw' := au(avcv+bv+bw) + bu
- im Falle, dass £u = "·":
- E = au[(avcv+bv) · (awX+bw)] + bu
- E = au(avcv+bv)awX + au(avcv+bv)bw + bu
- Þ ist linear in x
- da v und u entfernt werden, muss dieser Beitrag zur Marke von w geschrieben werden:
- aw' := au(avcv+bv)aw
- bw' := au(avcv+bv)bw + bu
- im Falle, dass £u = "+":
- für rechtsrake müssen entsprechend w und v vertauscht werden
- es sei "v Î V: Marke(1,0)
- Þ Für einen gegebenen Baum T über einem arithmetischen Ausdruck
kann die Berechnung mittels Baumkontraktion in O(log n) Zeit und O(n) Work ausgeführt werden
- Beispiel:
Ausgangsbaum
Ausschnitt, entfernen des markierten Bereichs mit Rake- Invariante (I):
- Sei u innerer Knoten
- Marken (av, bv), (aw, bw)
- val(u) = (av val (v) + bv) £ (aw val(w)+bw)
£ = +
*
- Was liefert u an p(u) ?
- offenbar E=av val(u)+bu
- Was ist val(u) ?
- val(u) = av cv + bc + (awX+bw)
- cv seien die Konstanten Werte
- X = unbekannter Wert (noch nicht berechneter Wert des Teilbaums)
- E = au((avcv+bb)+(awX+bw))+bu
=au(avcv+bv)+auawX+bu - =auawX+[au(avcv+bv+bw)+bu]=aw'X+bw'
- gilt für Links-Rake bei Rechtsrake müssen v und w vertauscht werden
- im Beispiel:
- w=-5
- aw'=auaw=1·1=1
- bw' = au(avcv+bv)+bu = 1(1·2+0}+0 = 2
man beachte die Markierungen am Knoten 3!
- ...
- Auswertung: (4*4+14)+20
- ...
- wir ordnen jedem Knoten v eine Marke (av,bv) zu
Minimum bei nichtbalancierten Bäumen ohne Ordnung- Sei (U,£) eine kommutative Halbgruppe mit einem Identitäts-Element e
Beispiel 1: U@natürliche Zahlen
£ = *
e = 1
"xÎ\int : x*1 = xBeispiel 2: U@natürliche Zahlen
£ = +
e = 0
"xÎ\int : x+0 = xBeispiel 3: U@natürliche Zahlen,
£ = min,
e = +&infin
"xÎ\int : min(x,∞) = x
- beliebiger Baum T=(V,E)
- Knoten v sollen Werte l(v) aus U enthalten
- gesucht ist für alle Knoten v das Minimum aller Werte des Teilbaums mit Wurzel v
- Vorgehen:
- Umformen in einen Binärbaum
- 4': Knoten, der nicht gezählt wird
- Wert +∞
- Satz
- gegeben sei T=(V,E)
- U geordnete Menge
- Operation £ = Min
- Kanten seien mit Elementen von U markiert
- Dann kann das Minimumm aller Knoten analog zur
Auswertung arithmetischer Ausdrücke berechnet werden- in O(log n) TIME (auch für lineare Bäume)
- mit O(n) WORK
- Sei (U,£) eine kommutative Halbgruppe mit einem Identitäts-Element e