Question

3. Design a data structure D that can store integers. The data structure should be ale to store nent can appear multiple times. The da the following operations in O(log n) time, where n is the number of distinct integers stored in D . add(x): Adds/inserts integer a into D. Even if belongs to D, z should still be added .frequencyx) Nuber of times r appears in D search(x): Returns true if is in D order (y): Number of elements in D that are larger than y. The element y may or may not be in D If you are using BST and would like to balance the tree, you may simply write balance and assume that this operation will take O(log n) time. Analyze the worst-case run time of the operations.

Show steps. Please.

Answer 1

Consider a self-balancing binary tree which is represented as an AVL tree.

The tree become a skewed tree, if the assumed tree is a self-balancing binary tree.

add(x):

• The insertion of the element in the BST, search for an empty space to keep the element there.
• To insert the element in the tree, compare the element with the root node first.
• If the value to be inserted is less than the root node, then move the insertion operation to the left tree of the root node.
• Otherwise, go to the right subtree for insertion.
• Keep doing the same operation, while getting the NULL value, place the value to be inserted in that place.

Since, the tree is a self-balancing tree which is an AVL tree whose height is O (log n).

Therefore, the time complexity of the insertion is O (Log n).

frequency(x):

The frequency count will be done by start the traversal from the left to the right and update the count whenever get the element.

The time complexity would be O (right – left + 1) or O (n).

A more efficient approach can be used which is unordered_map in c++.

This will take time of O (Log n).

search (x):

• Compare the element with the root node and traverse the part according to the method discussed above in Add(x).
• And when the element is found, return true.
• If the value is returned as -1, then it means the element which is searched is not found in the tree. So, return false.
• The time taken to search an element in the tree is log n.

Therefore, the complexity of the search is log n.

order (x):

Create a field as “less_nodes” to store the number of nodes which are less than y.

To count of the elements which are greater than the element y, three cases will be there:

Case 1: In this case, if the value y is greater than the root node. Then, traverse the right subtree.

Case 2: If the value of y is less than the root node, increase the count by the number of successor of the right child. The successor is those of the current nodes.

Also, increase the count by 2, one for itself and the other is due to the current node.

After that move to the left subtree.

Case 3: If the value of y is equal to the root node, add the value to the field less_nodes and add 1. Also, check whether the right child exist or not.

The time complexity would be O (Log n) as n represents the number of nodes in the tree.