Next: Amortisierte Kostenanalyse der Splay-Operation
Up: Splay-Trees als Suchbäume
Previous: Einleitung
Ein Knoten, auf den zugegriffen wird (Splay(x,T)), wird durch eine Folge von einfachen und doppelten Rotationen
an die Wurzel bewegt.
Fälle:
- 1.
- (zig): x ist Kind der Wurzel von T: einfache Rotation
- 2.
- (zig-zig): x hat Großvater g(x) (und Vater p(x)) und x und p(x) sind
jeweils linke (bzw. rechte) Kinder ihres Vaters.
- 3.
- (zig-zag): x hat Großvater g(x) und Vater p(x), x ist linkes (rechtes)
Kind von p(x), p(x) ist rechtes (linkes) Kind von g(x).
Übung: (Splaying-Operation mit dem eingekreisten Element durchführen)
Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999
![\begin{picture}
(82.5,28.5)
\put(0,0){\line(2,3){5}}
\put(0,0){\line(1,0){10...
...,24.5){\makebox(5,5)[b]{$x$}}
\put(72,13.5){\makebox(3,5)[l]{$y$}}\end{picture}](img337.gif)
![\begin{picture}
(115,37)
\put(7.5,0){\line(2,3){5}}
\put(7.5,0){\line(1,0){10...
...put(102.5,15){\circle*{2}}
\put(104.5,13.5){\makebox(3,5)[l]{$z$}}\end{picture}](img341.gif)
![\begin{picture}
(87,40)
\put(15,0){\circle*{1.4}}
\put(15,0){\line(-1,1){5}}
...
...{\makebox(3,5)[r]{3)zigzag}}
\put(100,17){\makebox(3,5)[r]{4)zig}}\end{picture}](img342.gif)