3-2 Binary Search Tres.ppt2-2 Dictionari

2-2 Dictionaries.ppt2-2 Dictionaries.ppt2-2 Dictionaries.ppt

1. Binary Search Tree
•A binary tree is referred as a binary search tree if
for any node n in the tree:
1.The node elements in the left subtree of n are
lesser in value than n.
2.The node elements in the right subtree of n are
greater than or equal to n.
•Binary search tree arranges its node elements in a
sorted manner.
•As the name suggests, the most important
application of a binary search tree is searching.

2. Binary Search Tree Contd….
•All the nodes in the left
subtree are less than the
nodes in the right subtree.
•While creating the binary
search tree the data is
systematically arranged.
•That means values at left
sub-tree < root node value <
right sub-tree values.
•The various operations
performed on a binary search
tree are:
1.Insert
2.Search
3.Delete

3. Binary Search Tree Insertion operation
•The insert operation involves
adding an element into the
binary tree.
•The location of the new
element is determined in
such a manner that insertion
does not disturb the sort
order of the tree.
•Eg: insert 39 in Binary
Search Tree

4. 1.If the current node is NULL
•Return a new node created with the specified value.
2. If the value is less than the key of the current node:
•Recursively call insertNode with the left subtree of the
current node and the value.
•Update the left child of the current node with the result of
the recursive call.
3. If the value is greater than the key of the current
node:
•Recursively call insertNode with the right subtree of the
current node and the value.
•Update the right child of the current node with the result of
the recursive call.
4. Return the current node (the root of the modified
tree).

5. Binary Search Tree search operation
1. If the root is NULL or the key of the root matches the target:
•Return the current root node.
2. If the target is greater than the key of the current root:
•Recursively call searchNode with the right subtree of the current root
and the target.
•Return the result of the recursive call.
3. If the target is smaller than the key of the current root:
•Recursively call searchNode with the left subtree of the current root
and the target.
•Return the result of the recursive call.
4. If the target is not found in the current subtree, return NULL.

6. Binary Search Tree deletion operation
•For deletion of any node from binary search tree there are three
1.Deletion of leaf node.
2.Deletion of a node having one child.
3.Deletion of a node having two children.
Deletion of leaf node
simply delete the node from the tree..

7. Binary Search Tree deletion operation
replace the target node with its child (single child) and then delete that child
node.

8. Binary Search Tree deletion operation
•Deletion of a node having two child.
•we will find the inorder successor of that node. And then replace the
node with the inorder successor. Then remove the inorder successor
from its original position.

9. 1. If the root is NULL:
1.Return NULL (base case for recursion).
2. If the value to be deleted (x) is greater than the key of the current root:
1.Recursively call delete with the right subtree of the current root and the value x.
2.Update the right child of the current root with the result of the recursive call.
3. If the value to be deleted (x) is smaller than the key of the current root:
1.Recursively call delete with the left subtree of the current root and the value x.
2.Update the left child of the current root with the result of the recursive call.
4. If the value to be deleted (x) is equal to the key of the current root:
1.If the current node has no child:
Free the current node.
Return NULL.
2. If the current node has one child:
Set temp to the non-null child of the current node.
Free the current node.
Return temp.
3. If the current node has two children:
Find the minimum node in the right subtree (temp).
Replace the key of the current node with the key of temp.
Recursively call delete with the right subtree of the current node and the key of temp.
5. Return the current node (the root of the modified tree).