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)

[edit] RBST versus treap

According to Martinez and Roura, RBST has a random priority based on subtree size, while a treap has a random priority that does not depend on subtree size. MegaHasher 01:14, 6 August 2007 (UTC)