Java TreeMap detaljno: od analize izvornog koda do praktične primene

Sada molim učitelja Vanga da izađe na scenu i održi čas o TreeMap — pljesak!

U članku o LinkedHashMap već smo pomenuli da je HashMap neuređen, pa je nastao LinkedHashMap — dodavanjem dvostruko povezane liste može se održavati redosled umetanja i redosled pristupa. A šta je sa TreeMap?

TreeMap je realizovan preko crveno-crnog stabla i može održavati prirodni redosled elemenata, ili prilagođeni redosled zasnovan na interfejsu Comparator.

Moguće je da neki od vas ne poznaju crveno-crno stablo, pa ćemo to ukratko objasniti:

Crveno-crno stablo (engl. Red–black tree) je samobalansirajuće binarno stablo pretrage (Binary Search Tree) — složene strukture, ali dobrih performansi, gde su vremenske složenosti pretrage, umetanja i brisanja jednake log(n).

Binarno stablo pretrage je uobičajena drvolika struktura u kojoj svaki čvor sadrži jedan par ključ-vrednost. Ključevi čvorova u levom podstablu manji su od ključa trenutnog čvora, a ključevi čvorova u desnom podstablu veći su od njega — upravo ta osobina čini binarno stablo pretrage veoma pogodnim za pretragu i sortiranje podataka.

Evo jednostavnog ručno nacrtanog prikaza strukture binarnog stabla pretrage:

        8
      /   \
     3     10
    / \      \
   1   6     14
      / \    /
     4   7  13

U gornjem binarnom stablu pretrage koreni čvor je 8; čvorovi levog podstabla su 3, 1, 6, 4 i 7, a čvorovi desnog podstabla su 10, 14 i 13.

3<8<10
1<3<6
4<6<7
10<14
13<14

Ovo je tipično binarno stablo pretrage:

1. Vrednosti svih čvorova levog podstabla manje su ili jednake vrednosti korenog čvora.
1. Vrednosti svih čvorova desnog podstabla veće su ili jednake vrednosti korenog čvora.
1. I levo i desno podstablo takođe su binarna stabla pretrage.

Pretraga u binarnom stablu pretrage je veoma jednostavna: kreće se od korenog čvora i prolazi kroz stablo; ako ključ trenutnog čvora odgovara traženom ključu, pretraga je uspešna; ako je traženi ključ manji od ključa trenutnog čvora, nastavlja se kroz levo podstablo; ako je veći, ide se kroz desno podstablo. Ako se dođe do lista i dalje nije pronađen, pretraga je neuspešna.

Operacija umetanja je takođe jednostavna: kreće se od korenog čvora; ako je ključ koji se umeće manji od ključa trenutnog čvora, umeće se u levo podstablo, a ako je veći — u desno podstablo. Ako ključ koji se umeće već postoji u stablu, ažurira se vrednost tog čvora.

Operacija brisanja je nešto složenija i zahteva razmatranje više slučajeva: da li čvor koji se briše je list, da li ima samo jedan potomak, da li ima dva potomka itd.

Ukratko, binarno stablo pretrage je vrlo često korišćena struktura podataka koja nam pomaže da realizujemo pretragu, sortiranje i brisanje podataka.

Da li vam je sada jasno binarno stablo pretrage?

Ipak, binarno stablo pretrage ima jedan očigledan nedostatak: lzo postaje „šepavo” — na jednoj strani ima previše čvorova, a na drugoj premalo. Na primer ovako:

        6
      /   \
     4     8
    /     / \
   3     7   9
  /
 1

U gornjem nebalansiranom binarnom stablu pretrage levo podstablo je više od desnog. Koreni čvor je 6; čvorovi levog podstabla su 4, 3 i 1, a čvorovi desnog podstabla su 8, 7 i 9.

Pošto je levo podstablo više od desnog, ovo nebalansirano binarno stablo pretrage može dovesti do pada efikasnosti pretrage, umetanja i brisanja.

Pogledajmo jedan još ekstremniji slučaj.

U ovom krajnje nebalansiranom binarnom stablu pretrage svaki čvor ima samo jednog desnog potomka. Koreni čvor je 1, a čvorovi desnog podstabla su 2, 3, 4, 5 i 6.

