Question

just need to answer the second question

3 AVL Trees Assume the following notation/operations on AVL trees. An empty AVL tree is denoted E. A non-empty AVL tree T has three attributes: . The key T.key is the root node's key. The left child T.left is T's left subtree, which is an AVL tree (possibly E). The right child T.right is T's right subtree, which is an AVL tree (possibly E) [3 marks] Describe an alternative version of the RANGECOUNT(T, lo, hi) function that runs in O(log n) time. . You do not have to write an algorithm in pseudo code to answer part (b) of this ques tion. We are expecting that you write a short paragraph or a short list of bullet points describing the important steps of the algorithm In your answer, you may augment the AVL tree notation/operations listed above. For example, you may include additional node attributes such as T.bal indicating the balance factor of the AVL tree, or T.sum indicating the sum of all key values in the tree with root T, and possibly even T.parent that points to the parent node of current root, T. If uetto do w pleaeat you ioan 3 AVL Trees Assume the following notation/operations on AVL trees. An empty AVL tree is denoted E. A non-empty AVL tree T has three attributes: . The key T.key is the root node's key. The left child T.left is T's left subtree, which is an AVL tree (possibly E). . The right child T.right is T's right subtree, which is an AVL tree (possibly E) (a) 5 marks] Write a function RANGECoUNT(T, lo, hi) to count the number of nodes in an AVL tree with root T, where the key value is in the range lo key S hi. Your algorithm should run in O(n) time, assuming that n is the number of nodes in the AVL tree, T. (b) 13 marksl Describe an alternative version of the RANGECoUNT (T, lo, hi) function that runs in O(log n) time . You do not have to write an algorithm in pseudo code to answer part (b) of this ques- tion. We are expecting that you write a short paragraph or a short list of bullet points describing the important steps of the algorithm . In your answer, you may augment the AVL tree notation/operations listed above. For example, you may include additional node attributes such as T.bal indicating the balance factor of the AVL tree, or T.sum indicating the sum of all key values in the tree with root T, and possibly even T.parent that points to the parent node of current root, T.I you elect to do so, please make sure that you explain your representation.

Answer 1

(2)AT each node of your AVL Tree, also keep count of the number of values in the tree that are lesser than its value .

Now, first find the node containing the value lo(or node with smallest value greater than lo). Get the count of values lesser than lo(or node with smallest value greater than lo) which has been stored at this node(say it n1).
This step is Log(n).

Now find the node containing the value hi(or node with larger value lesser than hi). Get the count of values lesser than hi(or node with larger value lesser than hi) which are stored in this node(say it n2). This step is also Log(n).

Print value n2-n1(will give number of node lies in[lo,hi]). Total complexity of this search is 2*Log(n) = O(Log(n)).