La classe Java TreeSet implementa la interfície Set que utilitza un arbre per a l'emmagatzematge. Hereta la classe AbstractSet i implementa la interfície NavigableSet. Els objectes de la classe TreeSet s'emmagatzemen en ordre ascendent.
Els punts importants sobre la classe Java TreeSet són:
- La classe Java TreeSet només conté elements únics com HashSet.
- Els temps d'accés i recuperació de classes de Java TreeSet són ràpids i tranquils.
- La classe Java TreeSet no permet l'element nul.
- La classe Java TreeSet no està sincronitzada.
- La classe Java TreeSet manté l'ordre ascendent.
- La classe Java TreeSet només conté elements únics com HashSet.
- Els temps d'accés i recuperació de classes de Java TreeSet són bastant ràpids.
- La classe Java TreeSet no permet elements nuls.
- La classe Java TreeSet no està sincronitzada.
- La classe Java TreeSet manté l'ordre ascendent.
- El TreeSet només pot permetre aquells tipus genèrics que siguin comparables. Per exemple, la classe StringBuffer està implementant la interfície Comparable.
Treball intern de la classe TreeSet
TreeSet s'està implementant mitjançant un arbre de cerca binari, que s'autoequilibra igual que un arbre vermell-negre. Per tant, operacions com cercar, eliminar i afegir consumeixen temps O(log(N)). La raó d'això està a l'arbre d'autoequilibri. És allà per assegurar-se que l'alçada de l'arbre no superi mai O(log(N)) per a totes les operacions esmentades. Per tant, és una de les estructures de dades eficients per mantenir les grans dades que s'ordenen i també per fer-hi operacions.
Sincronització de la classe TreeSet
Com ja s'ha esmentat anteriorment, la classe TreeSet no està sincronitzada. Vol dir que si més d'un fil accedeix simultàniament a un conjunt d'arbres i un dels fils d'accés el modifica, la sincronització s'ha de fer manualment. Normalment es fa fent alguna sincronització d'objectes que encapsula el conjunt. Tanmateix, en el cas que no es trobi aquest objecte, el conjunt s'ha d'embolicar amb l'ajuda del mètode Collections.synchronizedSet(). Es recomana utilitzar el mètode durant el temps de creació per evitar l'accés no sincronitzat del conjunt. El fragment de codi següent mostra el mateix.
TreeSet treeSet = new TreeSet(); Set syncrSet = Collections.synchronziedSet(treeSet);
Jerarquia de la classe TreeSet
Com es mostra al diagrama anterior, la classe Java TreeSet implementa la interfície NavigableSet. La interfície NavigableSet amplia les interfícies SortedSet, Set, Collection i Iterable en ordre jeràrquic.
iterador de mapa java
Declaració de classe TreeSet
Vegem la declaració de la classe java.util.TreeSet.
len de cadena en java
public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, Serializable
Constructors de la classe Java TreeSet
| Constructor | Descripció |
|---|---|
| TreeSet() | S'utilitza per construir un conjunt d'arbres buit que s'ordenarà en ordre ascendent segons l'ordre natural del conjunt d'arbres. |
| TreeSet (Col·lecció c) | S'utilitza per construir un nou conjunt d'arbres que contingui els elements de la col·lecció c. |
| TreeSet (comparador comparador) | S'utilitza per construir un conjunt d'arbres buit que s'ordenarà segons el comparador donat. |
| Conjunt d'arbres (Conjunt ordenat s) | S'utilitza per construir un TreeSet que contingui els elements del SortedSet donat. |
Mètodes de la classe Java TreeSet
| Mètode | Descripció |
|---|---|
| suma booleana (E e) | S'utilitza per afegir l'element especificat a aquest conjunt si encara no està present. |
| booleà addAll(Col·lecció c) | S'utilitza per afegir tots els elements de la col·lecció especificada a aquest conjunt. |
| E sostre (E e) | Retorna l'element més gran igual o més proper de l'element especificat del conjunt, o nul no hi ha aquest element. |
| Comparador comparador() | Retorna un comparador que ordena els elements. |
| Iterador descendentIterator() | S'utilitza per iterar els elements en ordre descendent. |
| NavigableSet descendingSet() | Retorna els elements en ordre invers. |
| Planta E (E e) | Retorna l'element mínim igual o més proper de l'element especificat del conjunt, o nul no hi ha cap element. |
| SortedSet headSet (E aElement) | Retorna el grup d'elements que són inferiors a l'element especificat. |
| NavigableSet headSet (E aElement, booleà inclòs) | Retorna el grup d'elements que són menors o iguals a (si, inclòs és cert) l'element especificat. |
| E superior (E e) | Retorna l'element més proper més gran de l'element especificat del conjunt, o nul no hi ha aquest element. |
| Iterador iterador() | S'utilitza per iterar els elements en ordre ascendent. |
| E inferior (E e) | Retorna l'element més proper més a l'element especificat del conjunt, o nul no hi ha aquest element. |
| E pollFirst() | S'utilitza per recuperar i eliminar l'element més baix (primer). |
| E pollLast() | S'utilitza per recuperar i eliminar l'element més alt (últim). |
| Divisor divisor divisor () | S'utilitza per crear un divisor d'enquadernació tardana i fallida ràpida sobre els elements. |
| Subconjunt de NavigableSet (E des de l'element, booleà des de l'inclusive, E a l'element, booleà des de l'inclusive) | Retorna un conjunt d'elements que es troben entre l'interval donat. |
| Subconjunt SortedSet (E de l'element, E a l'element)) | Retorna un conjunt d'elements que es troben entre l'interval donat que inclou fromElement i exclou toElement. |
| SortedSet tailSet (E de l'element) | Retorna un conjunt d'elements que són superiors o iguals a l'element especificat. |
| NavigableSet tailSet(E fromElement, booleà inclòs) | Retorna un conjunt d'elements que són majors o iguals que (si, inclòs és cert) l'element especificat. |
| booleà conté (Objecte o) | Retorna true si aquest conjunt conté l'element especificat. |
| booleà és buit () | Retorna true si aquest conjunt no conté cap element. |
| eliminar booleà (Objecte o) | S'utilitza per eliminar l'element especificat d'aquest conjunt si està present. |
| buit clar () | S'utilitza per eliminar tots els elements d'aquest conjunt. |
| Clon d'objecte() | Retorna una còpia superficial d'aquesta instància de TreeSet. |
| E primer() | Retorna el primer element (el més baix) actualment en aquest conjunt ordenat. |
| E darrer () | Retorna l'últim element (més alt) actualment en aquest conjunt ordenat. |
| mida int () | Retorna el nombre d'elements d'aquest conjunt. |
Exemples de conjunt d'arbres de Java
Exemple 1 de conjunt d'arbres de Java:
Vegem un exemple senzill de Java TreeSet.
Nom de l'arxiu: TreeSet1.java
import java.util.*; class TreeSet1{ public static void main(String args[]){ //Creating and adding elements TreeSet al=new TreeSet(); al.add('Ravi'); al.add('Vijay'); al.add('Ravi'); al.add('Ajay'); //Traversing elements Iterator itr=al.iterator(); while(itr.hasNext()){ System.out.println(itr.next()); } } } Prova-ho ara Sortida:
Ajay Ravi Vijay
Exemple 2 del conjunt d'arbres de Java:
Vegem un exemple de travessa d'elements en ordre descendent.
Nom de l'arxiu: TreeSet2.java
import java.util.*; class TreeSet2{ public static void main(String args[]){ TreeSet set=new TreeSet(); set.add('Ravi'); set.add('Vijay'); set.add('Ajay'); System.out.println('Traversing element through Iterator in descending order'); Iterator i=set.descendingIterator(); while(i.hasNext()) { System.out.println(i.next()); } } } Prova-ho ara Sortida:
Traversing element through Iterator in descending order Vijay Ravi Ajay Traversing element through NavigableSet in descending order Vijay Ravi Ajay
Exemple 3 de conjunt d'arbres de Java:
Vegem un exemple per recuperar i eliminar el valor més alt i més baix.
Nom de l'arxiu: TreeSet3.java
exemples de codi java
import java.util.*; class TreeSet3{ public static void main(String args[]){ TreeSet set=new TreeSet(); set.add(24); set.add(66); set.add(12); set.add(15); System.out.println('Lowest Value: '+set.pollFirst()); System.out.println('Highest Value: '+set.pollLast()); } } Sortida:
Lowest Value: 12 Highest Value: 66
Exemple 4 de conjunt d'arbres de Java:
En aquest exemple, realitzem diverses operacions de NavigableSet.
Nom de l'arxiu: TreeSet4.java
netejar la memòria cau npm
import java.util.*; class TreeSet4{ public static void main(String args[]){ TreeSet set=new TreeSet(); set.add('A'); set.add('B'); set.add('C'); set.add('D'); set.add('E'); System.out.println('Initial Set: '+set); System.out.println('Reverse Set: '+set.descendingSet()); System.out.println('Head Set: '+set.headSet('C', true)); System.out.println('SubSet: '+set.subSet('A', false, 'E', true)); System.out.println('TailSet: '+set.tailSet('C', false)); } } Sortida:
Initial Set: [A, B, C, D, E] Reverse Set: [E, D, C, B, A] Head Set: [A, B, C] SubSet: [B, C, D, E] TailSet: [D, E]
Java TreeSet Exemple 5:
En aquest exemple, realitzem diverses operacions SortedSetSet.
Nom de l'arxiu: TreeSet5.java
import java.util.*; class TreeSet5{ public static void main(String args[]){ TreeSet set=new TreeSet(); set.add('A'); set.add('B'); set.add('C'); set.add('D'); set.add('E'); System.out.println('Intial Set: '+set); System.out.println('Head Set: '+set.headSet('C')); System.out.println('SubSet: '+set.subSet('A', 'E')); System.out.println('TailSet: '+set.tailSet('C')); } } Sortida:
Intial Set: [A, B, C, D, E] Head Set: [A, B] SubSet: [A, B, C, D] TailSet: [C, D, E]
Exemple de conjunt d'arbres de Java: llibre
Vegem un exemple de TreeSet on estem afegint llibres al conjunt i imprimint tots els llibres. Els elements de TreeSet han de ser de tipus Comparable. Les classes String i Wrapper són comparables per defecte. Per afegir objectes definits per l'usuari a TreeSet, heu d'implementar la interfície Comparable.
Nom de l'arxiu: TreeSetExample.java
import java.util.*; class Book implements Comparable{ int id; String name,author,publisher; int quantity; public Book(int id, String name, String author, String publisher, int quantity) { this.id = id; this.name = name; this.author = author; this.publisher = publisher; this.quantity = quantity; } // implementing the abstract method public int compareTo(Book b) { if(id>b.id){ return 1; }else if(id <b.id){ return -1; }else{ 0; } public class treesetexample { static void main(string[] args) set treeset(); creating books book b1="new" book(121,'let us c','yashwant kanetkar','bpb',8); b2="new" book(233,'operating system','galvin','wiley',6); b3="new" book(101,'data communications & networking','forouzan','mc graw hill',4); adding to treeset set.add(b1); set.add(b2); set.add(b3); traversing for(book b:set){ system.out.println(b.id+' '+b.name+' '+b.author+' '+b.publisher+' '+b.quantity); < pre> <p> <strong>Output:</strong> </p> <pre>101 Data Communications & Networking Forouzan Mc Graw Hill 4 121 Let us C Yashwant Kanetkar BPB 8 233 Operating System Galvin Wiley 6 </pre> <h3>ClassCast Exception in TreeSet</h3> <p>If we add an object of the class that is not implementing the Comparable interface, the ClassCast Exception is raised. Observe the following program.</p> <p> <strong>FileName:</strong> ClassCastExceptionTreeSet.java</p> <pre> // important import statement import java.util.*; class Employee { int empId; String name; // getting the name of the employee String getName() { return this.name; } // setting the name of the employee void setName(String name) { this.name = name; } // setting the employee id // of the employee void setId(int a) { this.empId = a; } // retrieving the employee id of // the employee int getId() { return this.empId; } } public class ClassCastExceptionTreeSet { // main method public static void main(String[] argvs) { // creating objects of the class Employee Employee obj1 = new Employee(); Employee obj2 = new Employee(); TreeSet ts = new TreeSet(); // adding the employee objects to // the TreeSet class ts.add(obj1); ts.add(obj2); System.out.println('The program has been executed successfully.'); } } </pre> <p>When we compile the above program, we get the ClassCastException, as shown below.</p> <pre> Exception in thread 'main' java.lang.ClassCastException: class Employee cannot be cast to class java.lang.Comparable (Employee is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap') at java.base/java.util.TreeMap.compare(TreeMap.java:1569) at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:776) at java.base/java.util.TreeMap.put(TreeMap.java:785) at java.base/java.util.TreeMap.put(TreeMap.java:534) at java.base/java.util.TreeSet.add(TreeSet.java:255) at ClassCastExceptionTreeSet.main(ClassCastExceptionTreeSet.java:52) </pre> <p> <strong>Explanation:</strong> In the above program, it is required to implement a Comparable interface. It is because the TreeSet maintains the sorting order, and for doing the sorting the comparison of different objects that are being inserted in the TreeSet is must, which is accomplished by implementing the Comparable interface.</p> <hr></b.id){> Excepció ClassCast a TreeSet
Si afegim un objecte de la classe que no està implementant la interfície Comparable, es genera l'excepció ClassCast. Observa el programa següent.
programa en java
Nom de l'arxiu: ClassCastExceptionTreeSet.java
// important import statement import java.util.*; class Employee { int empId; String name; // getting the name of the employee String getName() { return this.name; } // setting the name of the employee void setName(String name) { this.name = name; } // setting the employee id // of the employee void setId(int a) { this.empId = a; } // retrieving the employee id of // the employee int getId() { return this.empId; } } public class ClassCastExceptionTreeSet { // main method public static void main(String[] argvs) { // creating objects of the class Employee Employee obj1 = new Employee(); Employee obj2 = new Employee(); TreeSet ts = new TreeSet(); // adding the employee objects to // the TreeSet class ts.add(obj1); ts.add(obj2); System.out.println('The program has been executed successfully.'); } } Quan compilem el programa anterior, obtenim la ClassCastException, com es mostra a continuació.
Exception in thread 'main' java.lang.ClassCastException: class Employee cannot be cast to class java.lang.Comparable (Employee is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap') at java.base/java.util.TreeMap.compare(TreeMap.java:1569) at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:776) at java.base/java.util.TreeMap.put(TreeMap.java:785) at java.base/java.util.TreeMap.put(TreeMap.java:534) at java.base/java.util.TreeSet.add(TreeSet.java:255) at ClassCastExceptionTreeSet.main(ClassCastExceptionTreeSet.java:52)
Explicació: En el programa anterior, cal implementar una interfície Comparable. És perquè el TreeSet manté l'ordre d'ordenació, i per fer l'ordenació és necessària la comparació de diferents objectes que s'estan inserint al TreeSet, que s'aconsegueix implementant la interfície Comparable.