Ovo krajnje nebalansirano binarno stablo pretrage dovodi do drastičnog pada efikasnosti pretrage, umetanja i brisanja, jer se svaka operacija može odvijati samo u desnom podstablu, dok levo podstablo gotovo da se i ne koristi.

Efikasnost pretrage tada pada sa log(n) na o(n) (pogledajte ovde za više o vremenskoj složenosti), zar ne?

Stablo moramo nekako balansirati, zar ne? Tako su nastala balansirana binarna stabla, kod kojih apsolutna razlika visine levog i desnog podstabla nije veća od 1, kao na slici ispod:

        8
      /   \
     4     12
    / \    / \
   2   6  10  14
      / \    / \
     5   7  13  15

Koreni čvor je 8; čvorovi levog podstabla su 4, 2, 6, 5 i 7, a čvorovi desnog podstabla su 12, 10, 14, 13 i 15. Razlika visina levog i desnog podstabla nije veća od 1, pa je ovo balansirano binarno stablo pretrage.

Balansirano binarno stablo je poput drveta na tezinama: leva i desna strana treba da budu što je moguće izbalansiranije. Kada u balansirano binarno stablo umetnemo čvor, stablo će automatski prilagoditi položaj čvorova kako bi razlika visina levog i desnog podstabla ostala ne veća od 1. Isto važi i pri brisanju čvora — stablo ponovo automatski prilagođava položaj čvorova.

Uobičajena balansirana binarna stabla su AVL stablo, crveno-crno stablo itd.; sva ona održavaju balans pomoću rotacija, tako da visine levog i desnog podstabla ostanu što bliže.

Prikaz AVL stabla:

           8
         /   \
        4     12
       / \   /  \
      2   6 10  14
         / \
        5   7

AVL stablo je binarno stablo pretrage visokog stepena balansiranosti — zahteva da razlika visina levog i desnog podstabla ne bude veća od 1. Pošto je AVL stablo visoko balansirano, pri umetanju i brisanju potrebne su brojnije rotacije da bi se održao balans, ali je zato pretraga efikasnija. AVL stablo je pogodno za scenarije sa mnogo operacija čitanja.

Na primer, za scenarije koji zahtevaju čestu pretragu — kao što su strukture podataka poput rečničkog stabla (trie) ili heš tabele — AVL stablo može poslužiti za optimizaciju. Takođe, AVL stablo je pogodno i za scenarije gde je potrebno održavati uređenost podataka, kao što su indeksi u bazi podataka.

AVL stablo su prvobitno formulisala dva sovjetska informatičara, Adelson-Velskii i Landis, 1962. godine, pa je stablo po njihovim inicijalima i dobilo ime.

Otkriće AVL stabla značajno je uticalo na razvoj informatike — ne samo da je postavilo temelje za kasnija balansirana binarna stabla, već je dalo podstrek i strukturama podataka i algoritmima u drugim oblastima.

Prikaz crveno-crnog stabla (R je Red „crveno”, B je Black „crno”):

           8B
         /   \
        4R    12R
       / \   /  \
      2B 6B 10B 14B
         / \
        5R 7R

Crveno-crno stablo je, kako mu ime kaže, balansirano binarno stablo čiji su čvorovi crveni ili crni. Balans stabla održava se ograničenjima zasnovanim na bojama: zahteva se da broj crnih čvorova bude isti na svakoj putanji, a moraju se zadovoljiti i određeni dodatni uslovi — na primer, roditelj crvenog čvora mora biti crn.

1. Svaki čvor je isključivo crven ili crn.
1. Koreni čvor je crn.
1. Svaki list (NIL čvor, prazan čvor) je crn.
1. Ako je čvor crven, oba njegova potomka su crna — drugim rečima, na jednoj putanji ne smeju biti dva susedna crvena čvora.
1. Iz svakog čvora do svih njegovih listova vode putanje sa istim brojem crnih čvorova.

