生成均匀随机的奇妙二叉树

Question

如果一个二叉树有N个节点，它的节点值是1,2,...,N，并且满足以下条件，则称其为“奇特的”：

• 每个内部节点恰好有一个大于它的后代。
• 1,2,...,N中的每个数字在树中仅出现一次。

奇特二叉树示例

  4
 / \
5   2
   / \
  1   3

你能否提供一个算法来生成n个节点的均匀随机好奇二叉树，其运行时间保证为O(n)？

假设你只能访问一个随机数生成器，该生成器可以为任何1 <= k <= n的范围内提供（均匀分布的）随机数。假设生成器运行时间为O(1)。

我也想看到一个O(nlogn)时间复杂度的解决方案。

请按照标记二叉树的通常定义，将不同的好奇二叉树视为不同的。

- Aryabhatta

---

好的。我有点无聊。今天不用上班 :-) - Aryabhatta

随机是指在不同的树中均匀分布，还是每个节点从[1，n]的均匀随机分布中选择？ - Jacob

@Jacob：随机指的是不同树的均匀分布。节点始终为1、2、...、n。编辑问题以澄清。 - Aryabhatta

对于奇数N>2，存在偶数个树。运行RNG c次将给出c^N个可能的输出，为奇数。我们能保证运行时间吗？ - Nabb

@Nabb：抱歉，我不理解你的反对意见。 - Aryabhatta

Answer 1

“好奇”的二叉树和标准堆之间存在双射关系。具体来说，给定一个堆，从顶部开始递归地（自上而下）交换每个内部节点与其最大子节点。正如我不久前在StackOverflow上学到的那样，堆等价于1,2,...,N的排列。因此，您应该生成一个随机排列并将其转换为堆；或者以递归方式以相同的方式制作堆，就像您制作随机排列一样。之后，您可以将堆转换为“好奇树”。

- Greg Kuperberg

---

你如何在确定性 O(n) 时间内完成这个任务？ - Aryabhatta

使用排序方法在O(n(log n))时间内完成所有操作似乎并不困难。但是线性时间呢？从一个随机堆转换为一个随机的“奇特树”是线性时间的，这里有一些运气成分。我想知道你是否能以线性时间创建一个随机堆。使用Knuth排序算法可以在线性时间内创建一个随机排列，但对于随机堆就不确定了。 - Greg Kuperberg

我相信我们可以使用区间最小查询算法（O(n)时间O(n)空间）来采用这种方法以线性时间解决问题。 - Aryabhatta

Answer 2

哦，我想我知道如何在O（N）时间内创建随机堆了。（之后，使用Greg Kuperberg答案中的方法将其转换为“奇特”的二叉树。）

编辑2：制作随机最小堆的粗略伪代码。最大堆相同，只是插入堆的值按相反数顺序排列。

struct Node {
   Node left, right;
   Object key;
   constructor newNode() { 
     N = new Node; 
     N.left = N.right = null; 
     N.key = null;
   }
}

function create-random-heap(RandomNumberGenerator rng, int N)
{
   Node heap = Node.newNode();
   // Creates a heap with an "incomplete" node containing a null, and having
   // both child nodes as null.

   List incompleteHeapNodes = [heap];
   // use a vector/array type list to keep track of incomplete heap nodes.

   for k = 1:N
   {
      // loop invariant: incompleteHeapNodes has k members. Order is unimportant.

     int m = rng.getRandomNumber(k);
     // create a random number between 0 and k-1
     Node node = incompleteHeapNodes.get(m);
     // pick a random node from the incomplete list, 
     // make it a complete node with key k.
     // It is ok to do so since all of its parent nodes
     // have values less than k.
     node.left = Node.newNode();
     node.right = Node.newNode();
     node.key = k;

     // Now remove this node from incompleteHeapNodes
     // and add its children. (replace node with node.left,
     // append node.right)

     incompleteHeapNodes.set(m, node.left);
     incompleteHeapNodes.append(node.right);

     // All operations in this loop take O(1) time.
   }

   return prune-null-nodes(heap);
}

// get rid of all the incomplete nodes.
function prune-null-nodes(heap)
{
   if (heap == null || heap.key == null)
      return null;
   heap.left = prune-null-nodes(heap.left);
   heap.right = prune-null-nodes(heap.right);
}

- Jason S

---

@Jason：选择任何一个堆，并考虑使用你的方法获得该堆的概率。我相信我们可以证明这个概率恰好是1/n！。 - Aryabhatta

我可以相信这个...但是另一个分布（随机选择排列，逐个插入元素）是否也是等概率的呢？我猜如果有n！不同的堆结果，那么它必须是等概率的，否则就会少于n！不同的堆（只有n！种排列），这将遗漏一些。 - Jason S

它有效。该算法将数字按递增顺序插入到表示为堆结构的列表中。堆的空叶子表示每个新元素可以插入的间隙。该算法假设这些间隙是等可能的，事实也确实如此。这是一种堆版本的线性时间算法，用于生成随机排列。（如果您想要排列，堆也可以在线性时间内读取。）有趣。 - Greg Kuperberg

你如何将堆“读出”成排列？你使用中序遍历吗？似乎堆的排序属性会在某种程度上搞乱事情。 - Jason S

没错，中缀遍历。这就是堆和排列之间的双射。 - Greg Kuperberg