Zip Trees
> insertion and deletion can be done purely top-down, with O(1) expected restructuring time and exponentially infrequent occurrences of expensive restructuring. Certain kinds of deterministic balanced search trees, in particular weak AVL trees and red-black trees achieve these bounds in the amortized sense [3], but at the cost of somewhat complicated update algorithms.<p>It's a neat, novel data structure with O(1) typical insert and delete times. Very cool!