Pošto je stepen balansiranosti crveno-crnog stabla nešto niži od AVL stabla, pri umetanju i brisanju potrebne su ređe rotacije, ali je pretraga i dalje prilično efikasna. Crveno-crno stablo je pogodno za scenarije u kojima su operacije čitanja i pisanja približno izbalansirane.

Time ćemo za sada završiti priču o crveno-crnim stablima — dovoljno je da steknete opšti utisak i shvatite šta je TreeMap.

01,Prirodni redosled

Podrazumevano, TreeMap ređa elemente prema prirodnom redu ključa. Za cele brojeve to je rastući redosled: 1, 2, 3, 4, 5.

TreeMap<Integer,String> mapInt = new TreeMap<>();
mapInt.put(3, "Chenmo Wang Er");
mapInt.put(2, "Chenmo Wang Er");
mapInt.put(1, "Chenmo Wang Er");
mapInt.put(5, "Chenmo Wang Er");
mapInt.put(4, "Chenmo Wang Er");

System.out.println(mapInt);

Rezultat ispisa je sledeći:

{1=Chenmo Wang Er, 2=Chenmo Wang Er, 3=Chenmo Wang Er, 4=Chenmo Wang Er, 5=Chenmo Wang Er}

Kako to TreeMap uspeva? Da bismo zavirili u to, moramo pogledati izvorni kod — evo metode put() klase TreeMap:

