In Computer Science, a binary search tree is a data structure based on nodes in which all nodes in the left subtree (left child) have a numeric value lower the root node value, and all nodes of the right (right child) have a higher value than the root node value. The aim of this tree is to structure the data in a flexible way, allowing binary search.
- Nodes – are all items stored in the tree;
- Root – is the top node of the tree (in the illustration above, the root is the node 8);
- Children – are the nodes that come after the other nodes (in the case of the above figure, the node 6 is the son of 3);
- Parents – are the nodes that comes before the other nodes (in the case of the above figure, the node 10 is the father of 14);
- Leaves – are the nodes that have no children; are the last nodes of the tree (in the case of the above figure, the leaves are 1, 4, 7 and 13).
The search operation on a binary tree for a given value can be made recursive or interactively. (In the example below I have used the recursive approach).
Let’s assume we want to locate the number 15 in a given binary tree. The search starts at the root node. If the value in the root node is equal to the number 15 the search stops as we have found the number we were looking for. Otherwise, we go on checking ifour number (15) is greater or lower than the value in the root node. If our number is lower than the value in the root node, the search continues in left child (remember that the lowest values are located in the left child of the tree). On the other hand, if our number is greater than the value in the root node, the search continues in the right child. This process continues until either our number is found or the search reachs the leaf node, i.e. the value was not found in the tree.
1. Insertion operation
The process of inserting a new value in the tree is similar to the search process described above. The reason for that is that we need to go through the whole tree until we find a spot for the number we want to insert that will keep the ordering of the tree (remember that the values in the tree are organized in such a way that lower values are located in the left child and higher value in the right child). If the value to be inserted is greater than the value in the root, we go to the right child, or if it is lower than we go to the left child. We do this process until we find the perfect spot for that value.
2. Deletion operation
The process of removing a value from the tree is a little bit trickier. We have 3 different cases for deletion:
- Deleting a leaf node;
- Deleting a node with one child;
- Deleting a node with 2 children;
To do the exclusion of a leaf node, we simply remove it from the tree.
To do the exclusion of a node with 1 child, the child needs to be moved to his parent’s position.
To do the exclusion of a node with 2 children, we have two different ways to do it:
A) Using the lowest node of the sub-tree to the right;
B) Using the highest node of the sub-tree to the left;
These two approaches have the same complexity and search time. So it is up to you to decide which one you want to use.
Using method (A): In the example below, to remove the node holding the number 3 we search for the lowest node from 6, in this case will be the 4 node.
Using method (B): In the example below, we remove the 8 node and the result is as follows:
Let’s now see some codes so you will understand a little bit better how a binary tree works. Remember that at the end of this post you can download a Binary Tree project that was developed in C using Dev-C++.
Function to insert a value in binary tree:
void inserir(tArv *t, int dado){
int ok;
if (*t == NULL) {
*t = (tnoarv *) malloc(sizeof(tnoarv));
if (*t == NULL) return;
(*t)->esq = NULL;
(*t)->dir = NULL;
(*t)->info = dado;
}
if (dado < (*t)->info) {
inserir(&((*t)->esq), dado);
}
else{
if (dado > (*t)->info) {
inserir(&((*t)->dir), dado);
}
}
}Function to remove a value from a binary tree:
void remover(tArv *raiz, int valor){
tArv aux;
if(!arvore_vazia(*raiz)){
if(valor < (*raiz)->info){
remover(&((*raiz)->esq), valor);
}else{
if(valor > (*raiz)->info){
remover(&((*raiz)->dir), valor);
}else{
if( !arvore_vazia((*raiz)->esq) && !arvore_vazia((*raiz)->dir) ){
aux = minimo((*raiz)->dir);
(*raiz)->info = (aux->info);
remover(&(*raiz)->dir, (*raiz)->info);
}else{
aux = *raiz;
if(arvore_vazia((*raiz)->esq)){
*raiz = (*raiz)->dir;
}
else {
*raiz = (*raiz)->esq;
}
free(aux);
}
}
}
}
}Minimum function returns the node with minimum value:
tArv minimo(tArv T){
if(arvore_vazia(T)){
return NULL;
}else{
if( arvore_vazia(T->esq) ){
return T;
}else{
return minimo(T->esq);
}
}
}Maximum function returns the node with the maximum value:
tArv maximo(tArv T){
if( !arvore_vazia(T) ){
while( !arvore_vazia(T->dir) ){
T = T->dir;
}
}
return T;
}Function to search for a value in the binary tree:
tArv busca_elemento(tArv t, int dado){
tArv achou;
if (arvore_vazia(t)) return NULL;
if (t->info == dado) return t;
achou = busca_elemento(t->esq, dado);
if (arvore_vazia(achou))
achou = busca_elemento(t->dir, dado);
return achou;
}
If you want to *download this project (binary tree in C) -> [download id=”168″].
*Note that to download you must register/login in this website.
Thanks for reading.
Like and Share if you found it may be useful to someone you know!
Would you like to check the Portuguese version?
Click on the Brazilian flag -> 