Problem 47

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Deletion from a randomized BST

Due: March 1
Points: 3

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 deletion, to guarantee an expected time performance that is the same as a balanced binary search tree like AVL or 2-3 trees.