Talk:Randomized binary search tree

From Wikipedia, the free encyclopedia

[edit] Overkill?

Implementing randomized binary search trees as treaps is a bit of overkill. I learned to make them by simply calculating the odds that the element being inserted would be a root in a random binary tree of that size that was randomly arranged (i.e. 1/number_of_nodes), checking that against a random number and inserting at the root 1/nth of the time, otherwise doing that whole procedure again at the appropriate child.

It requires generating some more random numbers, and I'm not sure off the top of my head whether the inserting at root is equivalent to rotating into place, but it saves you keeping track of priorities. ^L_Wizard @ 10:03, 10 October 2006 (UTC)