A city archive converts paper maps into digital records. Each record has a map ID, district name, scan date and file pointer. The records are stored in a bi...
Question 1 Report
A city archive converts paper maps into digital records. Each record has a map ID, district name, scan date and file pointer. The records are stored in a binary search tree using map ID as the key. An archivist enters IDs in the order 60, 40, 85, 30, 50 and 75. The program must search for ID 75 and then delete ID 30 after a duplicate scan is discovered. The archive manager needs the tree to remain valid after the delete command.
(a) Explain the route used to find ID 75. [2]
(b) When deleting ID 30, explain why this is simpler than deleting ID 40. [2]
(c) Explain one benefit of using a record rather than storing only map IDs in the tree. [2]
Answer Details
(a) Begin at 60. Since 75 is greater than 60, follow the right branch. Then compare 75 with 85; since 75 is less than 85, follow the left branch to 75. [2]
(b) ID 30 is a leaf node, so it has no children. Its parent's pointer can simply be changed to NULL. ID 40 has children, so deleting it would require reconnecting or replacing nodes to preserve the binary-search-tree structure. [2]
(c) A record keeps the district, scan date and file pointer associated with its map ID. Once the node is located, the program can retrieve all relevant map details rather than only the ID. [2]
Download The App On Google Playstore
Everything you need to excel in your exams
