Site icon Java blog

Java #34: TreeSet (drzewo)

developeronthego
java treeset

Skoro były już tablice, zbiory i mapy, to teraz muszą być drzewa. 😉 Drzewami (ang. treeset, dosłownie: zbiór drzewa) nazywamy struktury danych które swoim wyglądem przypominają drzewa genealogiczne, które na pewno znasz z lekcji w podstawówce. Każde drzewo zawiera jeden korzeń (root) z którego wychodzą kolejne liście/węzły (nodes). Każdy następny węzeł staje się też korzeniem dla kolejnych liści, itd. Każdy element drzewa przechowują jakąś konkretną wartość.*

Pewnym specjalnym rodzajem drzewa są drzewa binarne:

Drzewo binarne charakteryzuje się tym, że każdy rodzic ma co najwyżej dwójkę dzieci. Specyficznym rodzajem drzewa binarnego jest binarne drzewo poszukiwań (ang. Binary Search Tree, BST). Jest to drzewo, które samo organizuje się, co w praktyce oznacza, że elementy występują w nim w sposób posortowany. Implementacją takiego drzewa jest właśnie omawiany tutaj TreeSet.

Właściwości TreeSet

Główną zaletą drzewa jest to, że jego elementy zawsze będą posortowane.

Spójrz na poniższy przykład:

Set<Integer> primeNumbers = new TreeSet<>();
primeNumbers.add(13);
primeNumbers.add(7);
primeNumbers.add(3);
primeNumbers.add(5);
primeNumbers.add(11);
primeNumbers.add(2);
		
System.out.println(primeNumbers);

Zadziwiające jest, że gdy wyświetlisz zawartość drzewa, to wynik będzie posortowany:

[2, 3, 5, 7, 11, 13]

Dzieje się tak dlatego, bo klasa Integer ma zaimplementowany interfejs Comparable, który posiada specjalną metodę compareTo, wykorzystywaną m. in. przez drzewa do posortowania wyników. TreeSet posiada wszystkie te same metody co każda inna implementacja interfejsu Set, jednak ma tą właściwość, że jeśli klasa używana przez tą kolekcję, będzie posiadała metodę compareTo to automatycznie wszystkie elementy zostaną posortowane. Minusem tego rozwiązania jest to, że taka struktura jest dużo wolniejsza niż HashSet.

Posortowane wartości poprzez interfejs Comparable

W kolejnym przykładzie, pokaże Ci jak zaimplementować samodzielnie compareTo w swojej stworzonej klasie, tak aby, drzewo posortowało je tak jak w przypadku klasy Integer. 

public class City implements Comparable<City>{
	private int id;
	private String name;
	private int population;
	
	public City(int id, String name, int population) {
		this.id = id;
		this.name = name;
		this.population = population;
	}
	@Override
	public int compareTo(City o) {
		return getPopulation() - o.getPopulation();
	}
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getPopulation() {
		return population;
	}
	public void setPopulation(int population) {
		this.population = population;
	}
	@Override
	public String toString() {
		return "City [id=" + id + ", name=" + name + ", population=" + population + "]";
	}
}

Metoda compareTo

Klasa City zawiera trzy pola: id, name i population, jeden konstruktor parametrowy, gettery, settery oraz metodę toString() (dla łatwiejszego wyświetlania zawartości). Niech będzie, że będę sortował po populacji miasta. W takim wypadku muszę zaimplementować interfejs Comparable i nadpisać metodę compareTo. Metoda ta zwraca zawsze liczbę całkowitą. Możesz sortować, po czym chcesz, nie tylko po liczbach, ale wtedy prawdopodobnie będziesz używać porównywania obiektów za pomocą metody equals, także pamiętaj, aby była ona także poprawnie zaimplementowana. W moim przypadku do porównywania populacji wystarczyło napisać różnicę między populacją jednego obiektu w stosunku do drugiego.

Sprawdzę teraz wynik mojej implementacji:

Set<City> cities = new TreeSet<>();
cities.add(new City(1, "Wrocław", 634500));
cities.add(new City(2, "Warszawa", 1735400));
cities.add(new City(3, "Gdańsk", 463925));
System.out.println(cities);

Wynik na konsoli:

[City [id=3, name=Gdańsk, population=463925], City [id=1, name=Wrocław, population=634500], City [id=2, name=Warszawa, population=1735400]]

Jak widzisz, TreeSet prawidłowo posortował miasta od najmniejszego do największego. W podobny sposób możesz też korzystać z klasy TreeMap, posiadając w ten sposób posortowane wartości mapy według klucza.

* Linki z informacjami odnośnie drzew:

Link do lekcji: https://github.com/developeronthego/java-middle/tree/master/src/main/java/middle/lesson17

Powtórka odnośnie sortowania: Algorytmy #3: sortowanie – przykłady

Exit mobile version