Sich selbst organisierende Binary Keys

Next: Splay-Trees als Suchbäume Up: Sich selbst organisierende lineare Previous: Sich selbst organisierende lineare

Sich selbst organisierende Binary Keys

Priority Queue
Variante von Leftist-Bäumen [s.Knuth]: Ein Leftist-Baum ist ein (interner) binärer Suchbaum, so daß für jeden der Knoten gilt, daß ein kürzester Weg zu einem Blatt über das rechte Kind führt.

Wir wollen folgende Operationen unterstützen:

$\left. \begin{array} {l} \text{- \textsl{\textsf{Insert}} } \\ \text{- \... ...{\textsf{Delete}} } \\ \text{- \textsl{\textsf{Merge}} }\end{array} \right\}$ alle Operationen lassen sich auf Merge zurückführen

Operationen:

1.: Insert(T,x) : neuer Baum mit x als Element, merge diesen mit T
2.: FindMin : $\surd$ (Minimum an der Wurzel, wegen Heap-Bedingung)
3.: DeleteMin :

$\begin{picture} (76,25) \put(0,0){\line(1,0){10}} \put(5,10){\line(-1,-2){5}} \p... ...,5){$T_2$}} \put(57,15){\makebox(0,0){merge $T_1$\space und $T_2$}}\end{picture}$
4.: Delete :

$\begin{picture} (70,45) \put(0,0){\line(1,0){10}} \put(5,10){\line(-1,-2){5}} \p... ...5,10){\line(1,0){20}} \put(52.5,5){\makebox(0,0){merge$(T_1,T_2$)}}\end{picture}$
5.: Merge : Seien zwei Heaps H₁ und H₂ gegeben, seien a₁,..,a_r₁ die Folge der Knoten in H₁ von der Wurzel zum rechtesten Blatt, sei b₁,..,b_r₂ die entsprechende Folge in H₂.

$\begin{picture} (125,55) \put(5,48){\makebox(10,5){$H_1$}} \put(15,43){\circle*{... ...,-1){10}{\circle*{0.1}} \multiput(105,13)(-1,-1){10}{\circle*{0.1}}\end{picture}$
Sei c₁,c₂,..,c_r₁+r₂ die durch Merging aus (a₁,..,a_r₁) und (b₁,..,b_r₂) entstehende (sortierte) Folge. Mache (c₁,..,c_r₁+r₂) zum linkesten Pfad im neuen Baum und hänge den jeweiligen anderen (d.h. linken) UB a_i bzw. b_j als rechten UB des entsprechenden c_i an.

Beispiel:

$\begin{picture} (153,73) \put(2.5,15){ \framebox (5,5){}} \put(17.5,15){ \frame... ...,1){10}} \put(120,50){\line(1,1){10}} \put(145,50){\line(-1,1){10}}\end{picture}$

$\begin{picture} (90,75) \put(32.5,7.5){\circle{7}} \put(30,5){\makebox(5,5){$6$}... ...,55){\line(-1,2){5}} \put(0,35){\makebox(20,5){\Huge$\Rightarrow$}}\end{picture}$

Amortisierte Kostenanalyse der Merge -Operation:

Sei w(x): = Gewicht von x = # Knoten im UB von x (einschließlich x)

$\begin{picture} (75,32) \put(37,27){\line(-2,-3){10}} \put(37,27){\line(2,-3){10... ...kebox(0,0){$ (x,y)$\space schwer $\Rightarrow (x,z)$\space leicht}}\end{picture}$

$\textstyle\parbox{70mm}{ Kante($x,y$) hei\ss{}t leicht, falls $2.w(y) \le w(x)$\\ Kante($x,y$) hei\ss{}t schwer, sonst }$

Es gilt: Es ist immer ein Kind über leichte, eins über schwere Kante erreichbar.

Beobachtungen:

1.: (x,y) schwer $\Rightarrow (x,z)$ leicht
2.: Da sich über eine leichte Kante das Gewicht mindestens halbiert, kann ein Pfad von der Wurzel zu einem Blatt höchstens $\log n$ leichte Kanten enthalten.

Potential: # schwere Kanten zu rechten Kindern

$\begin{picture} (170,85) \put(15,79){\makebox(0,0){$H_1$}} \put(15,72){\makebox(... ...,19){\vector(4,-1){36}} \put(108,14){\makebox(0,0){schwere Kanten}}\end{picture}$

s₁:= # schwere Kanten auf den rechten Pfad. s₂:= Analog.

$r_1 \leq s_1 + \log n_1$
$r_2 \leq s_2 + \log n_2$

Amortisierte Kosten für Merge:

$\begin{displaymath} \begin{split} & \leq r_1 + r_2 + \log(n_1+n_2) -s_1 - s_2\\... ...2 + \log (n_1+n_2)\\ & = \mathcal{O}(\log(n_1+n_2))\end{split}\end{displaymath}$

$% latex2html id marker 7976 \fbox {\parbox[c]{12.45cm}{\textbf{Satz:} Eine Folge... ...o}\ss{}e des Baumes ist, der in der $i$-ten merge-Operation geschaffen wird. }}$

Next: Splay-Trees als Suchbäume Up: Sich selbst organisierende lineare Previous: Sich selbst organisierende lineare

Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999