Vorrei capire quale sarebbe il metodo ottimale per trovare una copertura minima dell'albero dei nodi dell'albero. Lasciami spiegare.
Ho una struttura autoreferenziale che rappresenta un albero, con una profondità limitata di X.
Inodinell'alberopossonoesserelogicamente"selezionati". Dal punto di vista dell'applicazione, significa che l'utente vorrebbe avere alcune informazioni aggregate sulla selezione.
Diciamo che l'utente sceglie i nodi A, D, I, J, L e M.
Quellochemipiacerebbefareèessereingradodiristrutturarelaselezionedegliutentialfinediscegliereilsetminimodinodichecopronol'interaselezione.
Perquestoesempio:
- Inodi
- IeJpossonoesserecopertidalloronodogenitorecomuneF,quindiselezionoFerimuovoIeJ
- ilnodoMpuòesserecopertodalnodogenitoreH,quindiselezionoHerimuovoM
- ilnodoDègiàcopertodalnodoA,quindirimuovoD
Dopodiché,nullapuòessereulteriormenteristrutturato:l'algoritmosifermaedovreiottenerelaseguenteselezione.
Perprimacosa,nonsose"copertura minima" sia il nome giusto. In secondo luogo, non riesco a trovare alcuna frase migliore, quindi Google non è il mio migliore amico qui.
Un'altra cosa da notare è che l'albero stesso può essere memorizzato:
- in memoria
- nel database transazionale
- nel database OLAP (non esattamente più autoreferenziale)
Sono bloccato: (
Modifica
Ho riflettuto molto su questo problema e potrebbe esserci una soluzione che devo analizzare.
Di seguito è possibile inserire:
- chiamiamo albero stesso "l'albero modello"
- chiamiamo la selezione "albero di selezione"
- ogni nodo dell'albero modello ha un attributo ridondante precalcolato - numero di nodi figli
- l'albero di selezione può essere "sporco" o "pulito"
- dopo che un nodo è stato aggiunto, se non è ancora stato fatto nulla, è nello stato sporco
- dopo che la ristrutturazione è terminata, è in stato di pulizia
- ogni nodo dell'albero di selezione ha attributi ridondanti - numero di nodi figli selezionati e stati: selezionati o fantasma L'albero di selezione
- è una variante dell'albero in doppia memoria in memoria (il bambino conosce il suo genitore, il genitore conosce i suoi figli)
Successivamente, l'aggiunta di un nodo nell'albero di selezione (nodo di selezione) funzionerebbe in questo modo. Chiamiamo il nuovo genitore del nuovo nodo nell'albero di selezione un genitore selezione e il genitore del nuovo nodo nell'albero modello un modello genitore. Chiamiamo i figli della selezione del nodo dell'albero di selezione: figli e figli del modello di nodo dell'albero modello-figli.
- Imposta lo stato sporco dell'albero di selezione
- Rimuovi tutti i child di selezione del nodo di selezione
- Se inesistente nell'albero di selezione, recupera template-parent del nodo di selezione, insieme al suo numero di attributi child; aggiungi selezione genitore come nodo fantasma, con il numero selezionato di bambini = 1
- Se esistente nell'albero di selezione, seleziona selezione-genitore del nodo di selezione e incrementa il numero selezionato di figli
- Se selezione genitore ha selezionato il numero di figli uguale al numero di bambini modello, promuovi il suo stato da fantasma a selezionato; considera il nodo di selezione come un nuovo nodo e inizia da 1
- Imposta lo stato di pulizia dell'albero di selezione
Sono curioso di sapere se questo algoritmo esiste già come un'implementazione da qualche parte. Il suo comportamento non sarebbe ovviamente peggiore di O (log (n)), giusto? Certo, se non manca qualcosa nella logica.