Binary Search Tree

 

Binary Search Tree(BST)

Handwritten Notes- Click Here


A Binary Search Tree (BST) is a type of binary tree in which each node is arranged according to a specific ordering rule.

  • All values in the left subtree are smaller than the value of the root node.
  • All values in the right subtree are greater than the value of the root node.
  • The same rule is followed recursively for every node in the tree.

Because of this ordering, searching, insertion, and deletion can be performed efficiently.

Insertion:
                      Insertion is used to add a new value to the BST.
Steps
  • Start from the root.
  • Compare the new value with the current node.
  • If the new value is smaller, move to the left subtree.
  • If the new value is greater, move to the right subtree.
  • Continue until an empty position is reached.
  • Insert the new node at that position.

Let us construct a Binary Search Tree by inserting the following values one by one:
                                  50, 30, 70, 20, 40, 60, 80

Step 1: Insert 50
  • There is no node in the tree.
  • Therefore, 50 becomes the root node.
       50

Step 2: Insert 30
  • Compare 30 with 50.
  • 30 < 50, so 30 is placed on the left side of 50.
       50
      /
    30

Step 3: Insert 70
  • Compare 70 with 50.
  • 70 > 50, so 70 is placed on the right side of 50.
        50
      /    \
    30    70

Step 4: Insert 20
  • First compare 20 with 50.
  • 20 < 50, so move to the left.
  • Now compare 20 with 30.
  • 20 < 30, so 20 is placed on the left side of 30.
        50
       /    \
     30    70
    /
  20

Step 5: Insert 40
  • First compare 40 with 50.
  • 40 < 50, so move to the left.
  • Now compare 40 with 30.
  • 40 > 30, so 40 is placed on the right side of 30.
        50
       /  \
     30    70
    /    \
  20    40


Step 6: Insert 60
  • First compare 60 with 50.
  • 60 > 50, so move to the right.
  • Now compare 60 with 70.
  • 60 < 70, so 60 is placed on the left side of 70.
          50
       /      \
     30      70
    /   \       /
  20   40 60

Step 7: Insert 80
  • First compare 80 with 50.
  • 80 > 50, so move to the right.
  • Now compare 80 with 70.
  • 80 > 70, so 80 is placed on the right side of 70.

           50
       /        \
     30        70
    /  \        /    \
  20   40 60    80

Deletion

Deletion in a Binary Search Tree (BST) means removing a particular node while maintaining the BST property.

The deletion operation has three main cases:

  • Deletion of a leaf node
  • Deletion of a node with one child
  • Deletion of a node with two children

Case 1: Deletion of a Leaf Node
A leaf node is a node that does not have any children.

Example
Suppose we want to delete 20.
        50
       /    \
     30    70
    /  \
  20   40

Node 20 has no children.Remove 20 directly from the tree.

After Deletion
        50
       /   \
     30    70
       \
        40


Case 2: Deletion of a Node with One Child
 In this case, the node to be deleted has exactly one child.

Example
Suppose we want to delete 30

        50
       /    \
     30    70
       \
        40

Node 30 has only one child, which is 40. After deleting 30, node 40 takes the position of node 30.

After Deletion

        50
       /    \
     40    70


Case 3: Deletion of a Node with Two Children
In this case, the node to be deleted has two children.
  • Find the Inorder Successor(Value in right subtree)
  • Copy sucessor value to node
  • Delete Sucessor node
Example:
Suppose we want to delete 70.

          50
        /    \
      30      70
             /      \
            60   80

After Deletion

          50                                     
        /    \
      30      80
             /     \
            60   80




          50
        /    \
      30      80
             /     
            60  
       



Video Explanation




Comments

Post a Comment

Popular posts from this blog

Queue ADT

Image
  Queue ADT Handwritten Notes- Click Here A  Queue  is a linear data structure in which elements are inserted at one end and removed from the other end.( Insertion → Rear,  Deletion → Front )                                   ↓ FRONT                                 ↓ REAR A B C D E    A queue follows the FIFO (First In, First Out) principle. This means that the element inserted first is removed first. A  Queue can be implemented using: Array Linked List Basic  Queue  Operations: 1. Enqueue - used to insert  a new element into the queue. 2. Dequeue - used to remove an element from the queue. 3. Peek - used to view the first element without removing it. 4. isEmpty - checks whether the queue contains any elements. 5...
Read more

Entity-Relationship(ER) Model

Image
Entity-Relationship(ER) Model Handwritten Notes - Click Here The Entity-Relationship (ER) Model is a conceptual data model. It helps database designers understand the requirements of a system before creating the actual database tables . It describes the important objects in a system, their properties , and the relationships between them. The three basic concepts of the ER model are Entity Attribute Relationship Entity An entity can be any real-world object, person, place, or class about which we want to store information in a database. In a traditional ER diagram, an entity is represented by a rectangle .                        Example: Employee and Department An employee works for a department. Here, Employee and Department are entities , and Works For is the relationship between them. Weak Entity A weak entity is an entity that depends on another entity for its identification of existence. A weak entity is represen...
Read more

Normalization in DBMS,(1NF,2NF,3NF,BCNF,4NF,5NF)

Image
                      Normalization in DBMS Handwritten Notes - Click Here Normalization divides a large table into smaller , logically related tables and connects them using appropriate keys. The main purpose of normalization is to reduce unnecessary duplication of data and prevent problems that may occur when data is inserted, updated, or deleted. 1. First Normal Form (1NF) A relation is said to be in First Normal Form (1NF) when every attribute contains a single, indivisible value . Conditions of   1 NF Each cell must contain only one value. Multiple values should not be stored in the same field. ·         Example Customer Items Purchased Gowsi Rice, Dal Tamil Soap ·   Here, the Items Purchased column contains more than one value for Gowsi . ·   Therefore, the table is not in 1 NF . ...
Read more