120 rbtree

Red-black tree, not so complex as it was thought

1 Introduction

1.1 Exploit the binary search tree

We have shown the power of binary search tree by using it to count the occurrence of every word in Bible. The idea is to use binary search tree as a dictionary for counting.

One may come to the idea that to feed a yellow page book 1 to a binary search tree, and use it to look up the phone number for a contact.

By modifying a bit of the program for word occurrence counting yields the following code.

int main(int, char** ){ 
  ifstream f(”yp.txt”); 
   map <string, string>  dict; 
  string name, phone; 
  while(f>> name  &&  f>> phone) 
    cout<<\ nname: ”; 
    cin>> name; 
    if(dict.find(name )==dict.end()) 
      cout<<”not found”; 
      cout<<”phone:  ”<<dict[name]; 

This program works well. However, if you replace the STL map with the binary search tree as mentioned previously, the performance will be bad, especially when you search some names such as Zara, Zed, Zulu.

This is because the content of yellow page is typically listed in lexicographic order. Which means the name list is in increase order. If we try to insert a sequence of number 1, 2, 3, ..., n to a binary search tree. We will get a tree like in Figure 1.

Figure 1: unbalanced tree

This is a extreme unbalanced binary search tree. The looking up performs O(h) for a tree with height h. In balanced case, we benefit from binary search tree by O(lg N) search time. But in this extreme case, the search time downgraded to O(N). It’s no better than a normal link-list.

PDF version provides a better outlook for this chapter.
Xinyu LIU,
2011年6月1日 下午11:31
Xinyu LIU,
2011年6月1日 上午3:04