TSEARCH, CAPP.

The following program implements a Binary Search Tree. The idea of a Binary Search tree is as follows.

Every node of the binary tree has a key associated with it. The tree is sorted in such a way that for each node, the key values of all the nodes that lie in its left sub-tree are smaller than the key value of that node, where as the key values of all the nodes that lie in its right sub-tree are greater than the key value of that node. It must be noted that there must be no duplicate nodes in the tree, and there must be a unique path from the root node to every node in the tree.

Some of the advantages of using a Binary Search Tree are as follows: Implementation of the code is simple and efficient, insertion, deletion, and searching in the Binary Search Tree is, with an average complexity of O(log n) and worst case complexity of O(n) for insertion and searching and a worst case complexity of O(height) for deletion.

Code Snippet
int: num_elements = 65535, depth = 16, key, index
tree := Binary tree with num_elements number of nodes in it.
initialize key_found = 0   // key_found keeps a track of how many keys we were able to find in the tree.


for(i=0; i<num_elements; ++i){
    key = i;  
    index = 0;
   
    if(key == tree[0]){
        key_found = key_found + 1;       
        continue;
    }
      
    for(i=0; i < depth-1; i++){
        index = (index*2) + 1 + (key > tree[index]); 
                                             
        if(key == tree[index]){
            key_found = key_found + 1;
            break;
        }
    }
}