Binäre Bäume
Binäre Bäume
Definition
Definition
Binäre Bäume
Übliche Darstellung von Binärbäumen:
Bäume mit Wurzel, wobei jeder Knoten zwei oder keinen Knoten
als (geordnete) Nachfolger hat.
B : Menge der binären Bäume, rekursiv definiert durch die Regeln:
I
ist ein binärer Baum
I
sind t` , tr binäre Bäume, so ist auch t = h, t` , tr i ein binärer
Baum
I
nur das, was durch die beiden vorigen Regeln erzeugt werden
kann, ist ein binärer Baum
I
zwei Nachfolger: mit bezeichnete inneren Knoten,
I
kein Nachfolger: mit
(Blätter).
I
ist ein binärer Baum, der nur aus einem einzigen
(äusseren) Knoten besteht;
t = h, t` , tr i ist ein Baum mit Wurzel , an die zwei binäre
Bäume t` und tr als linker bzw. rechter Teilbaum angehängt
sind.
I
Binäre Bäume
bezeichneten äusseren Knoten
Binäre Bäume
Definition
Lineare Codierung
Lineare Codierung von Binärbbäumen
(Wörter über dem Alphabet { , })
Beispiel
t = !", t!, tr #
code( ) =
code(h, t` , tr i) = code(t` ) code(tr )
Entsprechend:
Generierung mittels einer kontextfreien Grammatik in BNF GB mit:
t!
tr
– Variablensymbol B (auch Startsymbol)
– Terminalsymbolen und – Produktionen
B→
BB
Binäre Bäume
Binäre Bäume
Lineare Codierung
Lineare Codierung
t = !", t!, tr #
Bemerkungen:
I
t!
code(t` ) = tr
∼ “linke Klammer”
∼
“rechte Klammer”,
so entsprechen diese Wörter genau den wohlgeformten
Klammerausdrücken entsprechender Länge.
,
code(tr ) = streicht man in jedem von GB erzeugten Wort das letzte
Symbol und identifiziert man
I
die von GB erzeugte Sprache ist kontextfrei, aber nicht regulär
code(t) = code(t` ) code(tr )
= Binäre Bäume
Binäre Bäume
Struktur und Anzahl
Notation
I
Struktur und Anzahl
I (t) : innere Knoten von t ∈ B (internal)
I
I
I
hat keine inneren Knoten
h, t` , tr i hat als innere Knoten die Wurzel , die inneren
Knoten von t` und die inneren Knoten von tr
E (t) : äussere Knoten (Blätter) von t ∈ B (external)
I
I
I
Struktur und Anzahl
hat als äusseren Knoten
h, t` , tr i hat als äussere Knoten die äusseren Knoten von t`
und die äusseren Knoten von tr
Bn : Menge der Binärbäume mit n inneren und n + 1 äusseren
Knoten
I
Strukturelle Aussage
B0 = { }
Bn+1 ↔ (B0 × Bn ) ∪ (B1 × Bn−1 ) ∪ (B2 × Bn−2 ) ∪ · · · ∪ (Bn × B0 )
]
=
Bk × Bn−k
0≤k≤n
Binäre Bäume
Binäre Bäume
Struktur und Anzahl
Einfache Parameter
Parameter für Binärbäume
I
I
i(t) = Anzahl der inneren (“internal”) Knoten von t:
(
0
falls t = i(t) =
1 + i(t` ) + i(tr ) falls t = h , t` , tr i
I
e(t) = Anzahl der äusseren (“external”) Knoten von t:
(
1
falls t = e(t) =
e(t` ) + e(tr ) falls t = h , t` , tr i
I
s(t) = i(t) + e(t) = Grösse (“size”) von t:
(
1
falls t = s(t) =
1 + s(t` ) + s(tr ) falls t = h , t` , tr i
Segners Formel
c0 = 1
cn+1 = c0 · cn + c1 · cn−1 + c2 · cn−2 + · · · + cn · c0
I
Catalans Formel
n 1
2n
4
cn =
∈Θ
n+1 n
n3/2
Binäre Bäume
Binäre Bäume
Einfache Parameter
I
Einfache Parameter
h(t) = Höhe (“height”) von t:
(
0
h(t) =
1 + max{h(t` ), h(tr )}
Beziehungen zwischen den Parametern
falls t = falls t = h , t` , tr i
Für alle binären Bäume t gelten folgende Aussagen:
I
e(t) = i(t) + 1, und damit s(t) = 2 · i(t) + 1 = 2 · e(t) − 1
Beweis:
t = !", t!, tr #
e( ) − i( ) = 1 − 0 = 1
e(h , t` , tr i) − i(h , t` , tr i) = e(t` ) + e(tr ) − (i(t` ) + i(tr ) + 1)
= e(t` ) − i(t` ) + e(tr ) − i(tr ) − 1
t!
tr
i(t) = 8, e(t) = 9, s(t) = 17, h(t) = 4
=1+1−1=1
Binäre Bäume
Binäre Bäume
Einfache Parameter
I
Einfache Parameter
I
h(t) ≤ i(t)
e(t) ≤ 2h(t) , also log e(t) ≤ h(t)
Beweis:
Beweis:
e( ) = 1 = 20 = 2h( )
h( ) = 0 = i( )
e(h , t` , tr i) = e(t` ) + e(tr )
h(h , t` , tr i) = 1 + max{h(t` ), h(tr )}
≤ 2h(t` ) + 2h(tr )
≤ 1 + max{i(t` ), i(tr )}
≤ 2 · 2max{h(t` ),h(tr )}
≤ 1 + i(t` ) + i(tr )
= 21+max{h(t` ),h(tr )}
= i(h , t` , tr i)
Binäre Bäume
= 2h(h , t` , tr i)
Binäre Bäume
Einfache Parameter
Weglänge
Höhe von Knoten
Innere und äussere Weglänge
I
I
Für a ∈ I (t) ∪ E (t) :
innere Weglänge von t :
wi (t) =
I
X
h(a, t)
a∈E (t)
I
) = 0
0
h(a, h , t` , tr i) = h(a, t` ) + 1
h(a, tr ) + 1
äussere Weglänge von t :
we (t) =
rekursive Beschreibung:
h( ,
h(a, t)
a∈I (t)
h(a, t) = Höhe von a in t = Abstand von a zur Wurzel von t
I
X
a= a ∈ E (t` ) ∪ I (t` )
a ∈ E (tr ) ∪ I (tr )
mittlere innere Weglänge von t :
w (t) =
I
wi (t)
i(t)
mittlere äussere Weglänge = mittlere Höhe :
h(t) =
we (t)
e(t)
Binäre Bäume
Weglänge
Beispiel
t = !", t!, tr #
t!
tr
wi(t) = 14, we(t) = 30, i(t) = 8, w(t) =
I
14 7
30 10
= , h(t) =
=
8
4
9
3
Allgemein gilt: we (t) = wi (t) + 2 i(t)
© Copyright 2024 ExpyDoc
