Zip trees

This talk will present the zip tree, a simple and efficient type of binary search tree.  Zip trees use randomization to achieve balance.  A zip tree can be viewed as a binary-tree representation of a skip list or as a variant of a treap.  Insertion and deletion avoid the multiplicity of cases that arise in standard balanced trees.  Zip trees can be adapted to exploit biased access distributions.  Their simplicity makes them promising for concurrent use.