// Bottom-up red-black tree implementation without deletions,
// so free() does not appear.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "RB.h"

link z,head; // Pointers to sentinel and root
Item NULLitem=(-9999999); // Data for sentinel

int trace=0; // Controls trace output for insert

link NEW(Item item, link l, link r, int N)
// Allocates and fills in a node
{
link x = malloc(sizeof *x);
x->item = item;
x->l = l;
x->r = r;
x->red = 1;
x->N = N;
return x;
}

void STinit()
{
// Root/sentinel (head/z) is always black
head = (z = NEW(NULLitem, 0, 0, 0));
head->red=0;
}

Item searchR(link h, Key v)
// Recursive search for a key
{
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 i)
// Returns the ith smallest key where i=1 returns the smallest
// key. Thus, this is like flattening the tree inorder into an array
// and applying i as a subscript.
{
int r = h->l->N+1;

if (h == z)
{
printf("Impossible situation in selectR\n");
STprintTree();
exit(0);
}
if (i==r)
return h->item;
if (i<r)
return selectR(h->l, i);
return selectR(h->r, i-r);
}

Q1: Given the following recurrence prove using induction that ð‘†(...

Q1: Given the following recurrence prove using induction that ð‘†(...