110 bstree

Binary search tree, the ‘hello world’ data structure

Liu Xinyu *

Draft in August 5, 2009, Updated in April 19, 2011

The PDF version.

1 Introduction


It’s typically considered that Arrays or Lists are the ‘hello world’ data structure. However, we’ll see they are not so easy to implement actually. In some procedural settings, Arrays are the elementary representation, and it is possible to realize linked list by array (section 10.3 in [1]); While in some functional settings, Linked list are the elementary bricks to build arrays and other data structures.

Considering these factors, we start with Binary Search Tree (or BST) as the ‘hello world’ data structure. Jon Bentley mentioned an interesting problem in ‘programming pearls’ [2]. The problem is about to count the number of times each word occurs in a big text. And the solution is something like the below C++ code.

 
int main(intchar** ){ 
   map <string, int>  dict; 
  string s; 
  while(cin>>s) 
     ++dict[s]; 
   map <string, int>::iterator it=dict.begin(); 
  for(; it!=dict.end();  ++it) 
    cout<<it->first<< ”:_” <<it-> second<<\n”; 
}

And we can run it to produce the word counting result as the following.

$ g++ wordcount.cpp -o wordcount  
$ cat bbe.txt | ./wordcount > wc.txt

The map provided in standard template library is a kind of balanced binary search tree with augmented data. Here we use the word in the text as the key and the number of occurence as the augmented data. This program is fast, and it reflects the power of binary search tree. We’ll introduce how to implement BST in this post and show how to solve the balancing problem in later post.

Before we dive into binary search tree. Let’s first introduce about the more general binary tree.

The concept of Binary tree is a recursive definition. Binary search tree is just a special type of binary tree. The Binary tree is typically defined as the following.

A binary tree is

  • either an empty node;
  • or a node contains 3 parts, a value, a left child which is a binary tree and a right child which is also a binary tree.
Figure 1 shows this concept and an example binary tree.
Figure 1: Binary tree concept and an example.


A binary search tree is a binary tree which satisfies the below criteria. for each node in binary search tree,

  • all the values in left child tree is less than the value of of this node;
  • the value of this node is less than any values in its right child tree.
Figure 2 shows an example of binary search tree. Compare with Figure 1 we can see the difference about the key ordering between them.

Figure 2: A Binary search tree example.

Read the PDF file for the complete version.
Č
Ċ
ď
Xinyu LIU,
2011年5月25日 下午7:25
ċ
ď
bstree.zip
(9k)
Xinyu LIU,
2011年4月19日 上午12:46
Comments