Construit en binaire un arbre de recherche en Python?

Sont là tout auto-équilibrage arbre de recherche binaire (ROUGE-NOIR, AVL ou autres) des types intégrés dans Python 2.7 et Python 3.x?

Je suis à la recherche de quelque chose d'équivalent à Java TreeMap ou TreeSet.

Si il n'y a pas de built-ins, pourquoi ont-ils été omis? Est-il une raison particulière, pour ne pas inclure de tels outils?

  • Il n'en existe pas dans la bibliothèque standard. Pourquoi on n'a pas été inclus est impossible de répondre. Le reste de votre question est une demande de ressources extérieures, ce qui est hors-sujet.
  • Près de-dupe de stackoverflow.com/questions/2298165/...
InformationsquelleAutor Alexandru Chirila | 2013-07-25
  1. 18

    Il n'y a pas de raison particulière, à ma connaissance - je suppose que la raison en est que, pour de nombreuses applications de la très à l'écoute dict et set implémentations (qui sont des tables de hachage) fonctionnent bien. Qu'ils sont assez bons dans la plupart des cas. Il y a certainement des situations où vous devez les caractéristiques de performance de l'équilibre des arbres binaires (comme l'a ordonné la traversée de base sur les principaux plutôt que l'addition d'ordre), mais ceux-ci sont assez loin hors des sentiers battus que les gens sont heureux avec l'accaparement d'un tiers d'un paquet dans ce cas.

    J'ai eu une bonne expérience de l'utilisation de la bintrees paquet sur PyPI. Cela a implémentations de déséquilibre, AVL et-rouge-noir des arbres binaires, en pur Python et que les extensions écrites en Cython.

    Je pense que le reste de la raison est essentiellement historique accident. Si la personne qui a écrit bintrees fait pression en faveur de son inclusion dans la stdlib, et était disposé à mettre en place avec les contraintes qu'impose sur la maintenance et les rejets, il serait probablement aller dans. (Bien que le Cython dépendance pourrait poser problème, je suppose.)

    Complexité algorithmique:

    Pour les tables de hachage (comme les dicts ou des ensembles), de l'insertion et de la recherche sont en O(1), tandis que pour l'équilibre de l'arbre ce sont des O(log(n)). Dans l'ordre de la traversée de touches est O(n) dans un arbre, mais pour faire la même chose avec une table de hachage, vous devez trier les clés d'abord, il est donc O(n*log(n)). Lorsque vous êtes la cueillette quel genre de structure de données à utiliser, vous avez besoin de réfléchir sur les opérations que vous allez utiliser, et de choisir le compromis qui fait le plus de sens à votre demande.

    • Cela fait beaucoup de sens. Je devine que, probablement, dict et set sont en fait des arbres binaires, ou peut-être quelque chose d'encore plus efficace. Je vais faire quelques recherches dans exactement comment ils sont mis en oeuvre.
    • et set sont les tables de hachage.
    • Je donnerais blist une meilleure chance d'atterrissage int la stdlib. Je pense qu'il a été effectivement envisagé à un certain point, mais je ne me souviens pas des détails.
    • bien ne sont pas binaires, arbres de recherche (recherche en cours d'exécution en O(log n)) plus efficace que les tables de hachage (recherche en cours d'exécution en O(n)). Depuis les hachages sont des nombres, donc facilement comparables, arbres binaires semblent être une solution plus logique. Ai-je raté quelque chose?
    • table de hachage des recherches sont en O(1), plutôt que de O(n) - c'est pourquoi ils sont si souvent que vous le souhaitez. Parfois, c'est équilibré par le fait que le choix d'une bonne fonction de hachage peut être difficile, si vous avez beaucoup de collisions à l'avantage disparaît.
    • J'ai reçu aujourd'hui, merci encore pour la super réponse.
    • Ou plutôt, les tables de hachage dans le pire des cas, peut être O(n), mais avec de bonnes fonctions de hachage sont en O(1) dans le cas attendus. Ils n'utilisent plus de mémoire qu'un arbre de la même taille pour aider à assurer le cas attendus qui se passe réellement, mais de la mémoire supplémentaire est également utilisé pour amortir le coût de l'expansion de la structure de données que plusieurs éléments sont ajoutés en tant que bien.
    • vous avez peut-être raison, bien que blist est basée sur b+ arbres, je pense un peu un animal différent. Bien que beaucoup plus près des arbres binaires de tables de hachage.
    • oui, mais B+ arbres peuvent offrir le même ensemble d'opérations que les arbres binaires offre (notamment la Cartographie + triés itération), juste plus rapide dans la plupart des cas et en utilisant moins de mémoire.

    InformationsquelleAutor babbageclunk
  2. 1

    Vous ne trouverez pas tous les arbres dans la bibliothèque standard. Python utilise fortement dictionnaire de la table de hachage de son interne (objet, les classes et les modules sont tous basés sur des dicts). Donc dicts a été considérablement optimisé. Ce les besoins pour les arbres de recherche beaucoup plus petite. Aussi, pour être efficace, ces arbres ont été mis en œuvre dans un type d'extension.

    InformationsquelleAutor hivert