[자료구조] 코드로 알아보는 java의 TreeMap

안녕하세요. 오늘은 코드로 알아보는 java의 자료구조 시간입니다. 오늘 알아볼 자료구조는 TreeMap입니다.

바로 그러면 알아보도록 하겠습니다.

TreeMap

기본적으로 TreeMap은 내부의 값들을 key 값을 기준으로 정렬하여 가지고 있습니다. 정렬된 순서를 알 수 없는 HashMap과는 차이가 있습니다. 아래 예제 코드를 한번 보도록 하겠습니다.

@Test
public void treeMapTest() {
    TreeMap<Integer, String> map = new TreeMap<>();
    map.put(3, "val");
    map.put(7, "val");
    map.put(8, "val");
    map.put(9, "val");
    map.put(10, "val");
    map.put(11, "val");
    map.put(12, "val");
    map.put(155, "val");
    map.put(168, "val");
    map.put(15976, "val");

    System.out.println("TreeMap.keySet().toString() = " + map.keySet().toString());
    // 결과 : TreeMap.keySet().toString() = [3, 7, 8, 9, 10, 11, 12, 155, 168, 15976]
}

비교를 위하여 일반 HashMap의 코드와 결과를 보도록 하겠습니다.

@Test
public void hashMapTest() {
    HashMap<Integer, String> map = new HashMap<>();
    map.put(3, "val");
    map.put(7, "val");
    map.put(8, "val");
    map.put(9, "val");
    map.put(10, "val");
    map.put(11, "val");
    map.put(12, "val");
    map.put(155, "val");
    map.put(168, "val");
    map.put(15976, "val");

    System.out.println("HashMap.keySet().toString() = " + map.keySet().toString());
    // 결과 : HashMap.keySet().toString() = [3, 7, 8, 168, 15976, 9, 10, 11, 155, 12]
}

결과만 두고보면 TreeMap은 key의 순서가오름차순으로 유지된 반면 HashMap은 예측할 수 없는 순서를 가지고 있다는 것을 알 수 있었습니다. 먼저 HashMap은 왜 오름차순으로 순서의 보장이 되지 않았을까요? 그 이유는 내부 구조에 있습니다. HashMap은 Key에 대해서 Hashcode 함수를 이용하고 이 값을 Bucket의 크기로 나눈 나머지를 index로 이용하며 index가 겹치면 LinkedList를 통하여 이어나갑니다. 이런 구조를 취하고 있기때문에 HashMap은 Key의 순서대로 순환을 하지 못하는 것입니다. HashMap에 대해서 좀 자세히 알고 싶으시다면 [자료구조] 코드로 알아보는 java의 Hashmap를 참고해 주시기바랍니다.

그렇다면 TreeMap은 어떤 구조를 취하고 있기에 Key의 순서를 유지할 수 있는 것일까요?

Red-Black Tree

red-black tree, wikipedia

결론부터 말씀드리면 TreeMap는 내부에 레드-블랙 트리(Red-Black Tree)의 자료구조를 이용하고 있습니다. 레드-블랙 트리는 이진탐색트리의 문제점을 보완한 트리입니다. 이진 탐색 트리의 문제점은 한쪽으로 치우쳐 진다면 기존의 O(logN)의 탐색속도가 최악의 경우 O(N)으로까지 떨어질 수 있습니다. 이런 경우를 보완하기 위해 레드-블랙 트리가 등장했습니다.

레드-블랙 트리는 balanced binary search tree로 항상 넣을때와 뺄때, 그리고 순회에 대해서 모두 O(logN)을 만족합니다. 원리를 간단하게 말씀드리면 레드와 블랙으로 노드의 색깔을 칠하고 데이터를 넣을때(Insert)와 뺄때(Delete) Restructuring과 Recoloring라는 추가 프로세스로 진행하여 균형을 맞춥니다. "루트부터 리프노드까지의 블랙 노드의 개수는 같다."라는 것을 기조로 합니다. 레드-블랙 트리의 조건을 맞추면 루트로부터 리프까지의 최소길이와 최대길이의 차이가 2배 이하로 되게됩니다.

코드를 통한 확인

그렇다면 TreeMap의 코드를 한번 보도록 하겠습니다.

클래스 상속 구조

클래스 상속구조입니다. HashMap과 동일하게 AbstractMap을 상속받고 있습니다. 또한 특이한 부부은 NavigableMap을 implements 받고 있습니다. NavigableMap은 정렬된 Map에서 여러가지 방법의 탐색을 제공합니다.

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

내부 변수

