Upcoming Talks

Ist logo

Zip trees

Date: Monday, October 02, 2017 16:00 - 17:00
Speaker: Robert Tarjan (Princeton University)
Location: Raiffeisen Lecture Hall, Central Building
Series: Institute colloquium
Host: GSO
Contact: ZARUBA Katharina
Central building lecture hall

Abstract:

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.

Qr image
Download ICS Download invitation
Back to eventlist