question archive VIT Chennai wants to maintain a database of all it's present students only, where the unique key of each student is the roll number
VIT Chennai wants to maintain a database of all it's present students only, where the unique key of each student is the roll number
Subject:Computer SciencePrice:2.87 Bought7
VIT Chennai wants to maintain a database of all it's present students only, where the unique key of each student is the roll number. The purpose of maintaining this database is to search for the information of a student as fast as possible. Moreover, the institute wants to update the database fast whenever a new student joins (insert operation) or whenever a student leaves (delete operation) the institute. For delete operation, assume that the location of the entry to be deleted has been given to you. For insert and search operations, assume that you are only given the roll number. Describe a data structure which enables VIT Chennai to search for a student in Θ(n) worst-case time, insert in Θ(1) worst-case time, and delete in Θ(1) worst-case time, if there are n entries in the database.
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
Answer:
Binary Search tree is best suitable data structure for this database. Because student id's are unique. If tree is skewed binary search tree and element exists in last position then it will take O(n) time for search operation. Otherwise, if tree is not skewed binary tree, then best case it will take O(1) time and O(log n) time in average case for search operation.
When insert operation is performing, once search operation will take constant amount of time i.e., O(1). And delete operation also will take constant amount of time i.e., O(1). When you are deleting leaf node or one child node then it will take constant amount of time and if it is deleting two children node, then also it will take constant amount of time.
