INTRODUCTION TO BINARY SEARCH TREE

 

UNIT STRUCTURE

1. Learning Objectives
2. Introduction
3. Definition of Binary Search Tree
4. Searching in Binary Search Tree
5. Insertion into Binary Search Tree
6. Deletion from Binary Search Tree
7. Traversal in Binary Search Tree
8. Let Us Sum Up
9. Answers to check your progress
10. Further readings
11. Possible Questions.

LEARNING OBJECTIVES

 
After going through this unit, you will be able to:
learn the basic concept of binary search tree
describe the searching operation on BST
explain the insertion and deletion operation on BST

INTRODUCTION


In the previous unit, we have already discuss about trees and its various types along with different tree traversal procedures. Let us remind its basic concept again. A tree is either an empty (that cannot be drawn) or it consists of a node called the root of the tree and a number of disjoint trees called the subtrees of the original tree.

A node may contain a value or a condition or represents a separate data structure or a tree of its own. Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees grow down, not up as they do in nature). A node that has a child is called the child’s parent node (or ancestor node, or superior). A node has at most one parent.The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path).

The topmost node in a tree is called the root node. Being the topmost node, the root node will not have parents. It is the node at which operations on the tree commonly begin (although some algorithms begin with the leaf nodes and work up ending at the root). All other nodes can be reached from it by following edges or links. (In the formal definition, each such path is also unique). In diagrams, it is typically drawn at the top. In some trees, such as heaps, the root node has special properties. Every node in a tree can be seen as the root node of the subtree rooted at that node.


Nodes at the bottommost level of the tree are called leaf nodes. Since they are at the bottommost level, they do not have any children.
An internal node or inner node is any node of a tree that has child nodes and is thus not a leaf node.

A subtree is a portion of a tree data structure that can be viewed as a complete tree in itself. Any node in a tree T, together with all the nodes below it, comprise a subtree of T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree (in analogy to the term proper subset).
In this unit, we will introduce you an another binary tree data structure namely binary search tree. We will also discuss about the different operations (i.e. insertion, deletion and searching) on binary search tree.


BINARY SEARCH TREE


A binary tree is called a binary search tree (BST) if for every node in the tree the data elements in the node is greater than or equal to the data elements in all the nodes in the left subtree and is less than the data elements in all the nodes in the right subtree.
Consider a binary tree T. T is a binary seach tree, that is, the value of the data elements in every node N in T greater than or equal to the data elements in every node in left subtree and is less than the data elements in every node in right subtree. Here suppose 23 is replaced by 32. Then T would still be a binary search tree. On the other hand, suppose, the 23 is replaced by 42. Then T would not be a binary search tree, since the 38 would not be greater than the 42 in its left subtree.


The inorder traversal of such a binary search tree yields a list of sorted order. Now, let us discuss the various operations performed on BST i.e. searching for a node, inserting a node and deleting a node.


SEARCHING IN BINARY SEARCH TREE


Suppose T is a binary search tree. Here we are going to discuss the basic operation of searching with respect to the binary search tree T.
Suppose an ITEM of information is given. The following algorithm finds the location of ITEM in the binary search tree T.

Step1 : Compare ITEM with the root node N of the tree.
(i) If ITEM < N, proceed to the left child of N.
(ii) if ITEM > N, proceed to the right child of N.

Step2 : Repeat Step1 untill one of the following occurs :
(i) We meet a node N such that ITEM=N. In this case the search is successful.
The most common operations performed on a BST is searching for