내부 변수를 한번 보도록 하겠습니다. 기존 HashMap과는 변수부터 전혀 다르다는 것을 알 수 있었습니다. 먼저 정렬을 위해 사용되는 Compator 변수가 있으며 Entry는 Tree에 맞게 root의 이름을 가지고 있는 것을 알 수 있엇습니다.

/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;

private transient Entry<K,V> root;

/**
* The number of entries in the tree
*/
private transient int size = 0;

/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;

생성자

이어서 생성자를 알아보도록 하겠습니다. 생성자에 파라미터를 주지않고 기본으로 생성할 수 있으며, 정렬하고싶은 Key를 파라미터로하여 생성하는 것도 가능합니다.

public TreeMap() {
    comparator = null;
}

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

생성

Map에 데이터를 넣는 put 메서드를 한번 보도록 하겠습니다. return 값을 가지고 있습니다. key 충돌이 나면 이전의 값을 리턴하고 새로운 값을 넣도록 로직이 되어있는것을 알 수 있었습니다. 각 코드의 설명은 주석으로 달아두었습니다.

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // 타입 체크 아래 compare method 참고

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) { // 비교 Key 명시 되어있을 경우
        do {  // 새로들어온 값을 루트부터 차례대로 비교해나간다.
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) // 새로들어온 key가 parent에 더 작다
                t = t.left;
            else if (cmp > 0) // 새로들어온 key가 parent에 배해 더 크다
                t = t.right;
            else
                return t.setValue(value); // 같을 경우 값을 교체하고 이전 값 리턴
        } while (t != null);
    }
    else { // 비교 Key 명시 X
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            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);
    }

    // 새로 들어온 key, value의 노드에서 parent를 연결
    Entry<K,V> e = new Entry<>(key, value, parent); 
    if (cmp < 0) // parent에서 자식 Node와 연결
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e); // 한쪽으로 취우쳐 지지않도록 균형을 잡아준다. (레드블랙트리 알고리즘 참고)
    size++;
    modCount++;
    return null;
}

@SuppressWarnings("unchecked")
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

삭제

이번에는 삭제를 한번 보도록 하겠습니다. 삽입과 마찬가지로 삭제시에도 Tree를 재조정하는 일은 필요합니다. 삭제하려는 노드의 자식이 오른쪽 왼쪽에 모두 있다면 삭제 후 직후(오른쪽 X)의 원소와 자리를 교체한 후 삭제합니다. 색상을 건드리지 않은 채 키만 바뀌는 것으로는 트리의 특성에 영향을 미치지 않습니다. 삭제 이후에 레드-블랙 트리의 규칙에 위반되지 않도록 재배치가 필요합니다.

/**
* Delete node p, and then rebalance the tree.
*/
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // 양쪽 노드를 다 가지고 있다면 직후 노드와 위치 변경
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }

    // Start fixup at replacement node, if it exists.
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

순환

TreeMap은 왼쪽 노드는 부모노드보다 작고 오른쪽 노드는 부모노드보다 값이 큽니다. 따라서 오름차순으로 순환하기 위해서는 중위순환으로 트리를 탐색해야합니다. 즉, 가장 왼쪽 노드를 먼저 반환하고 다음은 부모노드, 그리고 오른쪽 노드의 순서로 반환하는 것입니다.

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    Objects.requireNonNull(action);
    int expectedModCount = modCount;
    for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) { // getFirstEntry()는 가장 왼쪽 노드를 반환한다.
        action.accept(e.key, e.value);

        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }
    }
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) { // 오른쪽 (본인 보다 큰 값) 값이 있으면
        Entry<K,V> p = t.right; // 오른쪽 노드 반환
        while (p.left != null)
            p = p.left;
        return p;
    } else { // 오른쪽 (본인 보다 큰 값) 값이 없으면
        Entry<K,V> p = t.parent; // 부모노드 반환
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

마무리

오늘은 이렇게 Java의 TreeMap에 대해서 알아보는 시간을 가져보았습니다. Java의 TreeMap은 레드-블랙 트리를 기반으로 하고 있다는 사실을 코드로 알 수 있었습니다.

레드-블랙 트리에 대해서 좀 더 자세히 알고 싶으신 분들은 Zedd0202님의 알고리즘 ) Red-Black Tree 글을 보시면 이미지와 함께 정말 자세하게 설명해 주셔서 저도 도움이 많이 됬습니다! 여러분들도 자세한 로직이 궁금하시면 해당 포스팅을 참고해주세요.

감사합니다.

참조

baeldung_java-treemap

geeksforgeeks_treemap-in-java

Zedd0202님의 알고리즘 ) Red-Black Tree

[덕`s IT Story님의 레드블랙-트리Red-black-tree](https://itstory.tk/entry/레드블랙-트리Red-black-tree)