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.)