Les deux BST auto-équilibrés que je connais le mieux sont le rouge-noir et le AVL, donc je ne peux pas dire avec certitude si d'autres solutions sont mieux, mais si je me souviens bien, le rouge-noir a une insertion plus rapide et une récupération plus lente par rapport à AVL.

Donc, si l'insertion est une priorité plus élevée que la récupération, le rouge-noir peut être une meilleure solution.

Pourquoi utiliser un BST ? D'après votre description, un dictionnaire fonctionnera aussi bien, sinon mieux.

La seule raison d'utiliser un BST serait si vous vouliez répertorier le contenu du conteneur dans l'ordre des clés. Il ne semble certainement pas que vous vouliez faire cela, auquel cas optez pour la table de hachage. O(1) insertion et recherche, pas de souci de suppression, quoi de mieux ?

[les tables de hachage ont] O(1) insertion et recherche

Je pense que c'est faux.

Tout d'abord, si vous limitez l'espace de clés à un espace fini, vous pouvez stocker les éléments dans un tableau et effectuer un balayage linéaire O(1). Ou vous pouvez trier le tableau de manière aléatoire, puis effectuer un balayage linéaire en temps prévu O (1). Quand la matière est finie, la matière est facilement O(1).

Alors, disons que votre table de hachage stockera n'importe quelle chaîne de bits arbitraire ; cela n'a pas beaucoup d'importance, tant qu'il y a un ensemble infini de clés, dont chacune est finie. Ensuite, vous devez lire tous les bits de toute requête et entrée d'insertion, sinon j'insère y0 dans un hachage vide et j'interroge sur y1, où y0 et y1 diffèrent à une seule position de bit que vous ne regardez pas.

Mais disons que les longueurs de clé ne sont pas un paramètre. Si votre insertion et votre recherche prennent O(1), en particulier le hachage prend un temps O(1), ce qui signifie que vous ne regardez qu'une quantité finie de sortie de la fonction de hachage (à partir de laquelle il est probable qu'il y ait be seulement une sortie finie, d'accord).

Cela signifie qu'avec un nombre fini de compartiments, il doit y avoir un ensemble infini de chaînes qui ont toutes la même valeur de hachage. Supposons que j'insère beaucoup, c'est-à-dire