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

Question

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

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

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

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

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

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

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

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

6

algorithm puzzle

задан Robert Harvey 25 May 2011 в 02:26

2 ответа

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

4

ответ дан 17 December 2019 в 02:21

Другие вопросы по тегам:

algorithm puzzle

Похожие вопросы:

score 2 · Accepted Answer

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

редактировать 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);
}