Introduction to Random Binary Search Trees

Learn how to improve efficiency of Binary Search Tree using randomization.

We'll cover the following

Here, we’ll 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 below in figure, 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