python implementation although the mathematical analysis of splay tree' performance is complex (see section )the implementation of splay trees is rather simple adaptation to standard binary search tree code fragment provides complete implementation of splaytreemap classbased upon the underlying treemap class and use of the balancing framework described in section it is important to note that our original treemap class makes calls to the rebalance access methodnot just from within the getitem methodbut also during setitem when modifying the value associated with an existing keyand after any map operations that result in failed search class splaytreemap(treemap) """sorted map implementation using splay tree "" splay operation def splay(selfp) while !self root) parent self parent( grand self parent(parent if grand is none zig case self rotate( elif (parent =self left(grand)=( =self left(parent)) zig-zig case move parent up self rotate(parentthen move up self rotate( else zig-zag case move up self rotate(pmove up again self rotate( override balancing hooks def rebalance insert(selfp) self splay( def rebalance delete(selfp) if is not none self splay( def rebalance access(selfp) self splay(pcode fragment complete implementation of the splaytreemap class