Binary Search Tree:
-
Operations: Search, Insertion, Deletion
-
Program Examples
-
Expression Tree Concept
-
Create Exp. Tree from Prefix
-
Create Exp. Tree from Postfix
-
Create Exp. Tree from Infix
-
Prefix, Postfix, Infix Traversal
-
Binary Search Tree has the following basic
operations:
-
find(x) :
find key x in the BST
-
insert(x) :
insert new key x into BST
-
remove(x) :
remove key x from BST
Operations: Search
•
Because of the property of BST,
finding/searching in BST is easy.
•
Let the key that we want to search is X.
– We begin at root
– If the root contains X then search
terminates successfully.
– If X is less than root’s key then search
recursively on left sub tree, otherwise search recursively on right sub tree.
-
struct node* search (struct node *curr, int
X) {
-
if ( curr == NULL )
return NULL;
-
// X is found
-
if ( X ==
curr->data ) return curr;
-
// X is located in
left sub tree
-
if ( X < curr->data ) return
find(curr->left, X);
-
// X is located in
right sub tree
-
return
find(curr->right, X);
-
}
Operations: Insertion
•
Inserting into Binary SearchTree is done recursively.
•
Let the new node’s key be X,
– Begin at root
– If X is less than node’s key then insert
X into left sub tree, otherwise insert X into right sub tree
– Repeat until we found an empty node to
put X (X will always be a new leaf)
Algorithm:
Step 1: IF
TREE = NULL, then
Allocate
memory for TREE
SET TREE->DATA =
VAL
SET
TREE->LEFT = TREE ->RIGHT = NULL
ELSE
IF VAL <
TREE->DATA
Insert(TREE->LEFT,
VAL)
ELSE
Insert(TREE->RIGHT,
VAL)
[END OF IF]
[END OF IF]
Step 2: End
Operations: Insertion – Example
Operations: Deletion
•
There are 3 cases which should be considered:
– If the key is in a leaf, just delete that
node
– If the key is in a node which has one
child, delete that node and connect its child to its parent
– If the key is in a node which has two
children, find the right most child of its left sub tree (node P), replace its
key with P’s key and remove P recursively. (or alternately you can choose the
left most child of its right sub tree)
Algorithm:
Step 1: IF TREE = NULL, then
Write “VAL not found in the
tree”
ELSE IF VAL < TREE->DATA
Delete(TREE->LEFT, VAL)
ELSE IF VAL > TREE->DATA
Delete(TREE->RIGHT, VAL)
ELSE IF TREE->LEFT AND TREE->RIGHT
SET
TEMP = findLargestNode(TREE->LEFT)
SET
TREE->DATA = TEMP->DATA
Delete(TREE->LEFT,
TEMP->DATA)
ELSE
SET
TEMP = TREE
IF
TREE->LEFT = NULL AND TREE ->RIGHT = NULL
SET
TREE = NULL
ELSE
IF TREE->LEFT != NULL
SET
TREE = TREE->LEFT
ELSE
SET
TREE = TREE->RIGHT
FREE
TEMP
Step 2: End
