Zip trees
Date
Monday, October 2, 2017 16:00 - 17:00
Speaker
Robert Tarjan (Princeton University)
Location
Raiffeisen Lecture Hall, Central Building
Series
Colloquium
Tags
Institute Colloquium
Host
GSO
Contact
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.