Binary Search Tree
By-
Ms. Shabnam Makandar
Asst. Prof.
DYPIMCAM
DYPIMCAM, Akurdi, Pune 1
Binary Search Tree
• Values in left sub tree less thanparent
• Values in right sub tree greater than parent
• Fast searches in a Binary Search tree, maximum of log n
comparisons
31
21 40
10 22 35 42
DYPIMCAM, Akurdi, Pune 3
Binary Search Trees
• Examples
5
10
10
2 45
5 30 5 45
30
2 25 45 2 25 30
10
25
Binary search Not a binary
trees search tree
DYPIMCAM, Akurdi, Pune 5
Example Binary Searches
• search (root, 25 )
10 5
10 < 25, right 5 < 25, right
5 30 30 > 25, left 2 45 45 > 25, left
25 = 25, found 30 > 25, left
2 25 45 30
10 < 25, right
10 25 = 25, found
25
DYPIMCAM, Akurdi, Pune 6
EXAMPLE
Root
15
15>10-Left
10 20
15<20-Right
10>8-Left
10<12-Right 8 12 17 25
20>17-Left
20<25-Right 16
DYPIMCAM, Akurdi, Pune 7
Algorithm for Binary Search Tree
A) compare ITEM with the root node N of the tree
i) if ITEM<N, proceed to the left child of N.
ii) if ITEM>N, proceed to the right child of N.
B) repeat step (A) until one of the following occurs
i) we meet a node N such that ITEM=N, i.e. search is
successful.
ii) we meet an empty sub tree, i.e. the search is
unsuccessful.
DYPIMCAM, Akurdi, Pune 8
SEARCH AN ELEMENT IN BST
Root
bool Search( bstnode* root, data) 12
{
if (root==NULL) return false; 5 15
else if(root->data == data) return true;
else if(root->data <= data)
return Search(root->left, data); 3 7 13 17
else
return Search(root->right, data);
} 21
8 11 14
DYPIMCAM, Akurdi, Pune 9
Insertion in a Binary Search Tree
• Algorithm
1. Perform search for valueX
2. Search will end at node Y (if X not in tree)
3. If X < Y, insert new leaf X as new leftsubtree
for Y
3. If X > Y, insert new leaf X as new rightsubtree
for Y
DYPIMCAM, Akurdi, Pune 10
Insertion in a Binary Search Tree
• Insert ( 20 )
10 10 < 20, right
30 > 20, left
5 30
25 > 20, left
2 25 45 Insert 20 on left
20
DYPIMCAM, Akurdi, Pune 11
Insertion in a Binary Tree
40, 60, 50, 33, 55, 11
40
Insertion in a Binary Tree
40, 60, 50, 33, 55, 11
40
60
DYPIMCAM, Akurdi, Pune 13
Insertion in a Binary Tree
40, 60, 50, 33, 55, 11
40
60
50
DYPIMCAM, Akurdi, Pune 14
Insertion in a Binary Tree
40, 60, 50, 33, 55, 11
40
33 60
50
DYPIMCAM, Akurdi, Pune 15
Insertion in a Binary Tree
40, 60, 50, 33, 55, 11
40
33 60
50
55
DYPIMCAM, Akurdi, Pune 16
Insertion in a Binary Tree
40, 60, 50, 33, 55, 11
40
33 60
11 50
55
DYPIMCAM, Akurdi, Pune 17
DLELETE A NODE FROM BST
Root
12
5 15
There are three items to delete.
Case 1: No Child
Case 2: One Child 3 7 13 17
Case 3: Two Child
14 22
6 9
DYPIMCAM, Akurdi, Pune 18
CASE 1: NO CHILD
Root
12
5 15
Remove to reference of the Node
From it’s parent &
3 7 13 17
Return NULL
23
6 9 14
DYPIMCAM, Akurdi, Pune 19
CASE 2: ONE CHILD
Root
12
5 15
Find the Node to Delete
Link it’s parent to this only child.
Remain attached to the tree. 3 7 13 17
24
6 9 14
DYPIMCAM, Akurdi, Pune 20
CASE 3: TWO CHILD
Root
12
Two way to delete. 5 15
1.
Find minimum in right
3 7 13 17
Copy the value in targetted node
Delete duplicate from right subtree.
25
6 9 14
DYPIMCAM, Akurdi, Pune 21
CASE 3: TWO CHILD
Root
12
5 15
2.
Find maximum in left
Copy the value in targetted node 3 7 13 17
Delete duplicate from left-subtree.
26
6 9 14
Best PDF Encryption Reviews DYPIMCAM, Akurdi, Pune 22