public V put(K key, V value) {
    Entry<K,V> t = root; // dodeljujemo koreni čvor promenljivoj t
    if (t == null) { // ako je koreni čvor null, TreeMap je prazan
        compare(key, key); // type (and possibly null) check, provera da li je tip ključa ispravan
        root = new Entry<>(key, value, null); // kreiramo novi čvor kao koreni
        size = 1; // postavljamo size na 1
        return null; // vraćamo null, što znači da je umetanje uspelo
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths, pretraga na osnovu načina poređenja
    Comparator<? super K> cpr = comparator; // uzimamo komparator
    if (cpr != null) { // ako se koristi Comparator
        do {
            parent = t; // trenutni čvor dodeljujemo promenljivoj parent
            cmp = cpr.compare(key, t.key); // poredimo ključ sa ključem čvora t pomoću Comparator-a
            if (cmp < 0) // ako je ključ manji od ključa čvora t
                t = t.left; // tražimo u levom podstablu čvora t
            else if (cmp > 0) // ako je ključ veći od ključa čvora t
                t = t.right; // tražimo u desnom podstablu čvora t
            else // ako je ključ jednak ključu čvora t
                return t.setValue(value); // direktno ažuriramo vrednost čvora t
        } while (t != null);
    }
    else { // ako se ne koristi Comparator
        if (key == null) // ako je ključ null
            throw new NullPointerException(); // bacamo izuzetak NullPointerException
            Comparable<? super K> k = (Comparable<? super K>) key; // ključ konvertujemo u tip Comparable
        do {
            parent = t; // trenutni čvor dodeljujemo promenljivoj parent
            cmp = k.compareTo(t.key); // poredimo ključ sa ključem čvora t pomoću Comparable
            if (cmp < 0) // ako je ključ manji od ključa čvora t
                t = t.left; // tražimo u levom podstablu čvora t
            else if (cmp > 0) // ako je ključ veći od ključa čvora t
                t = t.right; // tražimo u desnom podstablu čvora t
            else // ako je ključ jednak ključu čvora t
                return t.setValue(value); // direktno ažuriramo vrednost čvora t
        } while (t != null);
    }
    // Ako isti ključ nije pronađen, kreiramo novi čvor i umećemo ga u TreeMap
    Entry<K,V> e = new Entry<>(key, value, parent); // kreiramo novi čvor
    if (cmp < 0) // ako je ključ manji od ključa čvora parent
        parent.left = e; // e postaje levi potomak čvora parent
    else
        parent.right = e; // e postaje desni potomak čvora parent
    fixAfterInsertion(e); // nakon umetanja čvora potrebno je balansiranje
    size++; // uvećavamo size za 1
    return null; // vraćamo null, što znači da je umetanje uspelo
}

Prvo se definiše promenljiva tipa Entry, t, koja predstavlja trenutni koreni čvor.
Ako je t null, TreeMap je prazan, pa se direktno kreira novi čvor kao koreni i size se postavlja na 1.
Ako t nije null, potrebno je pronaći čvor sa zadatim ključem u TreeMap-u. Pošto su elementi u TreeMap-u uređeni, čvor se može traži metodom binarne pretrage.
Ako TreeMap koristi Comparator za sortiranje, poređenje se obavlja preko Comparator-a, u suprotnom preko Comparable. Ako se pronađe isti ključ, direktno se ažurira vrednost koja mu odgovara.
Ako se ne pronađe isti ključ, kreira se novi čvor i umeće u TreeMap. Zatim se metodom fixAfterInsertion() ispravlja stanje balansa nakon umetanja.
Na kraju se size TreeMap-a uvećava za 1 i vraća se null. Ako je ažurirana vrednost postojećeg ključa, vraća se prethodna vrednost.

Obratite pažnju na liniju cmp = k.compareTo(t.key) — ona služi za poređenje ključeva; pošto je ključ u ovom trenutku tipa String, pozvaće se metod compareTo() klase String.

public int compareTo(String anotherString) {
    // dužine trenutnog i drugog stringa
    int len1 = value.length;
    int len2 = anotherString.value.length;
    // kraća dužina je gornja granica poređenja
    int lim = Math.min(len1, len2);
    // nizovi znakova trenutnog i drugog stringa
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    // upoređujemo znakove jednog po jednog
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        // ako znakovi nisu jednaki, vraćamo njihovu razliku
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    // ako su svi znakovi do kraja kraćeg stringa jednaki, vraćamo razliku dužina
    return len1 - len2;
}

Pogledajmo sledeći primer.

TreeMap<String,String> mapString = new TreeMap<>();
mapString.put("c", "Chenmo Wang Er");
mapString.put("b", "Chenmo Wang Er");
mapString.put("a", "Chenmo Wang Er");
mapString.put("e", "Chenmo Wang Er");
mapString.put("d", "Chenmo Wang Er");

System.out.println(mapString);

Rezultat ispisa je sledeći:

{a=Chenmo Wang Er, b=Chenmo Wang Er, c=Chenmo Wang Er, d=Chenmo Wang Er, e=Chenmo Wang Er}

Iz rezultata se vidi da je sortiranje obavljeno po abecednom redu, rastuće.

02,Prilagođeno sortiranje

Ako prirodni redosled ne odgovara, prilikom deklaracije TreeMap objekta možemo navesti pravila sortiranja.

TreeMap<Integer,String> mapIntReverse = new TreeMap<>(Comparator.reverseOrder());
mapIntReverse.put(3, "Chenmo Wang Er");
mapIntReverse.put(2, "Chenmo Wang Er");
mapIntReverse.put(1, "Chenmo Wang Er");
mapIntReverse.put(5, "Chenmo Wang Er");
mapIntReverse.put(4, "Chenmo Wang Er");

System.out.println(mapIntReverse);

TreeMap nudi konstruktor u koji se može proslediti pravilo sortiranja:

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

Comparator.reverseOrder() vraća objekat klase Collections.ReverseComparator, koji služi baš za obrtanje redosleda — veoma je zgodno.

private static class ReverseComparator
        implements Comparator<Comparable<Object>>, Serializable {
    // singleton obrazac, predstavlja komparator obrnutog redosleda
    static final ReverseComparator REVERSE_ORDER
            = new ReverseComparator();

    // implementacija metode compare — obrnuto poređenje dva objekta koja implementiraju Comparable
    public int compare(Comparable<Object> c1, Comparable<Object> c2) {
        return c2.compareTo(c1); // poziva compareTo() nad c2 sa c1 kao argumentom — obrnuto poređenje
    }

    // pri deserializaciji vraća Collections.reverseOrder() čime se održava singleton
    private Object readResolve() {
        return Collections.reverseOrder();
    }

    // vraća komparator prirodnog (rastućeg) redosleda
    @Override
    public Comparator<Comparable<Object>> reversed() {
        return Comparator.naturalOrder();
    }
}

Dakle, rezultat ispisa je sledeći:

{5=Chenmo Wang Er, 4=Chenmo Wang Er, 3=Chenmo Wang Er, 2=Chenmo Wang Er, 1=Chenmo Wang Er}

HashMap je neuređen i redosled umetanja se stalno menja kako broj elemenata raste. TreeMap, sa druge strane, od početka do kraja održava zadati redosled, što je za scenarije koji zahtevaju prilagođeno sortiranje zaista korisno!

03,Prednosti sortiranja

Pošto su elementi TreeMap-a sortirani, mnogo je lakše pronaći najveći, najmanji, ili sve ključeve veće ili manje od neke vrednosti.

Integer highestKey = mapInt.lastKey();
Integer lowestKey = mapInt.firstKey();
Set<Integer> keysLessThan3 = mapInt.headMap(3).keySet();
Set<Integer> keysGreaterThanEqTo3 = mapInt.tailMap(3).keySet();

System.out.println(highestKey);
System.out.println(lowestKey);

System.out.println(keysLessThan3);
System.out.println(keysGreaterThanEqTo3);

TreeMap je sve lepo predvideo i nudi metode poput lastKey() i firstKey() kojima se dohvataju poslednji, odnosno prvi ključ.

headMap() vraća ključeve do zadatog ključa (ne uključujući ga); tailMap() vraća ključeve od zadatog ključa (uključujući ga).

Pogledajmo rezultat:

5
1
[1, 2]
[3, 4, 5]

Još jedan primer:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "value1");
treeMap.put(2, "value2");
treeMap.put(3, "value3");
treeMap.put(4, "value4");
treeMap.put(5, "value5");

