Question

Tree & Hash Table & Heap

Use the following integer keys 73, 58, 91, 42, 60, 130, 64, 87 to perform the followings:

a) Binary Search Tree

- Draw a binary search tree

- Retrieve the integers keys in post-order

- Retrieve the integers keys in pre-order

- Draw a binary search tree after node 58 is deleted

b) Create a Hash Table using the methods described below. Show the final array after all integer keys are inserted. Assumes that the Hash Table is implemented using an array of size 13. The integer keys are
73, 58, 91, 42, 60, 130, 64, 87

• Linear Probing
  

Numbers
Index	0	1	2	3	4	5	6	7	8	9	10	11	12

• Quadratic Probing
  

Numbers
Index	0	1	2	3	4	5	6	7	8	9	10	11	12

• Double Hashing
  Constant = 5
  

Numbers
Index	0	1	2	3	4	5	6	7	8	9	10	11	12

b) Insertion and deletion in a Heap. Show the final array after all insertion and deletion are finished.

• Heap (Insert)
  

Numbers
Index	0	1	2	3	4	5	6	7	8	9	10	11	12

                Draw a binary tree from the heap array

Heap (Remove)

Numbers
Index	0	1	2	3	4	5	6	7	8	9	10	11	12

                Draw a binary tree from the heap array after the removal is performed

Answer 1

ら73, sg , 9 2, 60, l 30, 64,8 า Inset 13 Inset 13O 13 Insert S 5 8 73 130 73 13 .9ne止此 73 S8 13 Inpeus 60 3o 2)(6o 73 2) (60

Pre Oder traversal soot -Reft Subtree - Right Sulstrec since S8, has to chidren ereplace-the ncole cu m left most child - (omest Child of ke s.bree 13 23 13 60 8

Numbeus 13 60 64 nder O Quadratic prolking 60 9ntat 120130 13 Co lisn

13 um 130 73 60 87 6 Derbe tHasin 21 Constant iver as

Please post remaining as another question

Please upvote