a key stored in the tree. These operations run in O(h) time where h is the height of the tree i.e. h is the number of links root node to the deepest node.
The TREE-SEARCH (x, k) algorithm searches the tree root at x for a node whose key value equals k. It returns a pointer to the node if it exists otherwise NIL
BSTREE_SEARCH(x, k)
if x = NIL .OR. k = key[x]
then return x
if k < key[x]
then
return BSTREE_SEARCH (left[x], k)
else
return BSTREE_SEARCH (right[x], k)
Clearly, this algorithm runs in O(h) time where h is the height of the tree.
Algorithm : Searching in Binary Search Tree
FINDBST( INFO, LEFT,RIGHT,ROOT,ITEM,LOC,PAR)
A binary search tree T is in memory and an ITEM of information is given. This procedure finds the location LOC of ITEM in T and also the location PAR of the parent of ITEM. There are three special cases:
1.LOC=NULL and PAR=NULL will indicate that the tree is empty.
2.LOC=!NULL and PAR=NULL indicates that ITEM is the root of T.
3.LOC=NULL and PAR=!NULL indicates that ITEM is not in T and can be added to T as a child of the node N with location PAR.
Step1: If(ROOT=NULL) then // Tree Empty//
Set LOC :=NULL and PAR :=NULL and Return.
Step2: If ( ITEM=INFO[ROOT] then // ITEM at root//
Set LOC :=ROOT and PAR:=NULL and Return.

Step3: If (ITEM<INFO[ROOT] then //Initialize pointers PTR and SAVE/
Set PTR :=LEFT[ROOT] and SAVE:=ROOT
Else Set PTR:=RIGHT[ROOT] and SAVE:=ROOT
Step4: Repeat Step5 and Step6 while PTR=!NULL
Step5: If(ITEM=INFO[PTR]) then
Set LOC :=PTR and PAR:=SAVE and Return
Step6: If(ITEM<INFO[PTR]) then
Set SAVE :=PTR and PTR:=LEFT[PTR]
Else Set SAVE :=PTR and PTR :=RIGHT[PTR]
End of the step4 loop.
Step7: Set LOC:=NULL and PAR:=SAVE
Step8: Exit.
Example: Write a C program to search an element from the binary search tree.
Solution:
#include<stdio.h>
#include<conio.h>
struct tree
{
int data;
struct tree *lft;
struct tree *rt;
};
int sn;
struct tree *bt=NULL;
struct tree *insert(struct tree *bt,int no);
void search(struct tree *bt, int sn);

main()
{
int no;
clrscr();
printf(“\nEnter the nodes of tree in preorder and O to quit”);
scanf(“%d”,$no);
while(no!=O)
{
bt=insert(bt,no);
scanf(“%d”,&no);
}
printf(“\nEnter the number to be searched=”);
scanf(“%d”,&ns);
search(bt,sn);
}
struct tree *insert(struct tree *bt,int no)
{
if(bt==NULL)
{
bt=(struct tree *)malloc(sizeof(struct tree));
bt->lft=bt->rt=NULL;
bt->data=no;
}
else
{
if(no<bt->data)
bt->lft=insert(bt->lft,no);
else if(no>bt->data)
bt->rt=insert(bt->rt,no);
else if(no==bt->data)
{
printf(“\nDuplicate nodes:Program exited”);
exit(0);
}
}
return(bt);
}

void search(struct tree *bt,int fn)
{
if(bt==NULL)
printf(“\nThe number doesnot exit”);
else if( fn==bt->data)
printf(“\nTHe numbsr %d is present in tree”,fn);
else if(fn<bt->data)
search(bt->lft,fn);
else
search(bt->rt,fn);
}

INSERTION INTO BINARY SEARCH TREE


An element can be inserted into an appropriate position in a BST. For inserting an element, we will have to locate the parent node. Therefore, the node’s value is first compared with the value of the root. If its value is less than the root, it is then compared with the value of the root’s left child and recursively called the left sub-tree. If its value is greater than the root, it is compared with the root’s right child and recursively called the right sub-tree. This process continues, until the new node is compared with a leaf node, and then it is added as this node’s right or left child, depending on its value.
In the following we represent the function to implement insertion operation into a binary search tree.
void InsertNode(struct node *treeNode, struct node *newNode)
{
if (treeNode == NULL)
treeNode = newNode;
else if (newNode->value < treeNode->value)
InsertNode(treeNode->left, newNode);
else
InsertNode(treeNode->right, newNode);
}

This operation requires time proportional to the height of the tree in the worst case, which is O(log n) time in the average case over all trees.
Consider the following binary search tree T. Suppose we want to insert an ITEM=20. Then we proceed in the following ways :



Step: Compare ITEM=20 with the root, 38 of the tree T. Since 20<38,proceed to the left child of 38, which is 14.
Step2: Compare ITEM =20 with 14, Since 20>14, proceed to the right child of 23,
Step3: Compare ITEM =20 with 23, Since 20<23, proceed to the left child of 23, which is 18.
Step4: Compare ITEM =20 with 18. Since 20>18 and 18 does not have a right child, insert 20 as the right child of 18.
Hence we will get the following Binary search Tree after inserting the ITEM=20.


Example: Write a C program to insert an element into the binary search tree.
Solution:
#include<stdio.h>
#include<conio.h>
struct tree
{
int data;
struct tree *lft ,*rt;
}
int in;
struct tree *bt=NULL;
struct tree * insert(struct tree *bt, int no);
void inorder(struct tree *bt);
main()
{
clrscr();
printf(“\nEnter the nodes of the tree in preorder: and 0 to quit”);
scanf(“%d”,&no);
while(no!=0)
{
bt=insert(bt,no);
scanf(“%d”,&no);
}
printf(“\nEnter the number to be inserted=”);
scanf(“%d”,&in);
bt=insert(bt,in);
printf(“\nThe inorder of tree after insertion of an element”);
inorder(bt);
}
struct tree *insert(struct tree *bt, int no)
{
if (bt==NULL)
{
bt=(struct tree *)malloc(sizeof(struct tree));
bt->lft=bt->rt=NULL;
bt->data=no;
}

else
{
if(no<bt->data)
bt->lft=insert(bt->lft,no);
else
if(no>bt->data)
bt->rt=insert(bt->rt,no);
else
if(no==bt->data)
{
printf(“\nDuplicate nodes :Program exited”);
exit(0);
}
}
return(bt);
}
void inorder(struct tree *bt)
{
if(bt!=NULL)
{
inorder(bt->lft);
printf(“%d”,bt->data);
inorder(bt->rt);
}
}


DELETION FROM BINARY SEARCH TREE


Suppose T is a binary search tree, and suppose an ITEM of information is given. This section gives an algorithm which deletes ITEM from the tree T.
There are several cases to be considered :

1. Deleting a leaf : deleting a node with no children is easy, as we can simply remove it from the tree.
2. Deleting a node with one child : delete it and replace it with its child.
3. Deleting a node with two children : suppose the node to be deleted is called N. We replace the value of N with either its in-order successor (the left-most child of the right subtree) or the in-order predecessor (the right-most child of the left subtree).
Once we find either the in-order successor or predecessor, swap it with N, and then delete it. Since both the successor and the predecessor must have fewer than two children, either one can be deleted using the previous two cases. In a good implementation, it is generally recommended to avoid consistently using one of these nodes, because this can unbalance the tree.
Let us take an example, from the following BST if we are trying to delete a leaf, there is no problem. We just delete it and the rest of the tree is exactly as it was, so it is still a BST.


There is another simple situation: suppose the node we’re deleting has only one subtree. In the following example, ‘3’ has only 1 subtree.
To delete a node with 1 subtree, we just ‘link past’ the node, i.e. connect the parent of the node directly to the node’s only subtree. This always works, whether the one subtree is on the left or on the right. Deleting ‘3’ gives us:


which we normally draw :



Finally, let us consider the only remaining case : how to delete a node having two subtrees. For example, how to delete ‘6’? We’d like to do this with minimum amount of work and disruption to the structure of the tree.
The standard solution is based on this idea : we leave the node containing ‘6’ exactly where it is, but we erases the value 6 and find another value to store in the ‘6’ node. This value is taken from a node below the ‘6’s node, and it is that node that is actually removed from the tree.
Let the original tree structure from which we want to remove ‘6’.

Erase 6, but keep its node


Now, what value can we move into the vacated node and have a binary search tree? Let us try for it. If we choose value X, then :
everything in the left subtree must be smaller than X.
everything in the right subtree must be bigger than X.
Let’s suppose we’re going to get X from the left subtree. (2) is guaranteed because everything in the left subtree is smaller than everything in the right subtree. What about (1)? If X is coming from the left subtree, (1) says that there is a unique choice for X - we must choose X to be the largest value in the left subtree. In our example, 3 is the largest value in the left subtree. So if we put 3 in the vacated node and delete it from its current position we will have a BST with 6 deleted.
Here it is :


So our general algorithm is : to delete N, if it has two subtrees, replace the value in N with the largest value in its left subtree and then delete the node with the largest value from its left subtree.

CHECK YOUR PROGRESS



1. A binary search tree (BST) is a binary tree data structure which has the following properties:
i) Each node has a value.
ii) A total order is defined on these values.
iii) The left subtree of a node contains only values less than the node’s value.
iv)The right subtree of a node contains only values greater than or equal to the node’s value.

