Our final year just started. For my seventh semester I follow "Advanced Algorithm" Module. For the second day we were taught various of trees which were inspired by Binary Search Trees. You know when it comes to algorithms, all are not straight forward at all. Even though the theories are explained in pseudo codes, sometimes some of the steps are tricky. That because we are much familiar with the programming language which we use at most of the times.
Okay, the problem started like this. Before to study the tree concepts inspired by BST (here after Binary Search Tree will be called BST), I must have a thorough knowledge in BST, right :D ? But I can't remember a thing. So I started studying BST but pseudo codes were not straight forward and reading theory made me boring. Then I started to refer already implemented codes. But most of them were deviated form the pseudo code. So I dusted my hands and started to implement BST Operation based in Pseudo codes.
I preferred C++ and I implemented the code in C++. You can view it as a code blocks project in this link Code Blocks Project .
What is Binary Search Tree?
BST is organized as a binary tree with the following properties.
Let x and y be nodes in a BST
• If y is in the left subtree of x, y.key ≤ x.key
• If y is in the right subtree of x, y.key ≥ x.key
There are key words related with BST, They are,
- Root - The First Node of the tree
- Leaf - The endings of the tree are called leaves (leaf). They don't have any child nodes.
- Height of a node - Number of edges along the longest path from the node to a leaf.
- Height of Tree - Simply the height of the root. Descriptively Number of edges along the longest path from the root to a leaf.
- Depth of node : Number of edges from the root to the node
Let's implement it :)
Node :
Binary Search Tree Node represents the element of BST. It contains a key value, pointer to left child, pointer to right child and pointer to its parent. Following is the implementation of a node in C++.
struct node{
int key;
node *left;
node *right;
node *parent;
};
Tree :
Tree holds a pointer to the root node. If this root node is null, it means the tree is empty. Following is the implementation of a BST in C++.
struct BST{
node *root;
};
INSERTION IN BST !
Let us insert some values to the tree.
The Basic rule of BST is,
Let x and y be nodes in a BST
• If y is in the left subtree of x, y.key ≤ x.key
• If y is in the right subtree of x, y.key ≥ x.key
For the ease of learning, we will consider this order of keys entered to the BST.
10, 2, 20, 6, 8, 5, 14, 23, 4 , 3, 1
So if we followed binary search properties well, the expected output tree should be,
So now let's discuss step by step, how inserted them.
First thing BST Insertion is, we always start from the beginning. The first node is 10, then it will be the root.
In Step 1, 2 is smaller than 10, so 2 will be the left child of 10.
Step 2 : 20 is greater than 10, so 20 will be the right child of 10.
Step 3 : 6 is smaller than 10, it should be in left side of 10. But 10's left child is occupied. So it will forward to 10's left child which is 2. Now ^ is greater than 2. So 6 will be 2's right child.
Step 4 : .........
Step 5 : 23 is greater than 10. It should be in right side of 10. 10's right child is occupied. It will forward to 10's right child which 20. 23 is greater than 20. So 23 will be 20's right child.
Step 6: 1 is the smallest among all of them. It should be in 10's left side, So it will be the 2's left child.
Following is the implementation of the node insertion in BST in C++ .
node *y = NULL;
node *x = T->root;
while(x != NULL){
y = x;
if(z->key < x->key){
x = x->left;
}
else x = x->right;
}
z->parent = y;
if(y == NULL){
T->root = z; //tree T is empty
}
else if ( z->key < y->key ){
y->left = z;
}
else{
y->right = z;
}
}
Please find a simillar kind of example in this link.
TRAVERSE THROUGH BST!
In early we discussed that, when we consider a node in BST, left child contains the smaller key value than the key of node and right child contains the larger key value. Using this basic idea we can going around the BST in a sorted manner. In this algorithm we use Recursion .
The implementation of the algorithm as follows in C++.
void IN_ORDER_TREE_WALK(node *root){
if(root != NULL){
IN_ORDER_TREE_WALK(root->left);
cout << root->key << endl;
IN_ORDER_TREE_WALK(root->right);
}
}
For our given order the In Order Traversing result should be,
This may harder to understand, but let us clear this algorithm implementation with our example.
Following diagram shows the execution order of the recursive algorithm. If you don't understanding the following algorithm, I suggest you to improve your knowledge in recursion because in these typ of tree structures, recursion is heavily in use.
Today we learnt, What is a BST, how to implement a node and a BST and insertion and in order traversal in BST.
In Next Article, we'll discuss Finding the successor, find minimum key of a BST, find the maximum key of BST and Deleting a node in BST. Anyway I have already implemented them in the project. You can refer them and get a good idea of its implementation. Till then good bye.
Link to the Code Blocks C++ Project
Please feel free to publish problems in the comments and I will help you if I can :)
No comments:
Post a Comment