Binary Search Tree ( BST) and operations


A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree:

Properties of a Binary Search Tree:

Binary Tree Structure:
    Each node in the tree has at most two children: a left child and a right child.
    The left subtree of a node contains only nodes with values less than the node's value.
    The right subtree of a node contains only nodes with values greater than the node's value.

Ordering Property:
    For any node n, all nodes in its left subtree have values less than n, and all nodes in its right subtree         have values greater than n.

No Duplicates:
    A binary search tree does not allow duplicate values.

Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order, starting from an empty tree.


Operations on a Binary Search Tree:

Insertion:

To insert a new value into the tree, compare it to the current node's value.
If the value is less than the current node, go to the left subtree; if greater, go to the right subtree.
Repeat this process until an empty spot is found, then insert the new value as a leaf.

Insertion in a BST is also a straightforward operation. If we need to insert an element x, we first search for x. If x is present, there is nothing to do. If x is not present, then our search procedure ends in a null link. It is at this position of this null link that x will be included.

Algorithm
If the current node is null, create a new node with the given key and return it.
Compare the key with the current node's key.
If the key is less than the current node's key, recursively insert into the left subtree.
If the key is greater than the current node's key, recursively insert into the right subtree.
Return the modified node.

pseudo code:
struct Node* insert(struct Node* node, int key) {
    // Base case: if the tree is empty, create a new node
    if (node == NULL) {
        return createNode(key);
    }
    // Compare the key with the current node's key
    if (key < node->key) {
        // Recursively insert into the left subtree
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        // Recursively insert into the right subtree
        node->right = insert(node->right, key);
    }
    // Return the modified node
    return node;
}

Search:
    To search for a value in the tree, compare it to the current node's value.
    If the value is equal to the current node's value, the search is successful.
    If the value is less than the current node, search in the left subtree; if greater, search in the right subtree.

    Search is straightforward in a BST. Start with the root and keep moving left or right using the BST property. If the key we are seeking is present, this search procedure will lead us to the key. If the key is not present, we end up in a null link

    Algorithm
    If the root is null or the key is equal to the root's key, return the root (key found).
    If the key is smaller than the root's key, recursively search in the left subtree.
    If the key is greater than the root's key, recursively search in the right subtree.

    Pseudo code
    struct Node* search(struct Node* root, int key) {
        // Base cases: the key is not present or the root is null
        if (root == NULL || root->key == key) {
            return root;
        }

        // Key is smaller than the root's key, search in the left subtree
        if (key < root->key) {
            return search(root->left, key);
        }

        // Key is greater than the root's key, search in the right subtree
        return search(root->right, key);
    }

    Traversal:
    In-order Traversal: Visit the left subtree, then the current node, and finally the right subtree. This results in a sorted list of values.
    Pre-order Traversal: Visit the current node, then the left subtree, and finally the right subtree.
    Post-order Traversal: Visit the left subtree, then the right subtree, and finally the current node.

    Note that inorder traversal of a binary search tree always gives a sorted sequence of the values. This is a direct consequence of the BST property. This provides a way of sorting a given sequence of keys: first, create a BST with these keys and then do an inorder traversal of the BST so created.
      Minimum and Maximum:
    Find the minimum value by traversing the left subtree until a leaf is reached.
    Find the maximum value by traversing the right subtree until a leaf is reached.
Note that the highest valued element in a BST can be found by traversing from the root in the right direction all along until a node with no right link is found (we can call that the rightmost element in the BST).
The lowest valued element in a BST can be found by traversing from the root in the left direction all along until a node with no left link is found (we can call that the leftmost element in the BST).

pseudo code
int findMinimum(struct Node* root) {
    // Base case: the leftmost leaf node contains the minimum value
    while (root->left != NULL) {
        root = root->left;
    }
    return root->key;
}
int findMaximum(struct Node* root) {
    // Base case: the rightmost leaf node contains the maximum value
    while (root->right != NULL) {
        root = root->right;
    }
    return root->key;
}

Deletion:
To delete a node with a specific value:
    If the node is a leaf or has only one child, remove the node and replace it with its child.
    If the node has two children, find the node's in-order successor (the smallest node in its right subtree),      replace the node's value with the successor's value, and then delete the successor.


Deletion Example:







Note:Average case complexity of Search, Insert, and Delete Operations is O(log n), where n is the number of nodes in the tree.

If we repeatedly insert a sorted sequence of values to form a BST, we obtain a completely skewed BST. The height of such a tree is n - 1 if the tree has n nodes. Thus, the worst case complexity of searching or inserting an element into a BST having n nodes is O(n).

These operations ensure that a binary search tree maintains its properties, providing efficient access and manipulation of data with logarithmic time complexity for balanced trees. It's important to note that if the tree becomes unbalanced, the time complexity of operations may degrade to linear, and techniques like AVL trees or red-black trees can be used to maintain balance.


