📣 VIP通行证夏日特惠 限时立减$68
12
返回列表 发新帖
楼主: 茶园葱绿
跳转到指定楼层
上一主题 下一主题
收起左侧

狗家挂经

🔗
l553585 2018-3-14 03:48:19 | 只看该作者
全局:
茶园葱绿 发表于 2018-3-14 03:33
是要你随机生成一棵树,所有可能的树出现的可能性要是一样的

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

使用道具 举报

🔗
 楼主| 茶园葱绿 2018-3-14 03:52:22 | 只看该作者
全局:
hululei 发表于 2018-3-14 03:48
哦哦,这样啊, 感觉生成一棵树就像做partition一样, 假设node 从1,2...n。第一次随机取一个点作为root, ...

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

使用道具 举报

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

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

使用道具 举报

🔗
l553585 2018-3-14 04:00:29 | 只看该作者
全局:
茶园葱绿 发表于 2018-3-14 03:52
但是每一步按怎样的概率在左右添加节点才能保证最终每种情况出现的概率相等是需要思考的问题

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表