Test unitario per dimostrare l'albero bilanciato

3

Ho appena creato un albero autobilanciato (rosso-nero) in Java (la lingua dovrebbe essere irrilevante per questa domanda), e sto cercando di trovare un buon metodo per testare che sia correttamente bilanciato.

Ho testato tutte le operazioni dell'albero di base, ma non riesco a pensare a un modo per verificare che sia effettivamente ben bilanciato. Ho provato a inserire un ampio dizionario di parole, sia preordinate che non ordinate. Con un albero bilanciato, questi dovrebbero impiegare all'incirca lo stesso tempo, ma un albero sbilanciato richiederebbe molto più tempo nella lista già ordinata. Ma non so come fare per testarlo in un modo ragionevole e riproducibile. (Ho provato a fare test al millisecondo su questi, ma non ci sono differenze evidenti - probabilmente perché i miei dati di origine sono troppo piccoli.)

C'è un modo migliore per essere sicuro che l'albero sia veramente bilanciato? Dì, guardando l'albero dopo che è stato creato e vedendo quanto è profondo? (Ovvero, senza modificare l'albero stesso aggiungendo un campo di profondità a ciascun nodo, che è semplicemente dispendioso se non ne hai bisogno per qualcosa di diverso dal test.)

    
posta Darrel Hoffman 11.11.2013 - 01:08
fonte

2 risposte

10

Un modo per farlo sarebbe quello di creare un metodo sul tuo albero che misura la profondità dell'albero in un dato nodo. Non è necessario memorizzare il valore e, se si utilizza tale metodo getDepth() solo per il test, non è previsto alcun overhead aggiuntivo per le normali operazioni su albero. Il metodo getDepth() attraverserebbe in modo ricorsivo i suoi nodi figli e restituirà la profondità massima trovata.

Una volta ottenuto ciò, puoi controllare che l'intero albero sia bilanciato ricorrendo su ciascun nodo dell'albero e verificando una condizione come:

Math.abs(getDepth(left) - getDepth(right)) <= 1
    
risposta data 11.11.2013 - 01:27
fonte
0

Se si desidera misurare la complessità temporale per le letture, l'idea è che si possa avere l'albero che emette le callback per gli attraversamenti. In questo modo puoi misurare il numero di operazioni per una lettura, che sarebbe una misura più affidabile della complessità temporale.

    
risposta data 10.12.2013 - 18:31
fonte

Leggi altre domande sui tag