The following is the randomized Binary search tree insertion algorithm mentioned in sedgewick's book.

"This function makes a randomized decision whether to use the root insertion method of Program 12.13 or the standard insertion method of Program 12.8. In a random BST,
each of the nodes is at the root with equal probability; so we get random trees by
putting a new node at the root of a tree of size N with probability 1/(N + 1)."

``````void insertR(link& h, Item x)
{
if (h == 0) { h = new node(x); return; }
[B]if (rand() < RAND_MAX/(h->N+1))
{ insertT(h, x); return; }[/B]
if (x.key() < h->item.key())
insertR(h->l, x);
else insertR(h->r, x);
h->N++;
}``````

I failed to understand the statement in bold ie the one where randomization is taking place:

rand() < RAND_MAX/(h->N+1)

Can anybody explain what does that mean?

what is link a typedef of ?

(h->N+1)

is N the number of nodes?

if (rand() < RAND_MAX/(h->N+1))

If you read the work closely, you know that N is the data member of the node that counts its descendants. Lets use N=10 as an example. The probability of assigning new node at the root will be 1/(10+1), or 1/11 (approx. 9%). To determine that probability in the code, we're looking for a value returned by rand( ) that is just 1/11th of the possible values. RAND_MAX is a system constant that is the largest possible random value - let's say 32767. Divide that by 11, if the particular random value generated is less than 32767/11, the node gets inserted at root, otherwise it will (in the other 91% of cases) be assigned to the appropriate left or right node.

Furthermore, he also mentions this:

"This function uses the same method as Program 12.17, except that it makes a
randomized, rather than an arbitrary, decision about which node to use for the root in a
combined tree, using probabilities that ensure that each node is equally likely to be the
root. The private member function fixN updates b->N to be 1 plus the sum of the
corresponding fields in the subtrees (0 for null trees)."

``````private:
{
if (a == 0) return b;
if (b == 0) return a;
insertR(b, a->item);
b->l = joinR(a->l, b->l);
b->r = joinR(a->r, b->r);
delete a[;;] fixN(b); return b;
}
public:
void join(ST<Item, Key>& b)

This part, I am not sure whether this expression is right or not: