Kolekcje uporządkowane - TreeSet i TreeMap

Wstęp

Tym artykułem rozpoczniemy serię, w której szczegółowo omówimy komponenty zawarte w JCF (Java Collections Framework). Zakładam, że osoba czytająca te artykuły posiada już podstawową wiedzę o kolekcjach - mniej więcej na poziomie z kursu J2SE z naszego bloga. W tym artykule omówimy działanie kolekcji posortowanych, później przyjrzymy się samej klasie Collections, widokom i bardzo użytecznej metodzie stream().

SortedSet i NavigableSet

Zapewne korzystając do tej pory z Set'ów, używałeś implementacji HashSet. Jednak Java udostępnia interfejsy SortedSet i NavigableSet, które służą do obsługi zbiorów automatycznie sortowanych. Podstawową implementacją zbioru sortowanego jest klasa TreeSet, który został oparty o strukturę drzewa czerwono-czarnego. Omówimy ją na końcu tego artykułu.

Utworzymy teraz własną, pustą klasę, której obiekty dodamy do zbioru sortowanego.

W wyniku wykonania powyższego kodu otrzymam wyjątek ClassCastException - domyślnie TreeSet próbuje konwertować podane mu obiekty do typu ComparableSortedSet musi umieć porównywać obiekty, które w nim się znajdują. Generalnie mamy dwie opcje, możemy w klasie elementu zaimplementować interfejs Comparable lub do konstruktora zbioru podać obiekt klasy implementującej interfejs Comparator.

Przy poniższej implementacji klasy Fake, elementy będą sortowane w kolejności odwrotnej niż zostały dodane:

Wywołanie i output. Thread.sleep() jest dodany tylko po to, aby elementy zostały rozróżnione ( bez sleep'a compareTo zwracało 0).

Nie bez powodu używamy tu interfejsu SortedSet, a nie zwykłego Set. W SortedSetznajduje się kilka dodatkowych metod:

Użyjemy kilku z nich w poniższym programie:

Metody first()last() powinny być jasne, w każdym razie dzięki sortowaniu są realizowane w czasie stałym O( 1 ). Metody headSet()tailSet() zwracają TreeSetelementów, które są większe i mniejsze od elementu podanego jako argument.

TreeMap mapa z sortowanymi kluczami

Mapa drzewiasta - TreeMap jest w zasadzie rozwnięciem TreeSet, ponieważ zbiór kluczy mapy (który jest klasą wewnętrzną TreeMap) jest sortowany dokładnie tak samo jak TreeSet.

Klasa TreeMap zachowuje się niemal identycznie jak TreeSet np. jeśli jako klucz podamy obiekt klasy, której nie można porównywać, (ani za pomocą Comparable, ani Comparator), wygeneruje tak samo jak TreeSet wyjątek ClassCastException.

W interfejsie SortedMap znajdują się metody analogiczne dla SortedSet z tym, że operują na kluczach mapy, a nie jej wartościach:

Drzewo czerwono-czarne struktura danych pozwalająca na wydajne korzystanie z TreeSetTreeMap

Nie bez powodu klasy omawiane przed chwilą dostały nazwy z prefiksem Tree. Wedle dokumentacji wszystkie operacje na tree-mapie i tree-zbiorze czyli wyszukiwanie, wstawianie, usuwanie są realizowane w czasie O( log(n) ). Jest to możliwe dzięki zastosowaniu w ich implementacji drzew czerwno - czarnych.


Źródło: i.imgur.com

Takie drzewa muszą spełniać kilka warunków:

  • Każdy węzeł posiada co najwyżej dwóch synów - jednego z wartością większą, a drugie z wartością mniejszą od ojca
  • Każdy węzeł jest czerwony lub czarny.
  • Korzeń jest czarny.
  • Każdy liść jest czarny
  • Jeśli węzeł jest czerwony, to jego synowie muszą być czarni.
  • Każda ścieżka z ustalonego węzła do liścia liczy tyle samo czarnych węzłów.

Taka konstrukcja zapewnia nam to, że odszukanie dowolnego elementu w całym zbiorze będzie wymagała tylko log( n ) porównań.

Ten artykuł jest elementem poniższych kursów: