Amortisierte Kostenanalyse der Splay-Operation Amortisierte Kostenanalyse

Jeder Knoten habe Gewicht w(x) > 0. Gewicht tw(x) des Unterbaums mit Wurzel x ist: $\sum_y{\text{w}(y)}$ ($\forall y$ im Unterbaum mit Wurzel x)

Rang r$(x) = \log($tw(x))
Potential eines Baumes T: $\sum\limits_{x \in T}{\text{r}(x)}$

Lemma: Sei T ein Splay-Tree mit Wurzel u, x ein Knoten in T. Die amortisierten Kosten für Splay(x, T) sind $\leq 1 + 3(\text{r}(u) - \text{r}(x)) = \mathcal{O}\left(\log\frac{\text{tw}(u)}{\text{tw}(x)}\right)$.

Beweis: Induktion über die Folge von (Doppel)Rotationen:
Berechne r und r', tw und tw', die Rang- bzw. Gewichtsfunktion vor und nach dem Rotationsschritt. Wir zeigen, daß die amortisierten Kosten im Fall 1 (zig) $\leq 1 + 3(\text{r}'(x) - \text{r}(x))$ und in den Fällen 2 und 3 (zig-zig bzw. zig-zag) $\leq 3(\text{r}'(x) - \text{r}(x))$ sind. y sei der Vater von x, z der Großvater (falls er existiert).

1.

Fall:

amortisierte Kosten:

$$\begin{split} &\leq 1 + \text{r}'(x) + \text{r}'(y) - \text... ...text{r}(x))\text{,\quad da r}'(x) \geq \text{r}(x) \end{split}$$

2.

Fall:

amortisierte Kosten:

$$\begin{split} &\leq 2+\text{r}'(x)+\text{r}'(y)+\text{r}'(z... ...)\geq \text{r}'(y)\text{ und r}(y)\geq\text{r}(x) \end{split}$$

Es gilt, daß

$$\begin{split} &2+\text{r}'(x)+\text{r}'(z)-2\text{r}(x)\leq 3(\text{r}'(x)-\text{r}(x)) \end{split}$$

d.h.

$$\begin{split} &2\text{r}'(x)-\text{r}(x)-\text{r}'(z)\geq 2 \end{split}$$

Betrachte dazu die Funktion

$$\begin{split} \text{f}(x,y)=\log(x)+\log(y) \end{split}$$

auf dem Bereich

$$\begin{split} x,y\gt,\ x+y\leq 1 \end{split}$$

$\parbox{90mm}{ \textbf{Behauptung:} $\text{f}(x,y)$\space nimmt ihr eindeutiges Maximum im Punkt $\left(\frac{1}{2}, \frac{1}{2}\right)$\space an. }$

Beweis: Da die Funktion z $\to \log(z)$ streng monoton wachsend ist, kann sich das Maximum der Funktion f$(x,y)=\log(x)+\log(y)$ nur auf dem Geradensegment x+y=1, x,y>0 befinden. Dadurch erhalten wir ein neues Maximierungsproblem für die Funktion g$(x)=\log(x)+\log(1-x)$ auf diesem Geradensegment. Da g(x) an den Rändern gegen $-\infty$ strebt, muß es sich um ein lokales Maximum handeln. Die einzige Nullstelle der Ableitung

$$\text{g}'(x) = \frac{1}{\ln a}\left(\frac{1}{x} - \frac{1}{1-x}\right),$$

wenn $\log=\log_a$, ist x=0.5 (unabhängig von a). Weiter ist

$$\text{g}''(x) = -\frac{1}{\ln a}\left(\frac{1}{x^2}+\frac{1}{(1-x)^2}\right).$$

Da g''(0.5) < 0 ist, nimmt g(x) in x=0.5 sein globales Maximum an. Insgesamt folgt, daß die Funktion f$(x,y)=\log(x)+\log(y)$ ihr globales Maximum im Bereich x,y>0, $x+y\le 1$ an der Stelle (0.5,0.5) annimmt. $\Diamond$

Damit gilt:

$$\begin{split} \text{r}(x)+\text{r}'(z)-2\text{r}'(x)=\log\l... ...frac{\text{tw}'(z)}{\text{tw}'(x)}\right) \leq -2 \end{split}$$

