Binary Search Trees

Binary search tree is one of the most often used data structure in computer science. It seems that computer science people like asking about BST and its algorithms in job interviews. The following are advantages of binary search trees (summarized from here):

  • binary trees are memory-efficient; they do not reserve more memory than they need to
  • BST have simpler behavior and do not tend to suddenly allocate a lot of data and do a rehashing operation (compare to hash-table e.g.)
  • you can iterate through the contents of the tree in sorted order
  • you can find the element closest to (not necessarily equal to) some arbitrary key value (or closest above/below)
  • binary search tree can be implemented with a persistent interface, where a new tree is returned but the old tree continues to exist
  • BST tend to be the ultimate average data structure. They can act as lists, can easily be split for parallel operation, have fast removal, insertion and lookup on the order of O(lg n). They do nothing particularly well, but they don’t have any excessively bad behavior either.

Here is the C implementation taken from Robert Sedgewick’s book:

static struct node
{int key, info; struct node *l, *r;}
static struct node *t, *head, *z;

int treesearch(int v){
struct node *x = head->r;
z->key = v;
while(v != x->key){
    x = (v < x->key) ? x->l : x->r;
}
return x->info;
}

This code assumes binary search tree are given to us; head->r points to the root of the tree (this not shown in the code). Head is not used so far.
Lets look at the initialization:

void treeinitialize(){
z = (struct node *) malloc(sizeof *z);
z->l = z; z->r = z; z->info = -1;
head = (struct node*) malloc(sizeof * head);
head->r = z; head->key = 0;
}

z node always points to itself and indicates the end of the tree. Empty tree is the one whose head points to node z; non-empty tree will have head->r pointing at its root.
Lets look at the insertion; node p keeps track of the parent of the current node.

void treeinsert(int v, int info){
struct node *p, *x;
p = head; x = head->r; // x is root node now
while(x != z)
    {p = x; x = (v < x->key) ? x->l : x->r;}
x = (struct node *) malloc(sizeof *x);
x->key = v; x->info = info; x->l = z; x->r = z;
if(v < p->key) p->l = x; else p->r = x;
}

Traversing the tree in order:

void treeprint(){
    treeprintr(head->r); // starting recursion from the root of the tree
}
void treeprintr(){
if(x!=z){
treeprintr(x->l);
printnode(x);
treeprint(x->r);
}

The logic behind the traversing the tree in the code above is the following.
You move to the left until the end. Print the smallest node. Then step to the right and again traverse the left branch of the tree until the end; print the node; step to the right and traverse stepping to the left and so on :).
To be continued 🙂

Advertisements
This entry was posted in C++, Interview, Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s