Wörterbuchoperationen in Splay-Trees

Betrachte (Alle diese Operationen werden mit Hilfe von Splay implementiert):

• Access(i, T) : $\surd$ (Haben wir bereits)
• Join(T₁, T₂) :

  
  
  
  beachte $x \in T_1,\ y \in T_2$, dann gilt x<y

• Split(i, T) :

  
  
  

• Insert(i, T) :

  
  
  

• Delete(i, T) :

  
  
  

Definition: Sei $i \in U$; T ein Splay-Tree. Dann bezeichnen wir mit i- (bzw. i+) den Vorgänger (bzw. den Nachfolger) von i in der gegebenen Ordnung in T (falls diese existieren). Falls i- bzw. i+ undefiniert sind, so setzen wir w$(i-)=\infty$ bzw. w$(i+)=\infty$. Weiterhin sei W das Gesamtgewicht aller an einer Wörterbuch-Operation beteiligten Knoten.