[Home | Assignments | Links | Grades | CIS 313]

CIS 323 - Assignment 3

Left-leaning red-black trees

Due Thursday, February 18, 2010

Description

You can write your code in any programming language for this assignment — except Java!.

The goal of the assignment is to get more familiar with a modern version of the red-black tree data structure, called left-leaning red-black trees.

Problem description

Imagine that we have a large database consisting of n distinct numbers. Each number corresponds to a unique score that has been assigned to a student according to how well the student performs in school. All scores are positive integers.

At the end of the school year, the university assigns a score to each student and sends an email to the student, telling what score he or she got.

The list of scores is a big, long unordered list of numbers and associated student names so the university wants to order the names according to increasing score. Fortunately, someone has heard that balanced binary search trees (such as a left-leaning red-black tree) can be used to maintain an ordered list so they decide to put the numbers into a balanced tree but do not implement it yet.

Now, a student wonders how well his or her score ranks among all scores in the university. The student walks into the office and says:

I have the score k, where does this score rank in the system?

The office secretary thinks a little bit and says:

We are planning to have an ordered list of scores but, hmm, even though my list of scores is sorted, I still have to potentially search through all n numbers to find out what your rank is. What is the point of having a sorted list then?

The student, being a computer science major, gives the office secretary a copy of Introduction to Algorithms and asks her to read section 14.1 about finding the rank of a given key in a red-black tree in O(lg n) time, using order statistics. The office secretary nods and says:

Well, smart guy, why don't you just implement the entire system for us then?

You are the computer science student in this story. Good luck :-)

Task

According to the above description, you should:

Implement a left-leaning red-black tree data structure with an O(lg n) insert operation.
Implement an O(lg n) algorithm that can find the rank of a given key k in the tree. A rank i for key k means that k is the ith largest score. Rank 1 thus correspond to the highest score and rank n is the lowest. The time constraint is important. Do NOT just use a tree walk!
You should conform to the input/output specification given further down.

You can find the implementation of the left-leaning red-black tree in the slides I posted for week 5. Of course, you will have to translate this into what ever language you choose for your implementation (remember, not Java!).

You can find a way to find a rank in O(lg n) time in section 14.1 of the book.

Input/Output

The input will be formatted in the following way:

A non-negative integer n on its own line representing the number of scores to be inserted into your balanced tree.
n lines consisting of a score to insert and the name of the student with that score, separated by a whitespace. For simplicity, you can assume that a name is only one word.
A non-negative integer m on its own line representing the number of students that are eager to know their rank.
The m scores to find — each on their own line.

You may assume that no duplicate scores will be inserted and a test case on the order of 100000+ score insertions (yes, it is a big university) plus at least 50000+ rank searches will be used to evaluate your program.

Here is an example:

Input:

7
20 Bashful
30 Doc
50 Dopey
5 Grumpy
300 Happy
10 Sleepy
8 Sneezy
3
20
50
8

Output

The output is based on what the office secretary would say to the student asking for his or her rank. In the above case, Grumpy has rank 7, because he has the lowest score, Sneezy has rank 6, Sleepy rank 5 and so on. The correct output for the above example is shown below

Bashful, you have rank 4

Dopey, you have rank 2

Sneezy, you have rank 6

Hint: Since you have to print out the name but you are only given the score, it seems that you will have to find the score in your tree first and then start calculating the rank.

You should conform exactly to the input and output specification, as I will be using massive test cases and checking your output against the correct output. Just like last time.

Testcases

While implementing the LLRB, you can use the testcase generator from assignment 2. First, you will just have to worry about creating a correct tree.

When you are ready to test with names, you can use the inputs found here.

What to turn in

Your implementation of the left-leaning red-black tree and the order-statistics algorithms that works on this tree and conforms with the input/output specification.