Read carefully and answer the questions that follow: Suppose we want to create a

Question

Read carefully and answer the questions that follow:

Suppose we want to create an address book which contains names, phone numbers, emails, and other personal information. In the question below, give support to your answer based on the typical operations (for example, finding a person by his/her email) you might use. Explain why the algorithm and/or data structure you use gives a good tradeoff between memory use and runtime complexity. The question below could require nested data structures.

Suppose you have friends who live in various different cities. What data structure could be useful to find these friends efficiently. You can suppose that each friend has a city field associated with them. Give reasoning to your answer. Think about search engines for this question.

Explanation / Answer

Solution:-

The above given problem can be solved by an efficient data structure implementation. For this problem we can implement a Binary search tree to store the data.

Binary search tree is store data in sorted form. For the given problem the data will be searched by city names. So the data is stored in alphabetical order in binary search tree. Binary search tree has the property that the value in left subtree is less than root value and right subtree value is greater than root. So the data structure is automatically sorted. It is an efficient algorithm in terms of space and time complexity.

While searching the friends by the city names the city names used as the key. List is sorted and applying the binary search algorithm to search the entry it's complexity is O(log n). Which is an average case complexity. Do it is efficient in terms of time complexity. In terms of space, it can be stored in form of array in consecutive locations in memory.

So for the given problem the binary search tree is an better alternative. There are many efficient data structures are exists and can be used. But binary search tree is efficiently insert data, remove and search the required data.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.