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

Question

J'ai été en mesure de trouver des détails sur plusieurs auto-équilibrage BST s à travers plusieurs sources, mais je n'ai pas trouvé de bonnes descriptions détaillant lequel est le meilleur utiliser dans des situations différentes (ou si cela n'a pas vraiment d'importance).

Je veux un BST qui 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 aurait besoin d'être optimisée. J'ai l'intention de l'utiliser pour stocker des états de jeu visités précédemment dans un jeu de puzzle, de sorte que je puisse rapidement vérifier si une configuration précédente a déjà été rencontrée.

Answer 1

Red-black est mieux que AVL pour les applications lourdes 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 récemment visualisés sont plus susceptibles d'être visionnés à nouveau, vous devez utiliser splay trees.

Answer 2

Les deux auto-équilibrage BST s que je connais le plus sont rouge-noir et AVL, donc je ne peux pas dire avec certitude si d'autres solutions sont mieux, mais si je me souviens, le rouge-noir a une insertion plus rapide et 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.

Answer 3

Pourquoi utiliser un BST du tout? De votre description, un dictionnaire fonctionnera aussi bien, sinon mieux. La seule raison d'utiliser un BST serait si vous vouliez lister le contenu du conteneur dans l'ordre des clés. Il ne semble certainement pas que vous voulez faire cela, auquel cas optez pour la table de hachage. O(1) insertion et la recherche, pas de soucis de suppression, quoi de mieux?

Answer 4

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

Je pense que cela est faux. Tout d'abord, si vous limitez l'espace de clé à être fini, vous pouvez stocker les éléments dans un tableau et faire un balayage linéaire O (1). Ou vous pouvez shufflesort le tableau, puis faire un balayage linéaire en O (1) temps prévu. Quand les choses sont finies, les choses sont facilement O (1). Supposons que votre table de hachage stocke n'importe quelle chaîne de bits arbitraires; peu importe, tant qu'il y a un jeu 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 à une position de bit unique que vous ne regardez pas. Mais disons que les longueurs de clé ne sont pas un paramètre. Si votre insertion et recherche prennent O (1), en particulier le hachage prend O (1) temps, ce qui signifie que vous ne regardez qu'une quantité finie de la fonction de hachage (à partir de laquelle sera seulement une sortie finie , 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 ω (1), parmi ceux-ci, et que je commence à interroger.Cela signifie que votre table de hachage doit se replier sur un autre mécanisme d'insertion/recherche O (1) pour répondre à mes requêtes. Lequel, et pourquoi ne pas l'utiliser directement?