Viene generato un BST (mediante inserimento successivo di nodi) da ciascuna permutazione di chiavi dall'insieme {1,2,3,4,5,6,7}. Quante permutazioni determinano alberi di altezza due?Quante permutazioni di un determinato array risultano in BST di altezza 2?
Sono stato bloccato su questa semplice domanda per un po 'di tempo. Qualche suggerimento a chiunque.
Tra l'altro la risposta è 80.
consideri come l'albero sarebbe altezza 2?
-E deve avere 4 come root, 2 come il figlio sinistro, 6 figlio destro, ecc
Come mai 4 è la radice?
-Deve essere il primo inserito. Quindi ora abbiamo un numero, 6 possono ancora muoversi nella permutazione.
E?
-Dopo il primo inserimento ci sono ancora 6 posti a sinistra, 3 a sinistra e 3 a destra sotto. Questo è 6 scegliere 3 = 20 scelte.
E adesso?
-Per i sottoalberi sinistro e destro, le loro radici devono essere inserite prima, quindi l'ordine dei bambini non influenza l'albero - 2, 1, 3 e 2, 3, 1 dà lo stesso albero. Questo è 2 per ogni albero secondario e 2 * 2 = 4 per i sottoalberi sinistro e destro.
Quindi?
In conclusione: C (6, 3) * 2 * 2 = 20 * 2 * 2 = 80.
Perché abbiamo fatto C (6,3) poiché solo {1,2,3} può formare sottostruttura sinistra e {5,, 6,7} può formare sottostruttura destra? Non abbiamo scelta. Spiega per favore. –
notare che v'è solo una possibile forma per questo albero - deve essere perfettamente bilanciato . Quindi deve essere questo albero:
4
/ \
2 6
/\ /\
1 3 5 7
Ciò richiede che venga inserito prima 4. Successivamente, gli inserimenti devono creare i sottotitoli che contengono 1, 2, 3 e 5, 6, 7 nell'ordine corretto. Ciò significa che dovremo inserire 2 prima di 1 e 3 e inserire 6 prima di 5 e 7. Non importa quale ordine relativo inseriamo 1 e 3 in, purché siano dopo il 2, e allo stesso modo non importa quale ordine relativo abbiamo messo 5 e 7 in tutto il tempo che hanno dopo 6. Puoi quindi pensare a cosa dobbiamo inserire come 2 XX e 6 YY, dove le X sono i figli di 2 e il Gli Y sono i figli di 6. Possiamo quindi trovare tutti i modi possibili per recuperare l'albero sopra trovando tutti gli interleave delle sequenze 2 XX e 6 YY, quindi moltiplicando per quattro (il numero di modi di assegnare X e Y i valori 1 , 3, 5 e 7).
Quindi quanti modi ci sono per interlacciare? Bene, puoi pensare a questo come al numero di modi per permutare la sequenza L L L R R R, poiché ogni permutazione di L L L R R R ci dice come scegliere tra la sequenza Left o la sequenza Right. Ce ne sono 6!/3! 3! = 20 modi per farlo. Poiché ognuna di queste venti interlacciature offre quattro possibili sequenze di inserimento, si ottiene un totale di 20 × 4 = possibili modi per farlo.
Spero che questo aiuti!
Grazie per la tua spiegazione! – user2473033
Giusto per chiarire ci sono 20 modi distinti di inserire 6 nodi nell'albero dopo la radice? – user2473033
@ user2473033- In realtà, ce ne sono 80. La root è costretta a stare in prima fila. – templatetypedef
Ho creato una tabella per il numero di permutazioni possibili con 1 - 12 elementi, con altezze fino a 12, e incluso l'interruzione per root per chiunque cerchi di verificare che il loro processo manuale (descritto in altre risposte) corrisponde ai valori attuali.
http://www.asmatteringofit.com/blog/2014/6/14/permutations-of-a-binary-search-tree-of-height-x
OK, l'unica domanda che hai posto ha la risposta alla fine. Qual è la tua vera domanda? * Come * ottenere questa risposta? – vcsjones
Volevo solo sapere come arrivare alla risposta postata, posso vederlo ora grazie ai commenti postati. – user2473033