BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Treaps - Power and Simplicity of Randomisation - Kuba Bachurski\, 
 Trinity College
DTSTART:20220309T193000Z
DTEND:20220309T200000Z
UID:TALK171533@talks.cam.ac.uk
CONTACT:Matthew Ireland
DESCRIPTION:Every computer scientist is familiar with binary search trees.
  They are widely applicable structures\, and there are countless ways of m
 aking them efficient. We do this by making them balanced - for example\, r
 ed-black trees enforce strict rules and fix them with tree rotations based
  on case analysis. Treaps are a BST too\, but they take a different approa
 ch\, which we'll interpret geometrically\, leaving us with a couple of sim
 ple cases. What's interesting is that treaps use randomness to balance the
  tree. Equipped with them we'll be able to design a data structure for per
 forming efficient string operations\, used in text editors or for solving 
 dynamic connectivity problems.
LOCATION:Wolfson Hall\, Churchill College
END:VEVENT
END:VCALENDAR