如何构造一棵随机的二叉树？

喵仔牛奶 @ 2022-11-17 20:23:54

by Xy_top @ 2022-11-17 20:24:40

洛谷不是有那种专门生成毒瘤的东西吗？

by 喵仔牛奶 @ 2022-11-17 20:26:09

@Xy_top 不会，洛谷教程看不懂qwq

by jijidawang @ 2022-11-17 20:29:13

每个点随一个权值然后插 BST 里？不确定是否非常均匀 qwq

by Usada_Pekora @ 2022-11-17 20:29:13

@喵仔牛奶 钦定一个点为根，然后维护一个当前孩子数量 \leq 2 的点的队列。

从 2\sim n 每次取出一个点，然后在这个队列里面随便找一个点作为它的一个随机方向的孩子，再丢到队列里面。

by MoonFlower @ 2022-11-17 20:29:24

https://mivik.blog.luogu.org/the-art-of-randomness

by a2lyaXNhbWUgbWFyaXNh @ 2022-11-18 12:15:59

@喵仔牛奶 没记错的话算法进阶好像有生成随机树的模板改一下就行了