Augmented Binary Search Trees

Question

Given an unsorted set of n distinct numbers, suppose we are interested in carrying out the following two operations:

• Select the element of rank k. This operation will be carried out 1 ≤ m ≤ n times.

• Insert a new element into the set. This operation will be carried out 1 ≤ p ≤ n times.

The order of the above operations is not known. There are three specific ways to solve this problem:

1. Using an augmented binary search tree
2. Using a Select algorithm
3. A simple sort of the input.

For each approach, describe how to solve the above two operations and provide the overall runtime.

Using the results, decide which method you should use when:

• p = m = Θ(log n)

• p = 4, m = n

• m = 2, p = n

• m = p = n.

Answer 1

1. If you expect both many inserts and many selections:

Use the balanced tree. It keeps things efficient for both tasks.

1. If you expect many inserts but very few selects:

Keep things simple by storing data in a list and find elements when needed with a selection algorithm.

1. If you expect many selects but very few inserts:

Sort once and then quickly pick elements by their position. Insertions are rare, so it’s okay if they take longer.