Binary Search Tree(BST)
Binary search tree is either empty or satisfy rules.
- The value of a key in a left child or left subtree is less than the value of root.
- The value of a key in the right child or right subtree is greater than the value of the root.
Creation of Binary Tree
Create a Binary Search Tree
Data given : 40 60 50 33 55 11
Search a node from BST
- We begin by examining the root node.
- If the value equal to root, the search is successful.
- If the value is less than the root, search the left subtree.
- If the value is greater than the root, search the right subtree.
- The process is repeated until the value is found or the remaining subtree is NULL.
Algorithm for Searching Technique
- while(temp!=NULL)repeat 2 and 3
- Else if value data temp->temp->left
- Else temp=temp->right
Inserting a node in BST
Algorithm for inserting a node
- Start from the root node.
- If the value to be inserted is X, compare this value with the root node.
- Equal step because value already exists.
- Less-than value of root/choose left subtree
- Greater-than value of root /choose right subtree,
- Repeat step 2 until the leaf node is encountered where data to be inserted.
Binary Search tree deletion of element
- Search a node to remove.
- If node is found, call remove algorithm
Case 1:Node to be removed has no children
Case 2:Node to be removed has one child
Case 3:Node to be removed has two children
- Find the minimun value in the right subtree.
- Replace value of node to be removed with found minimimum value
- Apply remove to the right subtree to remove duplicacy