(a) 1, & 2 only (b) 1, 2 & 3 only
(c) 2 & 3 only (d) all above


2. which of the following traversal techniques lists the nodes of a binary search tree in ascending order ?
(a) Post-order (b) In-order
(c) Pre-order (d) none of these.
3. Binary expression tree is traversed in..............traversal.
(a) Pre-order (b) Post-order.
(c) In-order (d) Both(a)&(b).
4. The most common operations performed on a BST is searching for a key stored in the tree. If h is the height of the tree then this operations runs in the time
(a) O(h) (b) O(2h)
(c) O(1) (d) none of above
5. To traverse a non-empty binary search tree in inorder, perform the following operations :
(a) i) Traverse the left subtree in inorder
ii) Visit the root
iii) Traverse the right subtree in inorder
(b) i) Visit the root
ii) Traverse the left subtree in preorder
iii) Traverse the right subtree in preorder
(c) i) Traverse the left subtree in postorder
ii) Traverse the right subtree in postorder
iii) Visit the root
(d) none of these



LET US SUM UP


1. Binary Search Tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x.

2. In-order traversal of the binary search tree will produce the elements in ascending order.

3. Basic operations performed on BST are searching, inssertion and deletion.

4. Searching a binary tree for a specific value can be a recursive or iterative process.
5. Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees for findout the appropriate position for inserting elements.
6. For deleting a particular node from a BST, there are several cases to be considered :
i) Deleting a leaf : deleting a node with no children is easy, as we can simply remove it from the tree.
ii) Deleting a node with one child : delete it and replace it with its child.
iii) Deleting a node with two children : suppose the node to be deleted is called N. We replace the value of N with either its in-order successor (the left-most child of the right subtree) or the in-order predecessor (the right-most child of the left subtree).


ANSWERS TO CHECK YOUR PROGRESS


CHECK YOUR PROGRESS - 1
1(d),2(c),3(d), 4(a),5(a).

FURTHER READINGS


1. Data structures using C and C++
Yedidyah Langsam, Moshe J. Augenstein, aaron M. Tenenbaum.
Prentice-Hall India.

2. Data Structures
Seymour Lipschutz
Schaum’s Outline Series in Computers.
Tata Mc Graw- Hill.

3. Introduction to Data Structures in C
Ashok N. Kamthane
Perason Education.

 

POSSIBLE QUESTIONS


1. What is binary search tree ? How is an element searched ?

2. Explain the procedure of insertion and deletion of data with binary search tree.

3. Write a C program to search an element from the binary search tree.

4. Write a program to display all nodes of the binary search tree and then insert data and display it along with the previous data of the tree.

5. What are the various traversal techniques in a binary search tree? Explain it.



  TOP