狗家挂经

茶园葱绿 发表于 2018-3-14 03:33
是要你随机生成一棵树，所有可能的树出现的可能性要是一样的

哦哦，这样啊， 感觉生成一棵树就像做partition一样， 假设node 从1,2...n。第一次随机取一个点作为root, 然后左边就是左子树，右边是右字数，然后recursion 递归生成左边和右边应该就行了吧

hululei 发表于 2018-3-14 03:48
哦哦，这样啊， 感觉生成一棵树就像做partition一样， 假设node 从1,2...n。第一次随机取一个点作为root, ...

但是每一步按怎样的概率在左右添加节点才能保证最终每种情况出现的概率相等是需要思考的问题

茶园葱绿 发表于 2018-3-14 03:52
但是每一步按怎样的概率在左右添加节点才能保证最终每种情况出现的概率相等是需要思考的问题

比如node 是从1,2...n， 我选i作为root, 那么左子树有i-1个点，右字数有n- i个点，不同的i 构成的树的结构已经必定是不一样的了，这可以看做是n个大类，每一类是等概率。接下来处理左边i-1各点，又有若干种可能，我们按照同样的方法，最后每种结果都是等概率的

茶园葱绿 发表于 2018-3-14 03:52
但是每一步按怎样的概率在左右添加节点才能保证最终每种情况出现的概率相等是需要思考的问题

就像n个node, 需要做n-1次partition, partition的顺序最终决定了树的结构