da

$$\begin{split} \text{tw}(x)+\text{tw}'(z)\leq \text{tw}'(x) \end{split}$$

3.

Fall:

amortisierte Kosten:

$$\begin{split} &\leq 2 + \text{r}'(x) + \text{r}'(y) + \text{... ...Behauptung \uml {u}ber f}(x,y)\text{ wie im Fall 2.}\end{split}$$

Die Gesamtbehauptung des Lemmas folgt dann durch Aufaddieren der amortisierten Kosten für die einzelnen Schritte (Beachte: Teleskop-Summe). $\Diamond$

Sei T ein Splay-Tree mit n Knoten. Die Verringerung des Potentials durch eine Folge von Splay-Operationen $(\text{splay}(x_j,T))_{j=1..n}$,falls sich die Gewichte nicht ändern, beschränkt sich durch

$$\begin{split} \sum_{i=1}^{n}(\log{W}-\log{w_i}) =\sum_{i=1}... ...w_i \quad\quad w_i = \text{Gewicht von } x_i.\\ \\ \end{split}$$

Beweis:
amortisierte Kosten = reelle + $\Delta_{\text{balance}}$; reelle Kosten = amortisierte - $\Delta_{\text{balance}}$.Wähle $w_i = \frac{1}{n}$ für alle Knoten. $\Rightarrow$ amortisierte Kosten für einen Zugriff $\leq 1 + 3 \log n$, da $W = \sum\limits_{i=1}^n w_i= 1$. Die Verringerung im Potential ist $\leq \sum\limits_{i=1}^n\log\frac{W}{w_i} = \sum\limits_{i=1}^n\log n = n \log n$. $\Rightarrow$ reelle Kosten $\leq m(1 + 3 \log n) + n \log n$. $\Diamond$



Beweis: Setze Gewicht des i-ten Knotens gleich $\frac{\text{q}(i)}{m}$.

$$\begin{split} \Rightarrow \text{W}=\sum_{i=1}^{n}\frac{\text{q}(i)}{m}=1 \quad \text{ ; Rest wie oben.} \end{split}$$

$\Diamond$



Beweis: Sei U die Menge, d die Tiefe eines (fest gewählten) optionalen statischen Suchbaumes, sei für $x\in U$ , d(x) die Tiefe von x in diesem Suchbaum. Definiere:
$tw(x):=3^{d-d(x)}. \text{ Sei } T \text{ ein beliebiges Splay-Tree f\uml {u}r } U:$

$$\begin{split} bal(T) \leq \sum_{x\in U} r(x) & = \sum_{x \i... ... = \mathcal{O}(n^2); \quad \quad n=\vert U\vert\\ \end{split}$$

$$\begin{split} & \sum_{x \in U}tw(x) = \sum_{x \in U}3^{d-d(... ... \log \frac{3^{d+1}}{3^{d-d(x)}}=\log 3^{d(x)+1}. \end{split}$$

Damit ergibt sich für die amortisierte Kosten für Splay(x,T):
$\mathcal{O}(\log\frac{tw(T)}{tw(x)}) = \mathcal{O}(d(x)+1)$.
Damit sind die amortisierten Kosten $\leq c.$ Zugriffskosten (# Vergleiche) im optimalen Suchbaum (wo sie d(x)+1 sind). Die gesamten amortisierten Kosten für die Zugriffsfolge sind daher $\leq c.t$.
Damit sind reelle Kosten $\leq a.$Kosten + Verringerung des Potentials = $\mathcal{O}(t+n^2)$.
$\Diamond$