Clase de arbori de cautare echilibrati in pachetul java.util

Pachetul java.util ofera doua clase de arbori de cautare echilibrati: TreeMap si TreeSet. Ambele sunt realizate ca arbori bicolori.

Clasa TreeMap

Clasa java.util.TreeMap extinde clasa java.util.AbstractMap si implementeaza interfata java.util.SortedMap, astfel ca reprezinta o mapare sortata, realizata sub forma de arbore bicolor. Se garanteaza astfel ca operatiile de cautare, punere si eliminare a unui nod au complexitate logaritmica O(log n).

Ca la orice mapare, elementele (in cazul de fata informatiile atasate nodurilor arborelui) sunt perechi cheie-valoare, iar cautarea informatiei se face dupa cheie.
 
Clasa TreeMap are patru constructori:
   public TreeMap() - construieste o mapare vida, cu sortare in ordinea naturala a cheilor;
   public TreeMap(Comparator c) - construieste o mapare vida, la care sortarea se va face folosind comparatorul c;
   public TreeMap(Map m) - construieste o mapare care contine toate elementele maparii m, sortate in ordinea naturala a cheilor;
   public TreeMap(SortedMap m) - construieste o instanta a clasei TreeMap care contine elementele maparii sortate m, respectand acelasi mod de sortare.

Metodele clasei TreeMap sunt cele ale interfetei Map, la care se adauga metodele interfetei SortedMap:
   public Comparator comparator() - intoarce comparatorul asociat acestei mapari, sau null daca se foloseste ordinea naturala a cheilor;
   public SortedMap subMap(Object fromKey, Object toKey) - intoarce o vedere a acestei mapari care contine elementele situate intre cele doua chei date ca argumente;
   public SortedMap headMap(Object toKey) - intoarce o vedere a portiunii acestei mapari, cuprinsa intre primul element si cel cu cheia primita ca argument (exclusiv acesta);
   public SortedMap tailMap(Object fromKey) - intoarce o vedere a acestei mapari, continand elementele de la cel cu cheia primita ca argument, pana la sfarsit;
   public Object firstKey() - intoarce prima cheie din aceasta mapare;
   public Object lastKey() - intoarce ultima cheie din aceasta mapare.

Exemplu: in fisierul TestTreeMap.java este dat un exemplu de aplicatie in care se testeaza crearea unei instante a clasei TreeMap, punerea de elemente, eliminarea unui element, determinarea primei si ultimei chei si afisarea intregii mapari.
 

Clasa TreeSet

Clasa java.util.TreeSet extinde clasa java.util.AbstractSet si implementeaza interfata java.util.SortedSet, astfel ca reprezinta o multime ordonata, realizata ca un arbore bicolor.

Pentru a se poate face sortarea, elementele multimii (obiectele puse in TreeSet) trebuie sa fie mutual comparabile, deci trebuie sa apartina unei clase care implementeaza interfata Comparable, sau trebuie prevazute cu un Comparator.

Spre deosebire de clasa TreeMap, ale carei instante erau multimi de perechi cheie-valoare, instantele clasei TreeSet sunt multimi de obiecte ordonate, deci nu exista chei explicite, ci sortarea se face dupa valoare.
Complexitatea operatiilor de cautare, punere si eliminare de elemente este, si in acest caz, O(log n).
 
Clasa TreeSet are urmatorii constructori:
   public TreeSet() - construieste o multime vida, in care sortarea se va face respectand "ordinea naturala" a elementelor (cea data de metoda int comPareTO(Object obj) a interfetei Comparable);
   public TreeSet(Comparator c) - construieste o instanta a clasei TreeSet in care sortarea se va face folosind comparatorul c;
   public TreeSet(Collection c) - creeaza o multime sortata, in care pune toate elementele colectiei c (sortarea se face in ordine naturala);
   public TreeSet(SortedSet s) - creeaza o instanta a clasei TreeSet care contine elementele multimii sortate s, respectand acelasi mod de ordonare ca in s.

Metodele clasei TreeSet sunt cele ale interfetei Set (deci si ale clasei AbstractSet) completate cu urmatoarele metode ale interfetei java.util.SortedSet:
   public Comparator comparator() - intoarce comparatorul folosit pentru sortare, sau null daca sortarea se face in ordine naturala;
   public SortedSet subSet(Object fromElement, Object toElement) - intoarce o vedere a acestei multimi ordonate, continand elementele cuprinse intre cele doua argumente (exclusiv cel din urma);
   public SortedSet headSet(Object toElement) - intoarce o vedere a acestei multimi ordonate, continand elementele de la primul, pana la cel dat ca argument (exclusiv acesta);
   public SortedSet tailSet(Object fromElement) - intoarce o vedere a acestei multimi ordonate, continand elementele de la cel dat ca argument, pana la sfarsit;
   public Object first() - intoarce primul element al acestei multimi ordonate;
   public Object last() - intoarce ultimul element al acestei multimi ordonate;

Exemplu: in fisierul TestTreeSet.java se da un exemplu de testare a clasei TreeSet. Se testeaza crearea unei instante, punerea unor cuvinte primite ca argumente in linia de comanda, eliminarea unui element, determinarea numarului de elemente, obtinerea primului si ultimului element si afisarea multimii.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati