This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 58

Search in a randomized BST

Due: March 8
Points: 1

A randomized BST is a data structure for the dictionary ADT that should support three operations: search, insert, and delete. But in class we only talked about how insertion works in a randomized BST.

Come up with a way to do search, to guarantee an expected time performance that is the same as a balanced binary search tree like AVL or 2-3 trees.