can not make out the code fragment

[johndoe444]

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?

[mrnutty]

what is link a typedef of ?

(h->N+1)

is N the number of nodes?

[vmanes]

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.

[johndoe444]

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:
link joinR(link a, link b)
{
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)
{ int N = head->N;
[B]if (rand()/(RAND_MAX/(N+b.head->N)+1) < N)[/B]head = joinR(head, b.head);
else head = joinR(b.head, head); }

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

if (rand()/(RAND_MAX/(N+b.head->N)+1) < N)

I am not sure I understand its purpose. Does they want to calculate

rand()/RAND_MAX < N/(N+b.head->N+1)

Not sure what the purpose of 1 in the expression.

Thanks.