Mi stavo chiedendo, se ho un albero nero e rosso e voglio tenere traccia del numero di nodi nella sottostruttura, qual è il modo più efficace per farlo?
Voglio dire come faccio a lavorare con questi valori durante l'inserimento, la cancellazione e la rotazione dei nodi, così che non devo elaborare nuovamente il numero sotto ogni nodo?
Consentitemi di esporre un po 'il commento di @ Robert.
Quello di cui stai parlando è il caching di un risultato che può essere calcolato. Il caching dovrebbe essere visto come un'ottimizzazione, la cui applicazione prematura è un male noto, vale a dire: fallo solo nel momento in cui hai un problema di prestazioni misurabili. I cache possono facilmente diventare obsoleti e renderli precisi al 100% necessariamente complicheranno il codice. (E se dipendi da loro durante l'inserimento, aggiorna, ruota le operazioni, ora devi averli aggiornati all'interno di quelle operazioni, non solo tra le operazioni.) Il caching può anche rendere più complicato il codice multi-thread.
Puoi memorizzare i conteggi come suggerisce @Robert. Dovrai ragionare su quali valori di conteggio della sottostruttura nella cache dei nodi debbano cambiare ogni volta che si verifica un inserimento, eliminazione o rotazione e scrivere codice per aggiornare i conteggi memorizzati nella cache. Tuttavia, puoi calcolare il conteggio per contare anziché riconsiderare completamente. Quindi, quando inserisci un genitore, il conteggio dei genitori sale di uno, non devi ricontattare gli altri figli; allo stesso modo, il conteggio dei genitori del genitore sale anche di uno (se si sta facendo il conteggio transitivo) ecc ... La rotazione dovrebbe avere un effetto più locale, e non fare bolle su tutti i genitori.
Poiché con gli inserimenti e le eliminazioni, la correzione del conteggio deve necessariamente essere eseguita dai genitori fino alla radice, questo avrà un impatto negativo sulle prestazioni, a volte a causa di errori di cache della memoria del processore durante la visita ai genitori che non lo farebbero altrimenti sono stati visitati Avere test delle prestazioni sarebbe una buona idea, in modo che le versioni di caching e non-caching possano essere confrontate.
Leggi altre domande sui tag algorithms trees binary-tree