Scribd
Upload
46 views

Binary Search Tree

The document discusses binary search trees (BSTs) and algorithms for searching, inserting, and deleting nodes from a BST. It defines the properties of a BST, provides an example tree, and explains how to search for a node in O(log n) time. Insertion and deletion of nodes are described as multi-step processes involving finding the location of the node and handling different cases depending on the number of child nodes. Pseudocode is provided for the key algorithms.

Uploaded by

Sanjay Gowd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
46 views

Binary Search Tree

The document discusses binary search trees (BSTs) and algorithms for searching, inserting, and deleting nodes from a BST. It defines the properties of a BST, provides an example tree, and explains how to search for a node in O(log n) time. Insertion and deletion of nodes are described as multi-step processes involving finding the location of the node and handling different cases depending on the number of child nodes. Pseudocode is provided for the key algorithms.

Uploaded by

Sanjay Gowd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

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 < ptr.Data
4. ptr = ptr.Lchild
5. (ii) Case: Item = ptr.Data
6. Flag = True
7. (iii) Case: Item > ptr.Data
8. ptr = ptr.Rchild
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 < ptr.Data
4. ptr1 = ptr
5. ptr = ptr.Lchild
6. (ii) Case: Item > ptr.Data
7. ptr1 = ptr
8. ptr = ptr.Rchild
9. (iii) Case: Item = ptr.Data
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


14.If (ptr = null) then
15. new = Getnode(node)
16. new.Data=Item
17. new.Lchild=Null
18. new.Rchild=Null
19.If (ptr1.Data < Item)
20. ptr1.Rchild=new
21.Else
22. ptr1.Lchild = new
23.Endif

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 < ptr.Data
4. parent = ptr
5. ptr = ptr.Lchild
6. (ii) Case: Item > ptr.Data First part of the
7. parent = ptr Algorithm to find
8. ptr = ptr.Rchild the location.
9. (iii) Case: Item = ptr.Data
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 (ptr.Lchild=Null) and (ptr.Rchild=Null) then
16. Case = 1
17. Else if (ptr.Lchild Null) and (ptr.Rchild 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 (parent.Lchild = ptr) then
25. parent.Lchild = Null
26. Else Parent.Rchild = Null
27. Endif
28. Endif

30-Mar-17 Dr. D. P. Acharjya 12


29. If (Case = 2) then
30. If (parent.Lchild = ptr) then
31. If (ptr.Lchild=Null) then
32. parent.Lchild = ptr.Rchild
33. Else Parent.Lchild = ptr.Lchild
34. Endif
35. Else
36. If (parent.Rchild = ptr) then
37. If (ptr.Lchild=Null) then
38. parent.Rchild = ptr.Rchild
39. Else Parent.Rchild = ptr.Lchild
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=ptr1.Data
47. BST DELETE (Item1)
48. ptr.Data = Item
49. Endif

1. ptr1=ptr.Rchild
2. If (ptr1 Null)
3. while (ptr1.Lchild Null) do
Algorithm for SUCC(ptr)
4. ptr1=ptr1.Lchild
5. End while
6. Endif
7. Return ptr of inorder successor

30-Mar-17 Dr. D. P. Acharjya 14

You might also like