This blog is under construction

Wednesday, 1 May 2013

Implement Dictionary Using Binary Search Tree

  • Dictionary can be implemented using binary search tree.  A binary search tree is a binary tree such that each node stores a key of a dictionary.
  • Key 'k' of a node is always greater than the keys present in its left sub tree.
  • Similarly, key 'k' of a node is always lesser than the keys present in its right sub tree.

Example:
                              well
                            /       \
                          bus    xmas
                         /     \          \
                       air   aero      zebra

In the above example, keys present at the left sub-tree of the root node are lesser than the key of the root node.  And also, the keys present at the right sub-tree are greater than the key of the root node.
  • To insert an element in a binary search tree, check whether the root is present or not.  If root is absent, then the new node is the root.
  • If root node is present, check whether the key in new node is greater than or lesser than the key in root node.
  • If key in new node is less than the key in root, then traverse the left sub-tree recursively until we reach the leaf node.  Then, insert the new node to the left(newnode < leaf)/right(newnode > leaf) of the leaf.
  • If the key in new node is greater than the key in root, then traverse the right sub-tree recursively until we reach the leaf node.  Then, insert the new node to the left(newnode < leaf)/right of the leaf
InsertionInBST(T, newnode)
y<-NULL           
x <- root[T]
while x != NULL
     y<-x
     if  key[z] < key
          then x <- left[x]
          else  x <- right[x]
parent[newnode] <- y
if y == NULL
   then root[T] <- newnode
else if key[newnode] < key[y]
    then left[y] <- newnode
    else right[y] <- newnode

Insert "yell" to the below binary search tree.
                          workload
                            /       \
                          bus    xmas
                         /     \          \
                       air   aero      zebra


                          workload
                         /             \
                      bus            xmas
                      /     \        /        \
                   air   aero    yell     zebra

To delete a node from binary search tree, we have three different cases.
Node X has no children
Node X has one child
Node X has two children

Case 1:
If X has no children

                          workload
                         /             \
                      bus            xmas
                      /     \        /        \
                   air   aero    yell     zebra

Delete "zebra" from above binary search tree.

                          workload
                         /             \
                      bus            xmas
                      /     \        /   
                   air   aero    yell

Case 2:
If X has only one child, then delete x and point the parent of x to the child of x.

                          workload
                         /             \
                      bus            xmas
                      /     \        /   
                   air   aero    yell

Delete "xmas" from the above binary search tree.

                          workload
                         /             \
                      bus            yell
                      /     \       
                   air   aero

Case 3:
If X has two children, then find its successor 'S'.  Remove 'S' from the binary search tree.  And replace X with 'S'

                          workload
                         /             \
                      bus            xmas
                      /     \        /        \
                   air   aero    yell     zebra

Remove "workload" from the above binary search tree.  The successor for "workload"(smallest element in the right subtree of "workload") is "yell".  Remove it and replace "workload with "yell".

                              yell
                            /      \
                        bus      xmas
                       /    \          \
                    air   aero      zebra

See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs

