Pourquoi l'API Java Collections n'a pas d'implémentation Tree

Juste par curiosité, j'ai récemment eu à utiliser un arbre pour l'un de mes programmes, j'ai dû construire un arbre binaire de moi-même, mais pourquoi ne les Collections de l'API ne dispose pas d'un défaut de mise en œuvre de l'arbre(ou même un arbre binaire)?

Je pense qu'il devrait y avoir une bonne raison pourquoi ils ont décidé de ne pas l'inclure dans les collections de l'API.

source d'informationauteur Rajesh Pantula

  1. 15

    Je pense qu'il devrait y avoir une bonne raison pourquoi ils ont décidé de ne pas l'inclure dans les collections de l'API.

    Je pense que la raison en est que personne n'est venu avec une bonne API pour des arbres qui est à la fois

    • usage général assez pour couvrir un large éventail de cas d'utilisation, et
    • utile suffisante pour compenser le rendement des frais généraux de généraux de.

    (Et où avez-vous l'arrêter? L'arbre? Arbre binaire? N-aire arbre? DAG? Le graphique?)

    Il est intéressant de noter que ni Apache Commons Collections ou Google Collections (aka Goyave), un arbre de l'API. Cependant, il y a un actif de Goyave question sur ce sujet - http://code.google.com/p/guava-libraries/issues/detail?id=174 - si clairement au moins certains des gens sont d'accord avec votre point de vue.

    Mise à JOUR

    De la version 15.0, Goyave a maintenant l'arbre de soutien sous la forme de la TreeTraverser et BinaryTreeTraverser classes. Mais cela peut ne pas être ce que vous attendez. En vérité, ces classes ne sont pas réellement mettre en œuvre la structure d'arbre de données. Au lieu de cela, vous devez le faire dans un paramètre de type générique. De plus, l' Traverser classes de même éviter de faire des hypothèses sur les Api du type de nœud. Ils le font en étant les classes abstraites, et en exigeant que le béton traverser sous-type à mettre en œuvre les opérations qui questionnent l'arbre; par exemple, pour obtenir un nœud enfants.

    FWIW, TreeMap et TreeSet ne sont pas "l'arbre Api". Elles sont basées sur les arbres dans les implémentations de la Map et Set Api. L'arbre-ness est totalement caché par les Api publiques, faisant de ces deux classes totalement impropre à l'utilisation par les arbres.

  2. 10

    À mon humble avis, théoriquement, l'Arbre n'est pas un type de collection, c'est juste un type de mise en œuvre. Je veux dire, il y a des collections abstraites telles que Set (non ordonnée jeu d'entrées), Liste (ensemble ordonné d'entrées), la Carte (deux séries d'entrées de relations entre eux), et il y a de leur mise en œuvre: tableau, liste (par exemple, ArrayList et LinkedList), HashSet, etc., ils ont tous leurs propres avantages et inconvénients. Ainsi, l'Arbre est juste l'une des implémentations (pour les listes, par exemple) qui peut vous donner (à peu près) une recherche plus rapide de tableau mais pas d'accès par index.

    BTW, il y a TreeMap ("Rouge-Noir à base de bois NavigableMap mise en œuvre") et TreeSet ("Un NavigableSet mise en œuvre, basé sur un TreeMap.") les classes en Java.

  3. 0

    java.util.TreeMap est une mise en œuvre de Rouge et de Noir de l'Arbre.