Question

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 ≤ hi. Your algorithm should run in O(n) time, assuming that n is the number of nodes in the AVL tree, T.
(b) [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 question. 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 you elect to do so, please make sure that you explain your representation.

Answer 1

SOLUTION TO PART A

THE idea is very simple travel through each node of the tree .. if the key is in between the range the rise the count...

int Range(node *T, int lo, int hi)
{
if (!T) return 0;
if (T->key == hi && T->key == lo)
return 1;
if (T->key <= hi && T->key >= lo)
return 1 + Range(T->left, lo, hi) +
Range(T->right, lo, hi);
  
else if (T->key < lo)
return Range(T->right, lo, hi);
  
else return Range(T->left, lo, hi);
}

SOLUTION TO PART B

let a=no of nodes with a key greater than lo

b= no of nodes with a key greater than hi

then c= a-b ; // gives the count of required no of nodes between the range of lo and hi

int Range1( Node* T, int x)
{
int res = 0;
while (T != NULL) {
int desc = (T->right != NULL) ? T->right->desc : -1;
if (T->key > x) {
res = res + desc + 1 + 1;
T = T->left;
}
       else if (T->key < x)
T = T->right;
else {
res = res + desc + 1;
break;
}
}
return res;
}

int Range(node*T,int lo,int hi){

int a=Range1(T,lo-1);

int b=Range1(T,hi);

return a-b;

}