I am writing a function to search whether a key is found in the Red-Black Tree. The function STsearchBatch is supposed to do this. the arguments are int num(the total number of keys that we want to search, Key *in (array of Keys that are to be searched) and Item *out( where we store result if found or not. We store NULLitem in it to show not found) The given is a partial code which creates the red-black tree.
My question is that where do I begin to search ? How do I access this tree that is being created ? Also we have to use binary search and pointer arithmetic. I am sorry that I am asking a big homework help but I cannot begin this assignment to ask smaller suitable questions.
#include <stdlib.h>
#include <stdio.h>
#include "topdownRB.h"
link z,head; Item NULLitem=(-9999999);
int trace=0; void STsearchBatch(int num,Key *in,Item *out)
{
};
void STselectBatch(int num,int *in,Item *out){};
void STinvSelectBatch(int num,Key *in,int *out){};
link NEW(Item item, link l, link r, int N)
{
link x = malloc(sizeof *x);
x->item = item;
x->l = l;
x->r = r;
x->red = 1;
x->N = N;
return x;
}
void STinit()
{
head = (z = NEW(NULLitem, 0, 0, 0));
}
Item searchR(link h, Key v)
{
Key t = key(h->item);
if (h == z)
return NULLitem;
if (eq(v, t))
return h->item;
if (less(v, t))
return searchR(h->l, v);
return searchR(h->r, v);
}
Item STsearch(Key v)
{
return searchR(head, v);
}
Item selectR(link h, int k)
{
int t = h->l->N;
if (h == z)
{
printf("Impossible situation in selectR\n");
STprintTree();
exit(0);
}
if (t > k)
return selectR(h->l, k);
if (t < k)
return selectR(h->r, k-t-1);
return h->item;
}
Item STselect(int k)
{
if (k<0 || k>=head->N)
{
printf("Range error in STselect() k %d N %d\n",k,head->N);
exit(0);
}
return selectR(head, k);
}
int invSelectR(link h, Key v)
{
Key t = key(h->item);
int work;
if (h==z)
return -1; if (eq(v, t))
return h->l->N;
if (less(v, t))
return invSelectR(h->l,v);
work=invSelectR(h->r,v);
if (work==(-1))
return -1; return 1 + h->l->N + work;
}
int STinvSelect(Key v)
{
return invSelectR(head,v);
}
void fixN(link h)
{
h->N=h->l->N + h->r->N + 1;
}
link rotR(link h)
{
link x = h->l;
h->l = x->r;
x->r = h;
x->N = x->r->N;
fixN(x->r);
return x;
}
link rotL(link h)
{
link x = h->r;
h->r = x->l;
x->l = h;
x->N = x->l->N;
fixN(x->l);
return x;
}
link rsRBinsert(link h, Item item, int sw)
{
Key v = key(item);
if (h == z)
return NEW(item, z, z, 1);
if ((h->l->red) && (h->r->red))
{
h->red = 1;
h->l->red = 0;
h->r->red = 0;
}
if (less(v, key(h->item)))
{
h->l = rsRBinsert(h->l, item, 0);
if (h->red && h->l->red && sw)
h = rotR(h);
if (h->l->red && h->l->l->red)
{
h = rotR(h);
h->red = 0;
h->r->red = 1;
}
}
else
{
h->r = rsRBinsert(h->r, item, 1);
if (h->red && h->r->red && !sw)
h = rotL(h);
if (h->r->red && h->r->r->red)
{
h = rotL(h);
h->red = 0;
h->l->red = 1;
}
}
fixN(h);
return h;
}
void extendedTraceOn()
{
trace=2;
}
void basicTraceOn()
{
trace=1;
}
void traceOff()
{
trace=0;
}
void tracePrint(char *s,link h)
{
if (trace) {
if (h==z)
printf("%s at sentinel\n",s);
else
printf("%s at %d\n",s,key(h->item));
}
}
link RBinsert(link h, Item item, int sw)
{
Key v = key(item);
link before;
tracePrint("Down",h);
if (h == z)
return NEW(item, z, z, 1);
if ((h->l->red) && (h->r->red)) {
tracePrint("Color flip",h);
h->red = 1;
h->l->red = 0;
h->r->red = 0;
if (trace==2)
STprintTree();
}
if (less(v, key(h->item)))
{
tracePrint("Insert left",h);
before=h->l;
h->l = RBinsert(h->l, item, 0); if (trace==2 && before!=h->l) STprintTree();
if (h->l->red) {
if (h->red)
if (sw) {
tracePrint("Case ~1",h);
h = rotR(h); }
else
;
else if (h->l->l->red) {
tracePrint("Case 2",h);
h = rotR(h);
h->red = 0;
h->r->red = 1;
}
}
}
else
{
tracePrint("Insert right",h);
before=h->r;
h->r = RBinsert(h->r, item, 1); if (trace==2 && before!=h->r) STprintTree();
if (h->r->red) {
if (h->red)
if (!sw) {
tracePrint("Case 1",h);
h = rotL(h); }
else
;
else if (h->r->r->red) {
tracePrint("Case ~2",h);
h = rotL(h);
h->red = 0;
h->l->red = 1;
}
}
}
fixN(h);
tracePrint("Up",h);
return h;
}
void STinsert(Item item)
{
head = RBinsert(head, item, 0);
if (head->red)
printf("red to black reset has occurred at root!!!\n");
head->red = 0;
}
void checkRed(link h,int redParent)
{
if (redParent && h->red)
{
printf("Red property problem at %d\n",key(h->item));
STprintTree();
exit(0);
}
if (h==z)
return;
checkRed(h->l,h->red);
checkRed(h->r,h->red);
}
int leftPathBlackHeight(link h)
{
if (h==z)
return !(h->red);
return leftPathBlackHeight(h->l) + !(h->red);
}
void checkBlack(link h,int blackCount)
{
if (h==z) {
if (blackCount==!(h->red))
return;
else {
printf("Black height problem!\n");
STprintTree();
exit(0);
}
}
if (h->red)
{
checkBlack(h->l,blackCount);
checkBlack(h->r,blackCount);
}
else
{
checkBlack(h->l,blackCount-1);
checkBlack(h->r,blackCount-1);
}
}
Key lastInorder;
void checkInorder(link h)
{
if (h==z)
return;
checkInorder(h->l);
if (less(h->item,lastInorder))
{
printf("Inorder error\n");
STprintTree();
exit(0);
}
lastInorder=key(h->item);
checkInorder(h->r);
}
int checkN(link h)
{
int work;
if (h==z)
{
if (h->N!=0)
{
printf("Count for sentinel is %d, should be 0\n",h->N);
STprintTree();
exit(0);
}
}
else
{
work=checkN(h->l) + checkN(h->r) + 1;
if (h->N!=work)
{
printf("Count for key %d is %d, should be %d\n",key(h->item),h->N,work);
STprintTree();
exit(0);
}
}
return h->N;
}
void verifyRBproperties()
{
int lpbHeight;
if (head->red)
printf("Root is not black!\n");
if (z->red)
printf("Sentinel is not black!\n");
lastInorder=(-99999999);
checkInorder(head);
checkRed(head,0);
lpbHeight=leftPathBlackHeight(head);
checkBlack(head,lpbHeight);
checkN(head);
}
void printTree(link h,int depth,int bhAbove)
{
int i,bhBelow;
if (h==z)
{
if (bhAbove!=1)
{
for (i=0;i<depth;i++)
printf(" ");
printf("Black-height issue detected at sentinel\n");
}
return;
}
if ((h->red))
bhBelow=bhAbove;
else
bhBelow=bhAbove-1;
printTree(h->r,depth+1,bhBelow);
for (i=0;i<depth;i++)
printf(" ");
if (h->red)
printf("[%d %d %d]\n",key(h->item),h->N,bhBelow);
else
printf("(%d %d %d)\n",key(h->item),h->N,bhBelow);
printTree(h->l,depth+1,bhBelow);
}
void STprintTree()
{
printTree(head,0,leftPathBlackHeight(head));
}
void fixAllN(link h)
{
if (h->l)
fixAllN(h->l);
else
h->l=z;
if (h->r)
fixAllN(h->r);
else
h->r=z;
fixN(h);
}
void cleanUpUnbalanced(link h)
{
fixAllN(h);
head=h;
z->red=0;
verifyRBproperties();
}
What I have tried:
I understand what I am supposed to do in terms of searching.