In quanti modi è possibile inserire una serie di valori in un BST per formare un albero specifico?

Question

This earlier question chiesto quanti modi ci sono per inserire i valori di 1 - 7 in un albero binario di ricerca che si tradurrebbe nella seguente albero:

 4 
    / \ 
    2  6 
/\ /\ 
    1 3 5 7 

(La risposta è di 80, tra l'altro).

Supponiamo, più in generale, che ti venga assegnato un BST arbitrario contenente un certo numero di valori e vuoi sapere quanti modi possibili ci sono per inserire quei valori in un BST che finirebbe per produrre l'albero risultante. C'è un algoritmo efficiente per determinare questo?

Grazie!

Answer 1

Possiamo risolvere questo problema utilizzando un algoritmo ricorsivo intelligente.

Come nostro caso base, se ti viene dato un albero vuoto, c'è esattamente un modo per costruire quell'albero - non inserire valori.

Per il caso ricorsivo, supponiamo che avete un BST che assomiglia a questo:

   v 
      /\ 
      L R 

Qui, v è la radice, e L e R sono le sottostrutture destro, rispettivamente.

Se vogliamo costruire questo albero di ricerca binario, dovremmo iniziare inserendo prima v - se non lo facessimo, v non sarebbe la radice. Dopo aver inserito v, è necessario inserire gli elementi in un ordinamento che causerà la ricostruzione dei sottostrutture L e R. La parte difficile qui è che non abbiamo bisogno di costruire tutto di L prima di costruire R o viceversa; si potrebbe inserire alcuni elementi L, poi alcuni elementi da R, poi più elementi di L, poi più elementi da R, ecc

Fortunatamente, però, c'è un'osservazione utile possiamo fare. Supponiamo che S _L sia una sequenza di elementi che, se inserita in una BST, forma la BST L. Analogamente, sia S _R una sequenza di elementi che se inserita in una BST forma la BST R. Se consideriamo ogni possibile interleaving delle sequenze S _L e S _R, si finirà con una sequenza di elementi che, se inserito in un BST contenente solo v, si accumula l'albero

v 
/\ 
L R 

Come Ad esempio, considera questo albero:

 4 
    / \ 
    2  6 
/\ /\ 
    1 3 5 7 

Una possibile sequenza che costruisce il sottoalbero sinistro (contenente 1, 2, 3) è 2, 1, 3. Una possibile sequenza che costruisce il sottostruttura di destra è 6, 5, 7. Qualsiasi interleaving possibile di quelle sequenze, quando inserito in un BST contenente solo il nodo radice 4, finirà per costruire la BST sopra.Ad esempio, una di queste sequenze funzionerà:

2, 1, 3, 6, 5, 7 
2, 6, 1, 5, 3, 7 
6, 5, 2, 1, 3, 7 
... 

Dal dato alcun sequenze S _L e S _R che si accumulano L e R possiamo alternare in qualsiasi ordine, siamo in grado di scrivere un bel formula per il numero di sequenze che si baserà su un albero con v come radice, L come suo sottoalbero sinistro ed R come suo sottoalbero destro:

# modi = (# interfogli di S _L e S _R) × (# possibile S _L s) × (# possibile S _R s)

Se ci pensate, gli ultimi due termini in questo prodotto può essere trovato in modo ricorsivo trovare il numero di sequenza di inserzione questo funziona per i sottoalberi sinistro e destro. Ciò significa che se riusciamo a capire quanti possibili intrecci ci sono per le due sequenze, allora possiamo determinare quante possibili sequenze di inserimento costruiranno un dato albero valutando l'espressione sopra in modo ricorsivo!

Quindi quanti intrecci ci sono? Se ci vengono date due sequenze di lunghezza m e n senza duplicati in esse, allora possiamo ottenere il numero di interlacciamenti di quelle sequenze con la seguente osservazione. Si consideri la sequenza

L L L ... L R R R ... R 
    m times  n times 

Qualsiasi permutazione di questa sequenza restituirà una serie di Ls e Rs cui il numero di Ls è uguale al numero di elementi nella sequenza di lunghezza m e il numero di Rs è uguale a il numero di elementi nella sequenza di lunghezza n. Possiamo interpretare questa sequenza come un modo per descrivere come costruire l'interleaving: ogni volta che vediamo L, inseriamo un elemento dalla sequenza di sinistra, e ogni volta che vediamo una R, inseriamo un elemento dalla sequenza corretta. Ad esempio, si consideri il sequenze 4, 1, 0, 3 e 2, 7. Quindi la LLRLRL permutazione dà la sequenza

4, 1, 2, 0, 3, 7 
L L R L R L 

Se si inizia con una sequenza di m L's e n R, il numero di distinte permutazioni torna come

(m + n)! 
-------- = (m + n) choose m 
m! n! 

Questo vale perché ci sono (m + n)! possibili modi di riordinare le L e le R se fossero tutte distinte. Dal momento che non lo sono, ogni ordine viene contato m! n! Troppe volte perché possiamo permutare l'Indistinguibile di L e le R in modo indistinguibile. Un altro modo di pensare a questo è considerare l'insieme {1, 2, 3, ..., m + n} degli indici nell'interfoliazione, quindi scegliere m di essi per riempire con gli elementi della prima sequenza, riempiendo implicitamente il resto di loro con elementi dalla sequenza corretta.

Okay ... ora abbiamo un modo per determinare il numero di modi di interleaving di due sequenze di lunghezza m e n.Pertanto, abbiamo la seguente:

# modi = (# interfogli di S _L e S _R) × (# possibile S _L s) × (# possibile S _R s)

= ((m + n) scegliere n) × (# possibile S _L s) × (# possibile S _R s)

Dove m è il numero di elementi nella sottostruttura di sinistra e n è il numero di elementi nella sottostruttura di destra. Sìì!

Possiamo dunque scrivere pseudocodice per questo algoritmo:

function countInsertionOrderings(Tree t) { 
    if t is null, return 1; 
    otherwise: 
     let m = numElementsIn(t.left); 
     let n = numElementsIn(t.right); 
     return choose(m + n, n) * 
       countInsertionOrderings(t.left) * 
       countInsertionOrderings(t.right); 
} 

Questo algoritmo esegue un totale di O (n) moltiplicazioni, dove n è il numero di nodi dell'albero, e le visite ogni nodo esattamente una volta (supponendo che il numero di elementi nel BST sia memorizzato nella cache in ciascun nodo). Questo è non significa che l'algoritmo viene eseguito nel tempo O (n), tuttavia, poiché il lavoro richiesto per moltiplicare questi numeri insieme crescerà rapidamente man mano che i numeri diventano sempre più grandi.

Spero che questo aiuti!

Answer 2

Questa è una domanda interessante. Ho implementato questa idea in Python e questa ricorsione più la memorizzazione ha prestazioni piuttosto buone. Il "seq" è la lista di input di interi unici

def answer(seq): 
    from math import factorial 
    BStore = dict() # store binomsial coefficient 
    Store = dict() # store the recusion step 
    def TreeGenerator(a,L): # for a given number a and a list L, this functions returns the left tree (a list) and the right tree (a list) 
     LT = [] 
     RT = [] 
     for i in L: 
      if i<a: 
       LT.append(i) 
      else: 
       RT.append(i) 
     solution = [LT,RT] 
     return(solution)  
    def binomial_coefficient(n, k): 
     d = n - k 
     if d < 0: 
      return(0) 
     return(factorial(n)/factorial(k)/factorial(d)) 
    def binomial(n, k): 
     if (n, k) in BStore: 
      return(BStore[n, k]) 
     else: 
      solution = binomial_coefficient(n, k) 
      BStore[n, k] = solution 
      return(solution)  
    def R(S): # recursion starts here 
     if tuple(S) in Store: 
      return(Store[tuple(S)]) 
     else: 
      if len(S)<2: 
       results = 1 
      else: 
       a = S[0] 
       S = S[1:] 
       Tree = TreeGenerator(a,S) 
       R1 = R(Tree[0]) 
       R2 = R(Tree[1]) 
       results = binomial(len(R1)+len(R2), len(R2))*R1*R2    
     Store[tuple(S)] = results 
     return(results) 
    return(R(seq))