Friday, 24 November 2017

Binary Search Tree: A Non-Linear Data Structure

Definition: A binary search tree is a binary tree.  It may be empty.  If it is not empty, it satisfies the following properties:
1. Every element has a key, and no two elements have the same key, that is, the keys are unique.
2. The keys in a nonempty left subtree must be smaller than the key in the root of the subtree.
3. The keys in a nonempty right subtree must be larger than the key in the root of the subtree.
4. The left and right sub-trees are also binary search trees.

Example of the Binary Search Tree:

Searching operation performed on Binary Search Tree:
Suppose we wish to search for an element with a key.  We begin at the root.  If the root is NULL, the search tree contains no elements and the search is unsuccessful.  Otherwise, we compare key with the key value in root.  If key equals root’s key value, then the search terminates successfully.  If key is less than root’s key value, then no elements in the right sub-tree can have a key value equal to key.  Therefore, we search the left sub-tree of root.  If key is larger than root’s key value, we search the right sub-tree of root.

Implementation of Recursive function for Binary Search Tree:
tree_ptr   search( tree_ptr   root, int   key ) 
if ( !=root )
return   NULL;
if ( key = = root->data )
return   root;
if ( key < root->data )
return   search ( root->left_child, key );
return   search ( root->right_child, key );

Mukesh Rajput

No comments:

Post a Comment

Mukesh Rajput