Range Queries: Given an AVL tree show(using pseudocode) how to support the follo

Question

Range Queries: Given an AVL tree show(using pseudocode) how to support the following queries:
RangeCount(k1,k2): Count the number of keys in the AVL tree which are between k1 and k2 in O(logn) time.(Hint: Recall the size field)
RangeReport(k1,k2): List all the keys in AVL tree which are in between k1 and k2 in O(logn+output) time.
RangeMin(k1,k2): Consider the field data stored in each node to be an integer. Find the key with minimum data values among all the keys which are between k1 and k2 in O(logn) time. (Hint: Consider storing an additional field in the node structure and show how can this field be maintained during updates).

Explanation / Answer

1)range count int rangecount(tree *t,int k1,int k2){ if(t == k1 || t== k2) return 0; if (k1 >t.key) rangecount(t->right,k1,k2); if(k2 left,k1,k2); if(k1left,k1,k2); if(k2> t.key) return 1+ rangecount(t->right,k1,k2); } 2) void rangereport(tree *t,int k1,int k2){ if(t .key== k1 || t.key== k2) printf("%d",t.key); return; if (k1 >t.key) rangereport(t->right,k1,k2); if(k2 left,k1,k2); if(k1left,k1,k2); if(k2> t.key) printf("%d",t.key); rangereport(t->right,k1,k2); } 3) can you please elaborate it completely by giving example

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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