(Problem C-9.34, page 397 of the text) Given a heap H and a key k, give an algor
ID: 648952 • Letter: #
Question
(Problem C-9.34, page 397 of the text) Given a heap H and a key k, give an algorithm to compute all the entries in H having keys less than or equal to k. For example, given the heap in figure 9.12a and query k=7, the algorithm should report the entries with keys 2, 4, 5, 6, and 7 (but not necessarily in this order). Your algorithm should run in time proportional to the number of entries returned, and should not modify the heap.
Figure 9.12: Two cases of updating the last node in a complete binary tree after operation insert or remove. Node w is the last node before operation insert or after operation remove. Node z is the last node after operation insert or before operation remove.
(Problem C-9.34, page 397 of the text) Given a heap H and a key k, give an algorithm to compute all the entries in H having keys less than or equal to k. For example, given the heap in figure 9.12a and query k=7, the algorithm should report the entries with keys 2, 4, 5, 6, and 7 (but not necessarily in this order). Your algorithm should run in time proportional to the number of entries returned, and should not modify the heap. Figure 9.12: Two cases of updating the last node in a complete binary tree after operation insert or remove. Node w is the last node before operation insert or after operation remove. Node z is the last node after operation insert or before operation remove.Explanation / Answer
class btree
{
private:
struct node
{
node*left;
char data;
node *right;
}*root;
public:
btree(char *a,int *l,int *r,int size);
void insert(int index);
static node* buildtree(char *a,int *l,int *r,int index);
void display();
~btree();
static void del(node *w);
static void dis(node *w);
};
//initialises data members
btree::btree(char *a,int *l,int *r,int size)
{
root=NULL;
arr=new char[size];
lc=new int[size];
rc=new int[size];
for(int i=0;i<size;i++)
{
*(arr+i)=*(a+i);
*(lc+i)=*(l+i);
*(rc+i)=*(r+i);
}
}
void btree::insert(int index)
{
root=buildtree(arr,lc,rc,index);
}
//builds binary tree
node *btree::buildtree(char *a,int *l,int *r,int index)
{
node *z=NULL;
if(index!=-1)
{
z=new node;
z->left=buildtree(a,l,r,*(l+index));
z->data=*(a+index);
z->right=buildtree(a,l,r,*(r+index));
}
return temp;
}
//deletes nodes of a binery tree
void btree::del(node *w)
{
if(w!=NULL)
{
del(w->left);
del(w->right);
}
delete w;
}
// calls del to deallocate memory
btree::~btree()
{
delete arr;
delete lc;
delete rc;
del(root);
}
//display
void btree::display(node *w)
{
dis(root);
}
btree:: inorder(node *w)
{
if(w!=NULL)
{
dis(w->left);
cout<<w->data<<" ";
dis(w->right);
}
}
void main()
{
int sz=sizeof(a);
btree bt(a,l,r,sz);
bt.insert();
bt.display();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.