Ho bisogno di rappresentare un albero radice radicato nella memoria.
Quale sarebbe una buona struttura dati e algoritmi per l'esecuzione delle azioni principali, dati i dettagli elencati di seguito?
-
Dimensione: ~ 40.000 nodi. Ma idealmente dovrebbe scalare bene fino a 10 volte la dimensione o più.
-
Arity: molto variabile. Alcuni nodi hanno 2-3 bambini. Alcuni ne hanno 10. Alcuni (più rari) hanno 1000.
-
I dati NON sono statici - durante il giorno, ~ 1-3% dei nodi / bordi saranno aggiunti / rimossi / spostati in diverse parti dell'albero (per un buon esempio di vita reale, facciamo finta che sia un albero del filesystem in cui le persone sono molto attive e ha symlink).
Ai fini della notazione:
- D (V) - profondità del vertice (distanza dalla radice).
- A (V) - arità del vertice (quanti bambini ha)
- V - Dimensioni dell'albero (quanti vertici totali)
Le seguenti azioni sono necessarie (con la velocità d'azione desiderata indicata).
-
Possibilità di aggiungere un singolo vertice o una nuova sottostruttura
O (N) dove N è la quantità di vertici che vengono aggiunti (non già nell'albero) e O (D (V)) dove V è il vertice dove sono collegati i nuovi nodi.
-
Possibilità di eliminare una sottostruttura
O (N) dove N è la quantità di vertici eliminati e O (D (V)) dove V è il vertice da cui vengono cancellati i nuovi nodi.
-
Possibilità di spostare un sottoalbero in un altro genitore altrove nell'albero
O (N) dove N è la quantità di vertici che vengono spostati e O (D (V)) dove V è il vertice in cui vengono spostati i nuovi nodi.
Si noti che a causa delle esigenze di recupero descritte di seguito, NON prevedo che è possibile farlo in O (1) indipendentemente dal numero di nodi che vengono spostati, come in una normale struttura dati di base dell'albero con i puntatori del nodo figlio .
-
Possibilità di trovare un nodo con il suo nome (necessario per tutti i passaggi successivi)
Idealmente, O (1). Molto decisamente molto meno di O (log V).
-
Possibilità di conoscere il percorso completo dal vertice alla radice
O (1) idealmente. Ma decisamente inferiore a O (D (V)). Questo è molto importante; ed è la ragione per cui le implementazioni collegate standard dell'albero non funzioneranno, anche con collegamenti a 2 vie.