Binary Search Trees in C++ – 1 : search function

A binary search tree – BST is a binary tree with the following properties:

1. The data in the left child of a node is <= its own data.

2. The data in the right child of a node is >= its own data.

——-

We can easily see why it is called a binary search tree. Consider what happens if we try to search for a particular data entry. We compare the data entry with the data stored in the root of the BST. If they are equal, we are done. Else, if our target entry is less than the data contained in the root, we know that the target entry, if it exists in the tree, has to exist in the left subtree. Thus, we have eliminated the right subtree from further consideration. Analogous is the case when the target entry is greater than the data stored in the root. Thus, we can see that this is exactly the same as what happens when we try to search for an element in a sorted array using a binary search algorithm. Hence the name BST.

—————-

We first look at a recursive formulation of the search function.

———

struct Node

{

typedef char Item;

Item data;

Node *left;

Node *right;

};
——

// returns null is target is not present; else returns pointer to appropriate node.

Node* search (Node *root, const Item& target)

{

Node *null_ptr = (Node*) 0;

if ( ! root )

return null_ptr;

if ( root->data == target)

return root;

else if (root->data < target)

return search(root->right, target);

else

return search (root->left, target);

}

———-

We now look at a non-recursive version of the search function. The basic idea of searching remains the same — if the target is less than the root’s data, go to the left child, else if it is greater, go to the right.

———

Node* search (Node *root, const Item& target)

{

Node *temp = root, *null_ptr = (Node*) 0;

while (true)

{

if (temp == (Node*) 0)

return null_ptr;

if (temp -> data == target)

return temp;

else if (target < temp->data)

temp = temp->left;

else

temp = temp -> right;

}

}

——–

Searching in a BST takes O(log n) time in the average case. In the worst case – if the tree is highly skewed, it takes O(n) time. [n is the number of nodes in the BST.]

—————-

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

%d bloggers like this: