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

Question

N节点的二叉树是"好奇的",如果它是一个二进制树,其节点值为1,2,...,N并且满足属性

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

一个好奇的二叉树的例子

  4
 / \
5   2
   / \
  1   3

你能给出一个算法来生成n个节点的均匀随机好奇二叉树,它在O(n)保证时间内运行吗？

假设您只能访问一个随机数生成器,它可以为[1,k]范围内的任何1 <= k <= n提供(均匀分布的)随机数.假设发电机在O(1)中运行.

O(nlogn)时间解决方案也将获得我的支持.

请遵循标记二进制树的通常定义,以区分不同的二进制树.

Answer 1

啊哈，我想我已经知道如何在 O(N) 时间内创建随机堆了。（之后，使用 Greg Kuperberg 的答案中的方法转换为“好奇的”二叉树。）

编辑2：直接生成随机最小堆的粗略伪代码。Max-heap 是相同的，只是插入堆中的值按相反的数字顺序排列。

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);
}