State what Tree would be best used under each circumstance (Please Provide Expla

Question

State what Tree would be best used under each circumstance (Please Provide Explanation).

b. The NSA is ranking files of the million or so people of interest by their perceived threat level. They also want to be able to deal with the top. Each file is about I kilobytes New people and threats may be added. c) A competing software to the above lets the NSA search for any person of interest, and then examines their records. Note the often a group of people are suspicious for a while and then are ignored. Thus they are accessed often for a period and then are rarely accessed unless they are associate with a new threat. There are about 1 million files, each about 1 kilobyte in size. This software supports insertion deletion and find. d) The NSA has made a software application for the phones of their agents. This app stores text information on the top 1000 or so persons of interest, on their phone, and allows the agent to access this information to get background on people with whom he/she may come in contact. The tiles arc about 10 k.

Explanation / Answer

b. We can use max heap for first one as we can always keep maximum value on the top of tree . A Heap data structure is a Tree based data structure that satisfies the HEAP Property “If A is a parent node of B then key(A) is ordered with respect to key(B) with the same ordering applying across the heap. n a max heap the key(A) will be greater than Key(B). SO in this case , we can always maximum threat on top and can be easily tracked.

C. We can use AVL tree for this case as it is easy to delete less frequently and hence less rotations. Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree

D. We can use Max heap fr this one too , as we can store top n number of records as per our interest and can be retrieved easily as records are stored in order from maximum interest to least interest.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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