Clase de arbori de căutare echilibrați din pachetul java.util

Pachetul java.util oferă două clase de arbori de căutare echilibrați: TreeMap și TreeSet. Ambele sunt realizate ca arbori bicolori.

Clasa TreeMap

Clasa java.util.TreeMap extinde clasa java.util.AbstractMap și implementează interfața java.util.SortedMap, astfel că reprezintă o mapare sortată, realizată sub formă de arbore bicolor. Se garantează astfel că operațiile de căutare, punere și eliminare a unui nod au complexitatea logaritmică O(log n).

Ca la orice mapare, elementele (în cazul de față informațiile atașate nodurilor arborelui) sunt perechi cheie-valoare, iar căutarea informației se face după cheie.
 
Clasa TreeMap are patru constructori:
   public TreeMap() - construiește o mapare vidă, cu sortare în ordinea naturală a cheilor;
   public TreeMap(Comparator c) - construiește o mapare vidă, la care sortarea se va face folosind comparatorul c;
   public TreeMap(Map m) - construiește o mapare care conține toate elementele mapării m, sortate în ordinea naturală a cheilor;
   public TreeMap(SortedMap m) - construiește o instanța a clasei TreeMap care conține elementele mapării sortate m, respectând același mod de sortare.

Metodele clasei TreeMap sunt cele ale interfeței Map, la care se adaugă metodele interfeței SortedMap:
   public Comparator comparator() - întoarce comparatorul asociat acestei mapări, sau null dacă se folosește ordinea naturală a cheilor;
   public SortedMap subMap(Object fromKey, Object toKey) - întoarce o vedere a acestei mapări care conține elementele situate între cele două chei date ca argumente;
   public SortedMap headMap(Object toKey) - întoarce o vedere a porțiunii acestei mapări, cuprinsă între primul element și cel cu cheia primită ca argument (exclusiv acesta);
   public SortedMap tailMap(Object fromKey) - întoarce o vedere a acestei măpari, conținând elementele de la cel cu cheia primită ca argument, până la sfârsit;
   public Object firstKey() - întoarce prima cheie din această mapare;
   public Object lastKey() - întoarce ultima cheie din această mapare.

Exemplu: în fișierul TestTreeMap.java este dat un exemplu de aplicație în care se testează crearea unei instanțe a clasei TreeMap, punerea de elemente, eliminarea unui element, determinarea primei și ultimei chei și afișarea întregii mapări.
 

Clasa TreeSet

Clasa java.util.TreeSet extinde clasa java.util.AbstractSet și implementează interfața java.util.SortedSet, astfel că reprezinta o mulțime ordonată, realizată ca un arbore bicolor.

Pentru a se poate face sortarea, elementele mulțimii (obiectele puse în TreeSet) trebuie să fie mutual comparabile, deci trebuie să aparțină unei clase care implementeaza interfața Comparable, sau trebuie prevăzute cu un Comparator.

Spre deosebire de clasa TreeMap, ale cărei instanțe erau mulțimi de perechi cheie-valoare, instanțele clasei TreeSet sunt mulțimi de obiecte ordonate, deci nu există chei explicite, ci sortarea se face după valoare.
Complexitatea operațiilor de căutare, punere și eliminare de elemente este, și în acest caz, O(log n).
 
Clasa TreeSet are următorii constructori:
   public TreeSet() - construiește o mulțime vidă, în care sortarea se va face respectând "ordinea naturală" a elementelor (cea dată de metoda 
                              int comPareTO(Object obj)
a interfeței Comparable);
   public TreeSet(Comparator c) - construiește o instanță a clasei TreeSet, în care sortarea se va face folosind comparatorul c;
   public TreeSet(Collection c) - creează o mulțime sortată, în care pune toate elementele colecției c (sortarea se face în ordine naturală);
   public TreeSet(SortedSet s) - creează o instanță a clasei TreeSet care conține elementele mulțimii sortate s, respectând același mod de ordonare ca în s.

Metodele clasei TreeSet sunt cele ale interfeței Set (deci și ale clasei AbstractSet) completate cu următoarele metode ale interfeței java.util.SortedSet:
   public Comparator comparator() - întoarce comparatorul folosit pentru sortare, sau null dacă sortarea se face în ordine naturală;
   public SortedSet subSet(Object fromElement, Object toElement) - întoarce o vedere a acestei mulțimi ordonate, conținând elementele cuprinse între cele două argumente (exclusiv cel din urmă);
   public SortedSet headSet(Object toElement) - întoarce o vedere a acestei mulțimi ordonate, conținând elementele de la primul, pană la cel dat ca argument (exclusiv acesta);
   public SortedSet tailSet(Object fromElement) - întoarce o vedere a acestei mulțimi ordonate, conținând elementele de la cel dat ca argument, pana la sfârșit;
   public Object first() - întoarce primul element al acestei mulțimi ordonate;
   public Object last() - întoarce ultimul element al acestei mulțimi ordonate;

Exemplu: în fișierul TestTreeSet.java se dă un exemplu de testare a clasei TreeSet. Se testează crearea unei instanțe, punerea unor cuvinte primite ca argumente în linia de comandă, eliminarea unui element, determinarea numărului de elemente, obținerea primului și ultimului element și afișarea mulțimii.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați