DS Final Cheat Sheet (DRAFT) by adman

function Splay(node x, root r): if x == null or r == null: return r while x is not the root: if x is a child of the root: # Zig case if x is the left child: perform right rotation on the root else: perform left rotation on the root else: parent = parent(x) grandp­arent = parent­(pa­ren­t(x)) if x and parent are both left children (or both right children): # Zig-Zig case if x is a left child: perform right rotation on grandp­arent perform right rotation on parent else: perform left rotation on grandp­arent perform left rotation on parent else: # Zig-Zag case if x is a left child: perform right rotation on parent perform left rotation on grandp­arent else: perform left rotation on parent perform right rotation on grandp­arent return x # x is now the root

function Splay(node x, root r): if x == null or r == null: return r while x is not the root: if x is a child of the root: # Zig case if x is the left child: perform right rotation on the root else: perform left rotation on the root else: parent = parent(x) grandp­arent = parent­(pa­ren­t(x)) if x and parent are both left children (or both right children): # Zig-Zig case if x is a left child: perform right rotation on grandp­arent perform right rotation on parent else: perform left rotation on grandp­arent perform left rotation on parent else: # Zig-Zag case if x is a left child: perform right rotation on parent perform left rotation on grandp­arent else: perform left rotation on parent perform right rotation on grandp­arent return x # x is now the root