Et la dernière fois que j'ai regardé, rééquilibrer un arbre binaire ça coûte moins cher que d'augmenter la taille d'une table de hachage.
Ah bon ?
Rééquilibrer un arbre binaire, c'est O(log n).
Augmenter la taille d'une table de hachage, c'est un coût amorti de O(1), pour peu que tu utilises une progression géométrique.
[^] # Re: Les vrais théoriciens s'en foutent
Posté par neologix . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 4.
Ah bon ?
Rééquilibrer un arbre binaire, c'est O(log n).
Augmenter la taille d'une table de hachage, c'est un coût amorti de O(1), pour peu que tu utilises une progression géométrique.