Searching BST

“Scanning through an English dictionary is faster because, you directly go to the indexed character and scan through letter one-by-one to get to the exact text you are searching for”

Preface

  Sorry for not updating for a long period of around 5 months. Really struck up with busy schedules. Now I forgot all the data structures and algorithms. So need to relearn and hence will revisit all my previous posts before going into medium difficulty content.

References

http://analgorithmaday.blogspot.in/2011/03/successor-and-predecessorbst.html

Introduction

  How would you design a search algorithm which does a search through the English dictionary in really fast manner?  Manually, you can easily check a dictionary based on lexicographic ordering. But how would you design a data structure which can naturally allow you to do that? you can do this with a binary search tree.

In previous article, we learnt about Hash Tables(http://analgorithmaday.blogspot.in/2011/10/hash-tables-dictionaries.html) that it is an array index to data mapping. This is a direct mapping hash table which can be generically implemented using binary search trees. If you check the implementations of map and hash_map in C++ STLs, these are implemented using a kind of binary search trees.

Concept

   We decide left or right of the binary search tree based on the value we need to search for. It reduces loops logarithmically.

  Bonus: We can also check how to get the 4th smallest element out of the binary search tree.  This can be done by having an extra field which can calculate the rank of the node.

Rank of a node in BST is number of nodes in the left sub-tree + 1. This is nothing but number of keys less than the current value. This rank is helpful to identify the successor and predecessor easily.

If space is not a constraint, then we should go with ranking the nodes. But if its a constraint, then you should identify the successor of each node

Code

Searching a binary search tree (iteration)

class BST {

public:

    int data;

    BST* parent;

    BST* left;

    BST* right;

};

BST* createBSTNode(int data)

{

    BST* newNode = new BST();

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    newNode->parent = NULL;

    return newNode;

}

void bst_insert(BST*& tree, BST* node)

{

    BST* prev = NULL;

    BST* iter=tree;

    while(iter != NULL)

    {

        prev = iter;

        if(node->data > iter->data)

            iter = iter->left;

        else

            iter = iter->right;

    }

    // found node is parent to our node

    node->parent = prev;

    // if prev is NULL

    // then this is the first node

    // change the root NODE

    if(prev == NULL)

        tree = node;

    else {

        // now we need to decide where the node

        // should go: left or right

        if(node->data > prev->data)

            prev->left = node;

        else

            prev->right = node;

    }

}

BST* convert_arr_bst(int* arr, int size)

{

    BST* tree=NULL;

    for(int i=0;i<size;i++) {

        bst_insert(tree, createBSTNode(arr[i]));

    }

    return tree;

}

void main()

{

    BST *tree, *tmp;

    int k = 6;

    bool found = false;

    int arr[]= {2,30,12,10,22,6};

    tree = convert_arr_bst(arr, 6);

    tmp = tree;

    while(tmp && !found)

    {

        if(tmp->data == k) found = true;

        if(tmp->data < k) tmp = tmp->left;

        else {

            tmp = tmp->right;

        }

    }

    if(found == true)

        cout<<"Found"<<endl;

    else

        cout<<"Not Found"<<endl;

}

Searching a binary search tree based on ranks

Will see this in next article about constructing binary search trees with ranks.