Introduction to Random Binary Search Trees

Learn how to improve the efficiency of Binary Search Trees using randomization.

We'll cover the following

Here, we present a binary search tree structure that uses randomization to achieve O(logn)O(\log n) expected time for all operations.

Consider the two binary search trees shown in the figure below, each of which has n=15n = 15 nodes.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy