0

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?

*Edited 7 Years Ago by johndoe444*: n/a