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

Translate

J'ai pu trouver des détails sur plusieurs auto-équilibragesBSTs à travers plusieurs sources, mais je n'ai trouvé aucune bonne description détaillant celle qui est préférable d'utiliser dans différentes situations (ou si cela n'a vraiment pas d'importance).

je veux unBSTc'est optimal pour stocker plus de dix millions de nœuds. L'ordre d'insertion des nœuds est essentiellement 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 les états de jeu précédemment visités dans un jeu de puzzle, afin de pouvoir vérifier rapidement si une configuration précédente a déjà été rencontrée.

This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

Rouge noirest meilleur que AVL pour les applications à insertion intensive. 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 les plus récemment consultés sont plus susceptibles d'être consultés à nouveau, vous souhaitez utiliserarbres évasés.

La source
Translate

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

La seule raison d'utiliser unBSTserait si vous vouliez lister 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 soucis de suppression, quoi de mieux?

La source
Anastasia Lee
Translate

Les deux auto-équilibrageBSTs Je suis le plus familier avec le rouge-noir etAVL, donc je ne peux pas dire avec certitude si d'autres solutions sont meilleures, mais comme je me souviens, 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.

La source
Translate

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

Je pense que cela est faux.

Tout d'abord, si vous limitez l'espace de clés à être 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 dans le temps prévu O (1). Quand le truc est fini, le truc est facilement O (1).

Supposons donc que votre table de hachage stocke n'importe quelle chaîne de bits arbitraire; peu importe, 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 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 votre recherche prennent O (1), en particulier le hachage prend O (1) temps, ce qui signifie que vous ne regardez qu'une quantité finie de sortie de la fonction de hachage (à partir de laquelle il est probable quebeseulement une sortie finie, accordée).

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), et que je commence à interroger. Cela signifie que votre table de hachage doit se rabattre sur un autre mécanisme d'insertion / recherche O (1) pour répondre à mes requêtes. Lequel, et pourquoi ne pas l'utiliser directement?

La source