Генерация равномерно случайных любопытных бинарных деревьев - PullRequest
Новая
       3

Генерация равномерно случайных любопытных бинарных деревьев

6 голосов
/ 14 июля 2010

Бинарное дерево из N узлов является «любопытным», если оно является бинарным деревом, значения узлов которого равны 1, 2, .., N и удовлетворяют свойству, которое

  • Каждый внутренний узел дерева имеет ровно одного потомка, который больше его.
  • Каждое число в 1,2, ..., N появляется в дереве ровно один раз.

Пример любопытного бинарного дерева 

  4
 / \
5   2
   / \
  1   3

Можете ли вы дать алгоритм для генерации равномерно случайного любопытного двоичного дерева из n узлов, которое выполняется за O (n) гарантированное время?

Предположим, у вас есть доступ только к генератору случайных чисел, который может дать вам (равномерно распределенное) случайное число в диапазоне [1, k] для любого 1 <= k <= n. Предположим, что генератор работает в O (1). </p>

Решение о времени O (nlogn) также получит мое одобрение.

Пожалуйста, следуйте обычному определению помеченных бинарных деревьев как отличных, чтобы рассмотреть различные любопытные бинарные деревья.

Ответы [ 2 ]

4 голосов
/ 14 июля 2010

Существует биекция между "любопытными" бинарными деревьями и стандартными кучами.А именно, с учетом кучи, рекурсивно (начиная сверху) меняйте местами каждый внутренний узел с его самым большим дочерним элементомИ, как я недавно узнал в StackOverflow, куча эквивалентна перестановке 1,2, ..., N.Таким образом, вы должны сделать случайную перестановку и превратить ее в кучу;или рекурсивно составьте кучу так же, как вы сделали бы случайную перестановку.После этого вы можете преобразовать кучу в «любопытное дерево».

2 голосов
/ 14 июля 2010

Ага, я думаю, что у меня есть, как создать случайную кучу за O (N) времени. (после этого используйте подход в ответе Грега Куперберга для преобразования в «любопытное» двоичное дерево.)

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