// Primer headMap — parovi ključ-vrednost sa ključem manjim od 3
Map<Integer, String> headMap = treeMap.headMap(3);
System.out.println(headMap); // Ispisuje {1=value1, 2=value2}

// Primer tailMap — parovi ključ-vrednost sa ključem većim ili jednakim 4
Map<Integer, String> tailMap = treeMap.tailMap(4);
System.out.println(tailMap); // Ispisuje {4=value4, 5=value5}

// Primer subMap — parovi ključ-vrednost sa ključem većim ili jednakim 2 i manjim od 4
Map<Integer, String> subMap = treeMap.subMap(2, 4);
System.out.println(subMap); // Ispisuje {2=value2, 3=value3}

Metode headMap, tailMap i subMap dohvatile su redom parove sa ključem manjim od 3, većim ili jednakim 4, te većim ili jednakim 2 i manjim od 4.

04,Kako odabrati Map

Pre nego što smo učili TreeMap, već smo obradili HashMap i LinkedHashMap — kako onda odabrati između ta tri?

Treba razmotriti sledeće:

Da li je potrebno sortiranje po prirodnom ili prilagođenom redu ključeva. Ako jeste, može se koristiti TreeMap; ako nije, HashMap ili LinkedHashMap.
Da li je potrebno održavati redosled umetanja. Ako jeste, može se koristiti LinkedHashMap; ako nije, TreeMap ili HashMap.
Da li je potrebna efikasna pretraga. Ako jeste, može se koristiti LinkedHashMap ili HashMap, jer je vremenska složenost njihove pretrage O(1), dok je za TreeMap O(log n).

LinkedHashMap interno čuva parove ključ-vrednost u heš tabeli i održava redosled umetanja dvostruko povezanom listom, ali se pretraga obavlja samo u heš tabeli i nema veze sa listom, pa je vremenska složenost O(1).

Evo i tabele, radi preglednosti.

Karakteristika	TreeMap	HashMap	LinkedHashMap
Sortiranje	DA	NE	NE
Redosled umetanja	Nije zagarantovan	Nije zagarantovan	Garantovan
Efikasnost pretrage	O(log n)	O(1)	O(1)
Zauzeće prostora	Obično veće	Obično manje	Obično veće
Odgovarajući scenario	Kada treba sortiranje	Kada sortiranje nije potrebno	Kada treba održavati redosled umetanja

To bi bilo to za čas — o TreeMap-u smo ovde završili i nadamo se da sada svi imate jasnu sliku o tome. Vidimo se na sledećem času!