Quels sont les avantages et les inconvénients d'un TreeSet [fermé]
je me demande juste quels sont les avantages et les inconvénients d'un arbre, si quelqu'un peut me le dire s'il vous plaît? Merci!
5 réponses
une des classes de collecte. Il vous permet d'accéder aux éléments de votre collection par clé, ou de façon séquentielle par clé. Il est beaucoup plus haut que ArrayList ou HashMap. Utilisez HashSet lorsque vous n'avez pas besoin d'un accès séquentiel, cherchez juste par clé. Utilisez un ArrayList et utilisez des tableaux. trier si vous voulez juste les éléments dans l'ordre. TreeSet garde les éléments en ordre à tout moment. Avec ArrayList vous triez juste quand vous avez besoin. Avec TreeSets la clé doit être intégrée dans l'objet dans lequel vous stockez collection. Souvent, vous pourriez avoir Arbre de cordes. Tout ce que vous pouvez faire alors est de dire si une chaîne donnée est dans le jeu. Il ne vous trouvera pas un objet associé comme un tapis roulant. Avec un TreeMap, les clés et les objets auxquels elles sont associées sont séparés.
TreeSet et son frère TreeMap n'ont curieusement rien à voir avec la représentation des arbres. En interne, ils utilisent une organisation arborescente pour vous donner un ensemble/carte par ordre alphabétique, mais vous n'avez aucun contrôle sur les liens entre les parents et des enfants.
à L'intérieur des arbres, on utilise des arbres rouge-noir. Il n'est pas nécessaire de présenter les données pour obtenir un arbre bien équilibré. D'un autre côté, si les données sont triées (ascendantes ou descendantes), cela ne fera pas de mal comme c'est le cas avec d'autres types d'arbres.
si vous ne fournissez pas un comparateur pour définir L'ordre que vous voulez, TreeSet nécessite une implémentation Comparable sur la classe item pour définir l'ordre naturel.
les Inconvénients: Un écueil avec TreeSet est qu'il implémente l'interface d'une manière inattendue. Si un arbre contient l'objet a, alors l'objet b est considéré comme faisant partie de l'ensemble si a. compareTo (b) retourne 0, même si a. equals (b) est faux, donc si compareTo et equals ne sont pas implémentés d'une manière cohérente, vous êtes sur un mauvais chemin.
Ceci est particulièrement un problème quand une méthode renvoie un ensemble, et que vous ne savez pas si l'implémentation est un TreeSet ou, par exemple, un HashSet.
la leçon à apprendre ici est, toujours éviter de mettre en œuvre compareTo et égale de façon incohérente. Si vous devez commander des objets d'une manière qui n'est pas compatible avec des égaux, utilisez un comparateur.
TreeSet:
Avantages: trié, basé sur un algorithme d'arbre rouge/noir, fournit la complexité O(log(N)) pour les opérations.
Inconvénients: la valeur doit être Comparable ou si vous avez besoin de fournir Comparateur dans le constructeur. De plus, la mise en œuvre du HashSet offre une meilleure performance puisqu'elle fournit ~O(1) complexité.
fragments D'arbre mémoire et a des têtes supplémentaires de mémoire. Vous pouvez regarder les sources et calculer la quantité de mémoire supplémentaire et quantité d'autres objets qu'il crée. Bien sûr, cela dépend de la nature des objets stockés et vous pouvez aussi me soupçonner d'être paranoïaque à propos de la mémoire :) mais il est préférable de ne pas le dépenser ici et là - bas-vous avez GC, vous avez des trous de cache et toutes ces choses sont louches.
vous pouvez souvent utiliser PriorityQueue au lieu de TreeSet. Et dans votre cas d'utilisation typique, il est préférable de trier le tableau de cordes.
je suppose que cette structure de données utiliserait l'arbre binaire pour maintenir les données de sorte que la récupération d'ordre ascendant soit possible. Dans ce cas, s'il essaie de garder l'arbre en équilibre, l'opération d'enlèvement sera un peu coûteuse.