Problem 7 Below is a list of data structures and an application. Select two data
ID: 642066 • Letter: P
Question
Problem 7
Below is a list of data structures and an application. Select two data structures that you think would be the most useful for the particular application. Of the two data structures that you selected, pick the better of the two and explain why it is better for that particular application. State all relevant assumptions.
Data Structures:
Simple Array
Single Linked list
Binary Tree
Binary Search Tree
AVL Tree
B-Tree
Robot Requests: You have a robot that receives job requests from the Internet. These requests need to be processed based on their priority. The most urgent job needs to be executed first and then deleted. Choose a data structure to organize these jobs, support job insertion, the most urgent job extraction and deletion.
Explanation / Answer
A BST is best for this application , i.e. priority based.
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for an key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip over half of the tree, so that each lookup/insertion/deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an unsorted array, but slower than the corresponding operations on hash tables