Java for Beginner

Введение в TreeMap, принципы работы и внутреннее устройство

TreeMap — это реализация интерфейса NavigableMap, основанная на красно-черном дереве. Он предоставляет отсортированное отображение ключей и является мощным инструментом для хранения отсортированных данных.

Основные особенности TreeMap

Отсортированное отображение: Ключи в TreeMap всегда отсортированы в порядке возрастания, если не указан другой компаратор.
Красно-черное дерево: Использует самобалансирующееся бинарное дерево для хранения элементов.
Эффективность: Операции вставки, удаления и поиска выполняются за O(log n).

Внутреннее устройство TreeMap

Красно-черное дерево — это тип самобалансирующегося бинарного дерева поиска с следующими свойствами:

Каждый узел либо красный, либо черный.
Корень дерева всегда черный.
Все листья (NULL-указатели) считаются черными.
Красный узел не может иметь красных дочерних узлов (т.е., красные узлы не могут быть рядом).
Любой путь от корня до листа содержит одинаковое количество черных узлов.

Класс Entry

Внутренний класс Entry представляет узел в дереве:

static final class Entry<K, V> implements Map.Entry<K, V> {
    K key;
    V value;
    Entry<K, V> left, right, parent;
    boolean color = BLACK;

    Entry(K key, V value, Entry<K, V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    public K getKey() { return key; }
    public V getValue() { return value; }
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
}

Принципы работы TreeMap

Вставка
При вставке элемента TreeMap сначала находит подходящее место для нового элемента, а затем вставляет его как красный узел и балансирует дерево.

Удаление
Удаление элемента включает три основных шага:
Найти узел для удаления.
Удалить узел.
Балансировать дерево, если это необходимо.

Поиск
Поиск элемента осуществляется путем последовательного сравнения ключей и движения по дереву (влево или вправо), пока не будет найден нужный ключ.

Основные методы TreeMap

Метод put
Метод put добавляет пару ключ-значение в TreeMap:

public V put(K key, V value) {
    Entry<K, V> t = root;
    if (t == null) {
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K, V> parent;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) t = t.left;
            else if (cmp > 0) t = t.right;
            else return t.setValue(value);
        } while (t != null);
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0) t = t.left;
            else if (cmp > 0) t = t.right;
            else return t.setValue(value);
        } while (t != null);
    }
    Entry<K, V> e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

Метод get
Метод get возвращает значение по ключу:

public V get(Object key) {
    Entry<K, V> p = getEntry(key);
    return (p == null ? null : p.value);
}

final Entry<K, V> getEntry(Object key) {
    if (comparator != null) return getEntryUsingComparator(key);
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K, V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0) p = p.left;
        else if (cmp > 0) p = p.right;
        else return p;
    }
    return null;
}

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://javarush.com/groups/posts/2584-osobennosti-treemap
https://www.baeldung.com/java-treemap

#Java #Training #Medium #TreeMap

Baeldung

A Guide to TreeMap in Java | Baeldung

A quick and practical guide to TreeMap in Java.

179 viewsДен, 04:52

Java for Beginner

Основные методы TreeMap и их применение

Конструкторы TreeMap

Без параметров

TreeMap<String, Integer> map = new TreeMap<>();

С компаратором

TreeMap<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());

Из другого Map

Map<String, Integer> anotherMap = new HashMap<>();
TreeMap<String, Integer> map = new TreeMap<>(anotherMap);

Из SortedMap

SortedMap<String, Integer> sortedMap = new TreeMap<>(anotherMap);
TreeMap<String, Integer> map = new TreeMap<>(sortedMap);

Основные методы TreeMap

Метод put

Добавляет пару ключ-значение. Если ключ уже существует, то значение обновляется.

TreeMap<String, Integer> map = new TreeMap<>();
map.put("Apple", 50);
map.put("Banana", 30);
map.put("Orange", 20);

Метод get

Возвращает значение, связанное с указанным ключом.

Integer value = map.get("Apple");
System.out.println("Value for key 'Apple': " + value);

Метод remove

Удаляет запись по ключу и возвращает удаленное значение.

Integer removedValue = map.remove("Banana");
System.out.println("Removed value: " + removedValue);

Метод containsKey

Проверяет, содержится ли ключ в карте.

boolean contains = map.containsKey("Orange");
System.out.println("Contains key 'Orange': " + contains);

Метод containsValue

Проверяет, содержится ли значение в карте.

boolean containsValue = map.containsValue(20);
System.out.println("Contains value 20: " + containsValue);

Метод size

Возвращает количество элементов в карте.

int size = map.size();
System.out.println("Size of the map: " + size);

Метод isEmpty

Проверяет, пуста ли карта.

boolean isEmpty = map.isEmpty();
System.out.println("Is the map empty: " + isEmpty);

Метод clear

Очищает карту, удаляя все элементы.

map.clear();
System.out.println("Size after clear: " + map.size());

Специфические методы TreeMap

Метод firstKey

Возвращает первый (минимальный) ключ.

String firstKey = map.firstKey();
System.out.println("First key: " + firstKey);

Метод lastKey

Возвращает последний (максимальный) ключ.

String lastKey = map.lastKey();
System.out.println("Last key: " + lastKey);

Метод pollFirstEntry

Удаляет и возвращает первый (минимальный) элемент.

Map.Entry<String, Integer> firstEntry = map.pollFirstEntry();
System.out.println("Polled first entry: " + firstEntry);

Метод pollLastEntry

Удаляет и возвращает последний (максимальный) элемент.

Map.Entry<String, Integer> lastEntry = map.pollLastEntry();
System.out.println("Polled last entry: " + lastEntry);

Примеры использования TreeMap

Пример 1: Печать элементов в порядке возрастания ключей

TreeMap<String, Integer> map = new TreeMap<>();
map.put("Apple", 50);
map.put("Banana", 30);
map.put("Orange", 20);

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Пример 2: Использование метода subMap

Возвращает отображение части карты.

map.put("Grapes", 40);
SortedMap<String, Integer> subMap = map.subMap("Apple", "Orange");
for (Map.Entry<String, Integer> entry : subMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Пример 3: Получение диапазона ключей

NavigableMap<String, Integer> tailMap = map.tailMap("Banana", true);
for (Map.Entry<String, Integer> entry : tailMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

#Java #Training #Medium #TreeMap

170 viewsДен, 14:05

About

Blog

Apps

Platform