Ben, non, justement. Il faut juste regarder la forme de l'arbre et faire les rotations qu'il faut.
Pour un rééquilibrage, oui, mais tu ne fais pas un rééquilibrage pour le fun, non ?
C'est toujours dans le cadre d'une insertion ou d'un suppression d'élément (c'est le scénario qu'envisageait rewind dans son message).
Pour insérer ou supprimer ton élément, ta complexité est bien en O(l log n), contre O(l) pour une table de hashage, malgré le redimensionnement. Si tu veux du lookup en O(l) et insertion/suppression en O(lr)/O(l+r) où r est le radix), alors effectivement un trie est une bonne idée.
Après, je suis d'accord avec toi :
- dans le cas de longues chaînes, la comparaison est souvent bien plus rapide que O(l), contrairement au hashage (mais voir la remarque sur le fait que le hash d'un objet immutable est souvent conservé)
- en oubliant la longueur des chaînes, avec un arbre binaire ton insertion est O(log n) dans le pire des cas, contre O(n) pour une table de hashage (d'où cette vulnérabilité, et potentiellement un problème avec des contraintes temps réel)
[^] # 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.
Pour un rééquilibrage, oui, mais tu ne fais pas un rééquilibrage pour le fun, non ?
C'est toujours dans le cadre d'une insertion ou d'un suppression d'élément (c'est le scénario qu'envisageait rewind dans son message).
Pour insérer ou supprimer ton élément, ta complexité est bien en O(l log n), contre O(l) pour une table de hashage, malgré le redimensionnement. Si tu veux du lookup en O(l) et insertion/suppression en O(lr)/O(l+r) où r est le radix), alors effectivement un trie est une bonne idée.
Après, je suis d'accord avec toi :
- dans le cas de longues chaînes, la comparaison est souvent bien plus rapide que O(l), contrairement au hashage (mais voir la remarque sur le fait que le hash d'un objet immutable est souvent conservé)
- en oubliant la longueur des chaînes, avec un arbre binaire ton insertion est O(log n) dans le pire des cas, contre O(n) pour une table de hashage (d'où cette vulnérabilité, et potentiellement un problème avec des contraintes temps réel)