Example program To Implement Dictionary using Binary Search Tree(in C):



  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>

  struct BSTnode {
        char word[128], meaning[256];
        struct BSTnode *left, *right;
  };

  struct BSTnode *root = NULL;

  struct BSTnode * createNode(char *word, char *meaning) {
        struct BSTnode *newnode;
        newnode = (struct BSTnode *)malloc(sizeof(struct BSTnode));
        strcpy(newnode->word, word);
        strcpy(newnode->meaning, meaning);
        newnode->left = newnode->right = NULL;
        return newnode;
  }

  void insert(char *word, char *meaning) {
        struct BSTnode *parent = NULL, *current = NULL, *newnode = NULL;
        int res = 0;
        if (!root) {
                root = createNode(word, meaning);
                return;
        }
        for (current = root; current !=NULL;
           current = (res > 0) ? current->right : current->left) {
                res = strcasecmp(word, current->word);
                if (res == 0) {
                        printf("Duplicate entry!!\n");
                        return;
                }
                parent = current;
        }
        newnode = createNode(word, meaning);
        res > 0 ? (parent->right = newnode) : (parent->left = newnode);
        return;
  }

  void deleteNode(char *str) {
        struct BSTnode *parent = NULL, *current = NULL, *temp = NULL;
        int flag = 0, res = 0;
        if (!root) {
                printf("BST is not present!!\n");
                return;
        }
        current = root;
        while (1) {
                res = strcasecmp(current->word, str);
                if (res == 0)
                        break;
                flag = res;
                parent = current;
                current = (res > 0) ? current->left : current->right;
                if (current == NULL)
                        return;
        }
        /* deleting leaf node */
        if (current->right == NULL) {
                if (current == root && current->left == NULL) {
                        free(current);
                        root = NULL;
                        return;
                } else if (current == root) {
                        root = current->left;
                        free (current);
                        return;
                }

                flag > 0 ? (parent->left = current->left) :
                                (parent->right = current->left);
        } else {
                /* delete node with single child */
                temp = current->right;
                if (!temp->left) {
                        temp->left = current->left;
                        if (current == root) {
                                root = temp;
                                free(current);
                                return;
                        }
                        flag > 0 ? (parent->left = temp) :
                                        (parent->right = temp);
                } else {
                        /* delete node with two children */
                        struct BSTnode *successor = NULL;
                        while (1) {
                                successor = temp->left;
                                if (!successor->left)
                                        break;
                                temp = successor;
                        }
                        temp->left = successor->right;
                        successor->left = current->left;
                        successor->right = current->right;
                        if (current == root) {
                                root = successor;
                                free(current);
                                return;
                        }
                        (flag > 0) ? (parent->left = successor) :
                                        (parent->right = successor);
                }
        }
        free (current);
        return;
  }

  void findElement(char *str) {
        struct BSTnode *temp = NULL;
        int flag = 0, res = 0;
        if (root == NULL) {
                printf("Binary Search Tree is out of station!!\n");
                return;
        }
        temp = root;
        while (temp) {
                if ((res = strcasecmp(temp->word, str)) == 0) {
                        printf("Word   : %s", str);
                        printf("Meaning: %s", temp->meaning);
                        flag = 1;
                        break;
                }
                temp = (res > 0) ? temp->left : temp->right;
        }
        if (!flag)
                printf("Search Element not found in Binary Search Tree\n");
        return;
  }

  void inorderTraversal(struct BSTnode *myNode) {
        if (myNode) {
                inorderTraversal(myNode->left);
                printf("Word    : %s", myNode->word);
                printf("Meaning : %s", myNode->meaning);
                printf("\n");
                inorderTraversal(myNode->right);
        }
        return;
  }

  int main() {
        int ch;
        char str[128], meaning[256];
        while (1) {
                printf("\n1. Insertion\t2. Deletion\n");
                printf("3. Searching\t4. Traversal\n");
                printf("5. Exit\nEnter ur choice:");
                scanf("%d", &ch);
                getchar();
                switch (ch) {
                        case 1:
                                printf("Word to insert:");
                                fgets(str, 100, stdin);
                                printf("Meaning:");
                                fgets(meaning, 256, stdin);
                                insert(str, meaning);
                                break;
                        case 2:
                                printf("Enter the word to delete:");
                                fgets(str, 100, stdin);
                                deleteNode(str);
                                break;
                        case 3:
                                printf("Enter the search word:");
                                fgets(str, 100, stdin);
                                findElement(str);
                                break;
                        case 4:
                                inorderTraversal(root);
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("You have entered wrong option\n");
                                break;
                }
        }
        return 0;
  }



  Output(C Program To Implement Dictionary Using Binary Search Tree):
  jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:old
  Meaning:not new

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:fan
  Meaning:enthosiastic devotiee of sports

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:ant
  Meaning:insect

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:candy
  Meaning:chocolate

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:ball
  Meaning:object used in cricket

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:pig
  Meaning:animal

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1   
  Word to insert:queen
  Meaning:women ruler

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:4
  Word    : ant
  Meaning : insect

  Word    : ball
  Meaning : object used in cricket

  Word    : candy
  Meaning : chocolate

  Word    : fan
  Meaning : enthosiastic devotiee of sports

  Word    : old
  Meaning : not new

  Word    : pig
  Meaning : animal

  Word    : queen
  Meaning : women ruler

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:2
  Enter the word to delete:queen

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:4
  Word    : ant
  Meaning : insect

  Word    : ball
  Meaning : object used in cricket

  Word    : candy
  Meaning : chocolate

  Word    : fan
  Meaning : enthosiastic devotiee of sports

  Word    : old
  Meaning : not new

  Word    : pig
  Meaning : animal

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:2
  Enter the word to delete:old

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:4
  Word    : ant
  Meaning : insect
  
  Word    : ball
  Meaning : object used in cricket

  Word    : candy
  Meaning : chocolate

  Word    : fan
  Meaning : enthosiastic devotiee of sports

  Word    : pig
  Meaning : animal

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:2
  Enter the word to delete:candy

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:4

  Word    : ant
  Meaning : insect

  Word    : ball
  Meaning : object used in cricket

  Word    : fan
  Meaning : enthosiastic devotiee of sports

  Word    : pig
  Meaning : animal

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:3
  Enter the search word:ant

  Word   : ant
  Meaning: insect
  
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:5



8 comments:

  1. if i want to keep database of every words i have entered for future use,how could it be?

    ReplyDelete
  2. use file handling and save elements of tree in a file in pre/post/inoder(called as serialsise and deserialise bst)and make a function start() which inserts all elements from file to bst as you open program.

    ReplyDelete
    Replies
    1. hey man!!! cud u please send me ur mail id??? i need help. it wud be of great help. please. i have to submit my annual project and i am struggling. so please do consider

      Delete
  3. 1. Write a program constructing Dictionary using Tree.
    (a) Words are defined with letter strings and meanings.
    (b) Make an English dictionary for more than 100 words.
    The Dict should be loaded from a text db.
    (ex) rose: meaning
    rise: meaning
    roller: meaning…….
    (c) After making the Dict tree, the program should retrieve and print meaning of a queried word.
    Please help in writing code

    ReplyDelete
  4. hello,
    i am trying to implement the dictionary using files. so that i have an already created database. can u help?

    ReplyDelete
  5. i really need help for my final review of my project....Can you please help???

    ReplyDelete
  6. I get an error which says "Linked error:Undefined symbol _strcasecmp in module."
    Help!

    ReplyDelete