Data Structure and Algorithms
Dr. D. P. Acharjya
Professor, SCOPE
30-Mar-17 Dr. D. P. Acharjya 1
Binary Search Trees
A binary tree T is termed as binary search
tree if each node N of T satisfies the
following properties.
The value at N is greater than every value in the
left sub-tree.
The value at N is smaller than every value in the
right sub-tree.
A special kind of binary tree which is an
efficient structure to organize data for quick
search as well as quick update.
30-Mar-17 Dr. D. P. Acharjya 2
Illustrative Example
Root
Left Sub-tree Right Sub-tree
(Lesser) (Greater)
30-Mar-17 Dr. D. P. Acharjya 3
Searching (Item)
1. ptr=Root, Flag=False
2. While (ptr Null) and Flag = False
3. (i) Case: Item < [Link]
4. ptr = [Link]
5. (ii) Case: Item = [Link]
6. Flag = True
7. (iii) Case: Item > [Link]
8. ptr = [Link]
9. End Case
10. End while
Iteration hits when (n/2k)=1
11. If Flag = True, Print Ptr
Therefore 2k=n
12. Else Item not found.
i.e., k=log2(n)
30-Mar-17 Dr. D. P. Acharjya 4
Insert into a BST
1. ptr=Root, Flag=False
2. While (ptr Null) and Flag = False
3. (i) Case: Item < [Link]
4. ptr1 = ptr
5. ptr = [Link]
6. (ii) Case: Item > [Link]
7. ptr1 = ptr
8. ptr = [Link]
9. (iii) Case: Item = [Link]
10. Flag = True
11. End Case
12. End while 11
13. If Flag = True, Print Item exists
30-Mar-17 Dr. D. P. Acharjya 5
[Link] (ptr = null) then
15. new = Getnode(node)
16. [Link]=Item
17. [Link]=Null
18. [Link]=Null
[Link] ([Link] < Item)
20. [Link]=new
[Link]
22. [Link] = new
[Link]
30-Mar-17 Dr. D. P. Acharjya 6
Deleting a Node from BST
Case 1: N is the leaf node
Case 2: N has exactly one child.
Case 3: N has two children
35
Case 3 20 45 Case 2
16 29 42
24 33
27 Case 1
30-Mar-17 Dr. D. P. Acharjya 7
Case 1: Deleting a Leaf Node
35 35
20 45 20 45
16 29 42 16 29 42
24 33 24 33
For node 24: 27 Parent of node 27:
Left Address = Null Left Address = Null
Right Address = Not Null Right Address = Null
30-Mar-17 Dr. D. P. Acharjya 8
Case 2: Deletion Node has Exactly One Child
35 35
20 45 20 42
16 29 42 16 29
24 33 24 33
Parent of node 45: 35
27 27
Right Address of 35 =
Left Address of node 45
30-Mar-17 Dr. D. P. Acharjya 9
Case 3: Deletion Node has Two Childs
Succ(N): Node comes after N during inorder traversal of T
35 35
20 45 24 45
16 29 42 16 29 42
24 33 27 33
27
30-Mar-17 Dr. D. P. Acharjya 10
Algorithm of Deletion
1. ptr=Root, Flag=False
2. While (ptr Null) and (Flag = False) do
3. (i) Case: Item < [Link]
4. parent = ptr
5. ptr = [Link]
6. (ii) Case: Item > [Link] First part of the
7. parent = ptr Algorithm to find
8. ptr = [Link] the location.
9. (iii) Case: Item = [Link]
10. Flag = True
11. End Case
12. End while
13. If Flag = False, Print Item does not exists
14. Endif
30-Mar-17 Dr. D. P. Acharjya 11
15. If ([Link]=Null) and ([Link]=Null) then
16. Case = 1
17. Else if ([Link] Null) and ([Link] Null) then
18. Case = 3
19. Else
20. Case = 2
Second part of the
21. Endif
Algorithm to find
22. Endif
the case.
23. If (Case = 1) then
24. If ([Link] = ptr) then
25. [Link] = Null
26. Else [Link] = Null
27. Endif
28. Endif
30-Mar-17 Dr. D. P. Acharjya 12
29. If (Case = 2) then
30. If ([Link] = ptr) then
31. If ([Link]=Null) then
32. [Link] = [Link]
33. Else [Link] = [Link]
34. Endif
35. Else
36. If ([Link] = ptr) then
37. If ([Link]=Null) then
38. [Link] = [Link]
39. Else [Link] = [Link]
40. Endif
41. Endif
42. Endif
43. Endif
30-Mar-17 Dr. D. P. Acharjya 13
44. If (Case = 3) then
45. ptr1 = SUCC(ptr)
46. Item1=[Link]
47. BST DELETE (Item1)
48. [Link] = Item
49. Endif
1. ptr1=[Link]
2. If (ptr1 Null)
3. while ([Link] Null) do
Algorithm for SUCC(ptr)
4. ptr1=[Link]
5. End while
6. Endif
7. Return ptr of inorder successor
30-Mar-17 Dr. D. P. Acharjya 14
