Funzione di conteggio sulla struttura ad albero (non binario)

Question

Funzione di conteggio sulla struttura ad albero (non binario)

#1 da (3 voti)
#2 da (0 voti)

2

Sto implementando una struttura dati ad albero in c # (in gran parte su Implementazione generica di Dan Vanderboom ). Sto considerando un approccio sulla gestione di una proprietà Count che Dan non implementa.

Il modo ovvio e facile sarebbe usare una chiamata ricorsiva che attraversa felicemente l'albero aggiungendo nodi (o iterativamente attraversando l'albero con una coda e contando i nodi se preferisci). Sembra solo costoso. (Potrei anche voler caricare pigro alcuni dei miei nodi lungo la strada).

Potrei mantenere un conteggio nel nodo radice. Tutti i bambini dovrebbero attraversare fino a e / o mantenere un riferimento alla radice e aggiornare una proprietà di conteggio impostabile internamente sulle modifiche. Ciò spingerebbe il problema di iterazione quando mai voglio interrompere un ramo o cancellare tutti i bambini sotto un determinato nodo. Generalmente meno costoso, e mette il sollevamento pesante quello che penso sarà meno frequentemente chiamato funzioni.

Sembra una piccola forza bruta, e questo di solito significa casi eccezionali a cui non avevo ancora pensato, o bug, se preferisci.

Qualcuno ha un esempio di un'implementazione che mantiene un conteggio per una struttura Albero sbilanciato e / o non binario invece di contare al volo? Non preoccuparti del carico pigro o della lingua. Sono sicuro di poter adattare l'esempio per soddisfare le mie esigenze specifiche.

EDIT: sono curioso di un esempio, piuttosto che di istruzioni o discussioni. So che non è tecnicamente difficile ...

data-structures trees

posta Spevy 12.10.2012 - 16:08

fonte

2 risposte

Leggi altre domande sui tag data-structures trees

Testing vs QA - output? Progettazione dell'applicazione del diagramma di flusso dell'algoritmo

score 3 · Answer 1

Sembra che tu abbia risposto alla tua stessa domanda. Chiedi a ciascun nodo di tenere il conteggio dei suoi discendenti più uno (stesso). Ogni volta che rimuovi un nodo decrementi ogni conteggio sul percorso fino alla radice. Quando si inserisce si incrementa invece ogni conteggio su quel percorso. In questo modo ogni nodo contiene il numero totale di nodi nel suo sotto-albero. Questo funzionerà bene per gli alberi n-ary.

Puoi persino eseguire l'incremento / decremento lungo la strada verso l'albero se sei sicuro che il nodo che stai inserendo / eliminando non esiste / esiste.

EDIT : rimozione di un nodo nel mezzo dell'albero. Supponi di avere un albero (etichettato con i conteggi):

     |
    A(a)
   /   \
 B(b)  C(c)

Supponiamo che tu elimini A e che le regole dicano che B dovrebbe spostarsi verso l'alto per riempire la sua posizione. Come abbiamo detto prima decrementi i conteggi sul percorso della radice, ma devi anche aggiornare il conteggio di B poiché è la nuova radice della sottostruttura. Devi aggiungere il conteggio di C a B :

     |
   B(b+c)
  /     \
...    C(c)

score 0 · Answer 2

Suggerirei di tenere un conteggio nella stessa classe in cui decidi di disattivare le funzioni Inserisci e Rimuovi.

public class TreeStruct{
    private int _count;
    private Object rootNode;

    public int count{ return count;}

    public void Insert(object obj){
        //insert object to tree
        _count++
    }

    public void Remove(object obj){
        //remove object from tree
        _count --;
    }
}