perfect-ring's blog

How to generate random balanced tree ?
By perfect-ring, history, 14 months ago, In English

I was making a problem in which I have assumed that the tree is balanced (height of the tree is $$$O(logN)$$$). How to generate a random balanced tree $$$?$$$

  • Vote: I like it
  • +15
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
14 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Here is an idea (that may not work).

Create an AVL — or any data structure that is backed by a self balancing binary tree.

Generate n random numbers and insert them one by one into said tree.

This will result in a binary tree that should be random enough for most uses.

→ Reply
»
14 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I guess you can simply generate an array of ancestors as follows:

$$$p_k = \text{rng()} \mod k$$$, where $$$k \in [1, n)$$$

Then build a zero indexed tree with edges $$$(i, p_i)$$$. It can be proved that height of the tree is $$$O(\log(n))$$$. You can additionally shuffle vertices to get random enumeration of them as well.

→ Reply