Come ottenere o trovare in modo casuale un sottoalbero (include il nodo radice) da un dato albero che contiene n nodi foglia

Question

Come ottenere o trovare in modo casuale un sottoalbero (include il nodo radice) da un dato albero che contiene n nodi foglia

#1 da (1 voti)

2

Ho un albero non binario. Voglio trovare casualmente "sotto-alberi" che sono collegati da root a foglia che devono avere almeno n nodi foglia (i nodi foglia del sotto-albero devono essere nodi foglia dell'albero dato ). Ad esempio: dato un albero come sotto

           *A
          /   \
         B     C
        / \     \
      *E   D    *F
            \
             *J

n = 2
Un sottoalbero casuale che contiene 2 nodi foglia può essere:

            A
          /   \
         B     C
        /       \
       E         F

o

o

Non ho bisogno di ottenere tutti i sotto-alberi possibili, casualmente prendilo con un albero dato e n

java random algorithms trees

posta Hung Ton 08.01.2015 - 03:41

fonte

1 risposta

Leggi altre domande sui tag java random algorithms trees

Modo corretto per rifattorizzare più condizioni se basate [duplicato] Garantire l'affidabilità della compilazione incrociata

score 1 · Accepted Answer

Scegli a caso n nodi foglia. Restituisci l'albero che contiene quei nodi foglia e i loro antenati.

Ogni volta che dici "random", devi specificare quale distribuzione di probabilità vuoi. A meno che non annulli la distribuzione di probabilità, ognuna di queste "soluzioni" soddisferà le tue esigenze:

Seleziona sempre le foglie n più a sinistra.
Seleziona sempre le foglie n più a destra.
Scegli sempre le foglie di mezzo.
Visita tutte le foglie in un ordine desiderato. Metti ognuno alla fine di una lista. Se la lista ora contiene più di n nodi, cancellane uno a caso.
Crea un elenco di tutte le foglie, quindi scartane ripetutamente una a caso fino a quando ne rimane solo una.
Scegli un numero casuale compreso tra 1 e 5. Usa il metodo corrispondente dall'elenco precedente.

Si noti che la parola "casuale" appare più volte nella precedente. Ognuna di queste istanze di "random" dovrebbe essere qualificata dalla sua distribuzione di probabilità.

Ma soprattutto si noti che il prelievo casuale di n elementi da un set più grande è un sottotema completamente separato che non ha nulla a che fare con gli alberi. Per prima cosa lo risolvi, poi torni al dominio trees per costruire l'albero che ha i nodi foglia selezionati.

Prova a risolvere ciascuno di questi problemi secondari. Penso che scoprirai che nessuno dei due è terribilmente difficile, una volta che l'altro sotto-problema ti viene temporaneamente fuori di testa.

Altrimenti, se stai cercando di costruire l'albero mentre stai raccogliendo le foglie per farlo, ti farai impazzire.