Meilleur BST auto-équilibré pour l'insertion rapide d'un grand nombre de nœuds

Question

J'ai pu trouver des détails sur plusieurs auto-équilibrages BSTs à travers plusieurs sources, mais je n'ai trouvé aucune bonne description détaillant laquelle est la meilleure à utiliser dans différentes situations (ou si cela n'a vraiment pas d'importance).

je veux un BST c’est optimal pour stocker plus de dix millions de nœuds.L'ordre d'insertion des nœuds est fondamentalement aléatoire et je n'aurai jamais besoin de supprimer des nœuds, donc le temps d'insertion est la seule chose qui devrait être optimisée.

J'ai l'intention de l'utiliser pour stocker les états de jeu précédemment visités dans un jeu de réflexion, afin de pouvoir vérifier rapidement si une configuration précédente a déjà été rencontrée.

Answer 1

Rouge noir est meilleur qu'AVL pour les applications nécessitant beaucoup d'insertion.Si vous prévoyez une recherche relativement uniforme, alors le rouge-noir est la voie à suivre.Si vous prévoyez une recherche relativement déséquilibrée où les éléments consultés plus récemment sont plus susceptibles d'être consultés à nouveau, vous souhaitez utiliser arbres évasés.

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Je pense que cela est faux.

Tout d'abord, si vous limitez l'espace de clés pour qu'il soit fini, vous pouvez stocker les éléments dans un tableau et effectuer une analyse linéaire O(1).Ou vous pouvez trier le tableau de manière aléatoire, puis effectuer une analyse linéaire dans le temps prévu O (1).Quand les choses sont finies, les choses sont facilement O(1).

Supposons donc que votre table de hachage stocke n'importe quelle chaîne de bits arbitraire ;cela n'a pas beaucoup d'importance, tant qu'il existe 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 une requête sur y1, où y0 et y1 diffèrent sur une seule position de bit que vous ne regardez pas.

Mais disons que la longueur des clés n'est 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 que être seulement une production 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'en insère beaucoup, c'est-à-direω(1), parmi ceux-ci, et commencez l'interrogation.Cela signifie que votre table de hachage doit s'appuyer sur un autre mécanisme d'insertion/recherche O(1) pour répondre à mes requêtes.Lequel, et pourquoi ne pas l’utiliser directement ?