Erzeugen gleichmäßig zufälligen neugierigen Binärbäume

Question

einen Binärbaum aus N Knoten ist ‚gespannt‘, wenn es ein binärer Baum, dessen Knotenwerte sind 1, 2, .., N und die erfüllen die Eigenschaft, dass

• Jede interner Knoten des Baumes hat genau einen Nachkommen, der größer ist als dieser.
• Jede Zahl in 1,2, ..., N erscheint genau einmal im Baum.

Beispiel eines neugierigen Binärbaum

4 
/\ 
5 2 
/\ 
    1 3 

Können Sie einen Algorithmus geben einen einheitlich zufälligen neugierig Binärbaum von n Knoten, die in O (n) garantiert die Zeit abläuft, zu generieren?

Angenommen, Sie haben nur Zugriff auf einen Zufallsgenerator, der Ihnen eine (gleichmäßig verteilte) Zufallszahl im Bereich [1, k] für beliebige 1 < = k < = n geben kann. Angenommen, der Generator läuft in O (1).

Eine O (nlogn) Zeitlösung wird auch mein upvote bekommen.

Bitte folgen Sie der üblichen Definition von markierten binären Bäumen, die verschieden sind, um verschiedene merkwürdige binäre Bäume zu betrachten.

Answer 1

Aha, ich denke ich habe wie man einen zufälligen Haufen in O (N) Zeit erstellt. (nach dem, verwenden Sie Ansatz in Greg Kuperbergs Antwort zu verwandeln in "neugierig" Binärbaum.)

bearbeiten 2: Grobe Pseudocode für die Erstellung einer zufälligen Min-Heap direkt. Max-Heap ist identisch, außer dass die Werte, die in den Heap eingefügt werden, in umgekehrter numerischer Reihenfolge sind.

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

Answer 2

Es gibt eine Bijektion zwischen "neugierigen" Binärbäumen und Standardhaufen. Nämlich bei einem Heap, rekursiv (von oben beginnend) tausche jeden internen Knoten mit seinem größten Kind. Und wie ich in StackOverflow vor kurzem gelernt habe, entspricht ein Heap einer Permutation von 1,2, ..., N. Du solltest also eine zufällige Permutation machen und sie in einen Haufen verwandeln; oder rekursiv den Heap auf dieselbe Weise erstellen, wie Sie eine zufällige Permutation vorgenommen hätten. Danach können Sie den Haufen in einen "merkwürdigen Baum" umwandeln.