C Program Implementation BST Tree operations
/*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
struct Node {
    int key;
    struct Node* left;
    struct Node* right;
};
struct Node *root=NULL,*temp=NULL;

struct Node* createNode(int key) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct Node* insert(struct Node* node, int key) {
    // Base case: if the tree is empty, create a new node
    if (node == NULL) {
        return createNode(key);
    }

    // Compare the key with the current node's key
    if (key < node->key) {
        // Recursively insert into the left subtree
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        // Recursively insert into the right subtree
        node->right = insert(node->right, key);
    }

    // Return the modified node
    return node;
}
void inOrderTraversal(struct Node* node) {
    if (node != NULL) {
        // Traverse the left subtree
        inOrderTraversal(node->left);

        // Visit the current node
        printf("%d---",node->key);

        // Traverse the right subtree
        inOrderTraversal(node->right);
    }
}
void preOrderTraversal(struct Node* node) {
    if (node != NULL) {
        // Visit the current node
         printf("%d---",node->key);

        // Traverse the left subtree
        preOrderTraversal(node->left);

        // Traverse the right subtree
        preOrderTraversal(node->right);
    }
}
void postOrderTraversal(struct Node* node) {
    if (node != NULL) {
        // Traverse the left subtree
        postOrderTraversal(node->left);

        // Traverse the right subtree
        postOrderTraversal(node->right);

        // Visit the current node
         printf("%d---",node->key);
    }
}

struct Node* search(struct Node* root, int key) {
    // Base cases: the key is not present or the root is null
    if (root == NULL || root->key == key) {
        return root;
    }

    // Key is smaller than the root's key, search in the left subtree
    if (key < root->key) {
        return search(root->left, key);
    }

    // Key is greater than the root's key, search in the right subtree
    return search(root->right, key);
}

int findMinimum(struct Node* root) {
    // Base case: the leftmost leaf node contains the minimum value
    while (root->left != NULL) {
        root = root->left;
    }
    return root->key;
}
int findMaximum(struct Node* root) {
    // Base case: the rightmost leaf node contains the maximum value
    while (root->right != NULL) {
        root = root->right;
    }
    return root->key;
}
struct Node* inordersucc(struct Node* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}
// Function to delete a key from a BST
struct Node* deleteNode(struct Node* root, int key) {
    if (root == NULL) {
        return root;
    }

    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        struct Node* temp = inordersucc(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }

    return root;
}

int main()
{
    int op,key;
     do
    {
    printf("\n.menu\n1.insert\n2.preorder\n3.postorder\n4.inorder\n5.delete\n6.search\n7.Minimum\n8.Maximum\n9.exit\nenter option\n");
    scanf("%d",&op);
     switch(op)
     {
        case 1:printf("Enter the key:");
               scanf("%d",&key);
               if (root==NULL)
                root=insert(root,key);
                else
                insert(root,key);
                break;
        case 2:printf("Preorder Traversal\n");
               preOrderTraversal(root);
               break;
    case 3:printf("Postorder Traversal\n");
           postOrderTraversal(root);
           break;
    case 4:
            printf("Inorder traversal\n");
            inOrderTraversal(root);
            break;
   case 5:
          printf("Enter the key to delete:");
              scanf("%d",&key);
          root = deleteNode(root, key);
              printf("In-Order Traversal after deleting %d: ", key);
              inOrderTraversal(root);
          break;
   case 6:
          printf("Enter the key to search:");
              scanf("%d",&key);
          temp=search(root,key);
          if (temp==NULL)
           printf("Key not Found \n");
          else
           printf("key found \n");
          break;
  case 7:printf("Minimum key element is =%d\n",findMinimum(root));
         break;
  case 8:printf("Maximum key element is =%d\n",findMaximum(root));
         break;
      }
     }
   while(op!=9);
  return 0;
    
}

Example: University Questions

Show the structure of the binary search tree after adding each of the following values in the order 2,5,1,7,10,9,11,6.. What is the height of the created Tree. 



Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Stack

Image
A stack is a fundamental data structure in computer science and programming that follows the Last-In, First-Out (LIFO) principle . It is named "stack" because it resembles a stack of items, like a stack of plates or books, where you can only add or remove items from the top. Stacks are used for various purposes in programming and are essential in many algorithms and applications. Let's delve into the details of stacks: Key Operations:  A stack typically supports two primary operations: Push: This operation adds an element to the top of the stack. It is analogous to placing an item on top of the stack. Pop: This operation removes and returns the top element of the stack. It is like taking the top item off the stack. Additionally, stacks often provide the following operations: Peek (or Top): This operation retrieves the top element without removing it. It allows you to examine the top item without modifying the stack. IsEmpty: This operation checks if the stack is empty.
Read more

Quick Sort

Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a detailed algorithm for the Quick Sort algorithm: Algorithm: Quick Sort 1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance. 2,Partition the array into two sub-arrays:     Elements less than the pivot (left sub-array).     Elements greater than the pivot (right sub-array). 3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays. 4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted ar
Read more