A binary-search tree that provides “smaller-than-X counting”.

Question:

Let’s say we have several numbers. Is it possible to figure out the following tasks in O(nlogn) running time:

a) how many of them are smaller than a new number?

b) insert the new number into the group?

Idea:

1) sorted array + binary search can do that. But the inserting job would take O(n) in that way.

2) binary-search tree can do b). But it can’t do a).

Analysis:

(1) doesn’t seem to be a possible solution though. Let’s focus on 2).

Let’s think about how the insertion to be done in a binary tree: in an insertion, the inserting node reach its position by going from the root all the way down to the leaf. On the way, it compares to each node and picks the left or right path according to the result of the comparison. The number of comparisons along with the insertion is O(logn).

Maybe we can put something on the nodes to help us out in task 1).

Assume we are inserting a number 3 into the B-S tree. Let’s simulate the process of insertion.

step 1: 3 > root ? take the right path : the left path.

It seems like if 3 > root, then nodes[left_subtree] < root < 3. We can prove it by: a) all the nodes of the left subtree are put there by insertion; b) they all have been compared to root and are smaller than root.

Similarly, if 3 < root, then 3 < root < nodes[right_subtree].

This is a very useful information. If we think of the problem recursively, then

total_smaller_num_count

= smaller_node_count_in_tree(root, 3)

= left_subtree_node_count + 1 + smaller_node_count_in_tree(rightChild), if 3 > root.

= smaller_node_count_in_tree(leftChild), if 3 < root.

With this rough formula, we are now sure that task 1) can also be done with a binary-search tree in O(nlogn).

Pseudocode:

Insertion(root, num, smaller_count)

if num is larger than root’s num

smaller_count += left_node_count[root] + 1;

if right_node[root] is null

attach num to right_node[root].

else

Insertion(right_node[root], num, smaller_count);

right_node_count[root] += 1;

else

if left_node[root] is null

attach num to left_node[root];

else

Insertion(left_node[root], num, smaller_count);

left_node_count[root] +=1;