[Think Data Structures] 이진탐색트리(TreeMap) 구현 및 분석_2

이진 탐색 트리(binary search tree, BST)

---

트리로 구현된 맵의 성능을 시험. MyTreeMap 클래스를 구현하고, 문제점을 알아본 후  자바의 TreeMap 클래스가 어떻게 문제를 해결했는지 알아보자.

내부 class인 Node 클래스를 구현

protected class Node{
    public K key;
    public V value;
    public Node left = null;
    public Node right = null;
    
    public Node(K key, V value){
        this.key = key;
        this.value = value;
    }
}

노드를 찾는 findNode 메서드 구현

private Node findNode(Object target){
    if(target == null){
        throw new IllegalArgumentException();
    }
    
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) target;
    
    // 탐색
    Node node = root;
    while(node != null){
        int cmp = k.compareTo(node.key);
        if(cmp < 0){
            node = node.left;
        }else if(cmp > 0){
            node = node.right;
        }else{
            return node;
        }
    }
    
    return null;
}

findNode 메서드는 get과 containsKey 메서드에서 호출하는 메서드이다.

compareTo 메서드를 호출하기 전에 target 인자를 형변환하여 Comparable 객체를 만들어야 한다. 여기서 사용한 타입 와일드 카드는 가능한 허용한다.Comparable 인터페이스를 구현한 어떤 타입과도 동작하그 그 타입의 compareTo 메서드는 K 또는 K의 상위 타입까지 받는다.

@Override
public boolean containsKey(Object key) {
    return findNode(key) != null;
}
 
@Override
public V get(Object key) {
    Node node = findNode(key);
    return node == null ? null : node.value;
}

값 탐색하기

전체 트리를 검색할 필요가 없으므로 findNode 메서드의 실행시간은 트리의 높이에 비례하고 노드의 개수에 비례하지 않는다.

하지만 containsValue는 키가 아니라 값을 검색해야 하므로 전체 트리를 검색해야 한다.(BST 속성은 값에 해당하지 않기 때문이다.)

@Override
public boolean containsValue(Object value) {
    return containsValueHelper(root, value);
}
 
private boolean containsValueHelper(Node node, Object value) {
    if(node == null) {
    return false;
    }
    if(equals(value, node.value)) {
    return true;
    }
    if(containsValueHelper(node.left, value)) {
    return true;
    }
    if(containsValueHelper(node.right, value)) {
    return true;
    }
    return false;
}

재귀적으로 호출하여 모든 트리를 탐색한다.

1. 첫 번째 if 문은 노드가 null이면 대상을 찾지 못하고 트리의 바닥에 이른 것이므로 false를 반환. (한쪽 경로에만 없다는 의미로 여전히 다른쪽에는 있을 가능성이 있음)
2. 두 번째 if문은 원하는 것을 찾았는지 확인. 찾았다면 true, 못찾았다면 false
3. 세 번째 if문은 왼쪽 하위 트리에서 target을 찾는 재귀적인 호출을 함. 찾으면 오른쪽 하위 트리는 찾지 않고 즉시 true를 반환 찾지 못하면 계속 진행
4. 네 번째 if문은 오른쪽 하위 트리를 탐색. 찾지 못하면 전체 트리를 검색하였으므로 false를 반환

트리의 모든 노드를 방문하므로 실행시간은 노드의 개수(n)에 비례함

put 메서드 구현하기

• 주어진 키가 트리에 이미 있으면 값을 대체하고 기존값을 반환
• 주어진 키가 트리에 없으면 올바른 위치에 새로운 노드를 추가

@Override
public V put(K key, V value) {
    if(key == null){
        throw new IllegalArgumentException();
    }
    
    if(root == null){
        root = new Node(key, value);
        size++;
        return null;
    }
    
    return putHelper(root, key, value);
}
 
private V putHelper(Node node, K key, V value){
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    
    int cmp = k.compareTo(node.key);
    if(cmp < 0){
        if(node.left == null){
            node.left = new Node(key, value);
            size++;
            return null;
        }else{
            return putHelper(node.left, key, value);
        }
    }
    
    if(cmp > 0){
        if(node.right == null){
            node.right = new Node(key, value);
            size++;
            return null;
        }else{
            return putHelper(node.right, key, value);
        }
    }
    
    V oldValue = node.value;
    node.value = value;
    return oldValue;
}

첫 번째 인자인 node는 초기에는 트리의 루트이다.

재귀 호출을 할때마다 다른 하위 트리를 참조. compareTo 메서드를 호출하여 트리의 어느 경로를 따라 가야할지 확인

cmp < 0 이면, key가 node.key보다 작으므로 왼쪽 하위 트리를 검색

• 왼쪽 하위 트리가 비어있으면(null 반환) 키를 찾지 못하고 트리의 바닥에 이른 것이다. 이때는 키가 트리에 없으므로 새로운 노드를 생성하고 이 노드를 왼쪽 자식 노드로 추가한다.
• 왼쪽 하위 트리가 비어있지 않으면 왼쪽 하위 트리를 검색하기 위해 재귀 호출을 한다.

cmp > 0 이면, key가 node.key보다 크므로 오른쪽 하위 트리를 검색

cmp == 0 이면 트리에서 키를 찾은 것이므로 값을 대체하고 기존 값을 반환

중위 순회

Map의 다른 구현에서 keySet 메서드가 반환하는 키들은 특별한 순서가 없지만, 트리 구현의 장점 중 하나는 단순하고 효율적으로 키를 정렬할 수 있다는 것이므로 이러한 장점을 활용한다.

순서를 유지하는 Set 구현체인 LinkedHashSet 객체를 생성하여 중위 순회(in-order traversal)를 실행

@Override
public Set<K> keySet() {
    Set<K> set = new LinkedHashSet<K>();
    inorder(root, set);
    return set;
}
 
// 중위순회
public void inorder(Node root, Set<K> set){
    if(root != null) {
    inorder(root.left, set);
    set.add(root.key);
    inorder(root.right, set);
    }
}

1. 왼쪽 하위 트리를 순서대로 순회
2. node.key를 추가
3. 오른쪽 하위 트리를 순서대로 순회

로그 시간 메서드

MyTreeMap 클래스 get, put은 실행시간이 트리의 높이인 h에 비례한다.

자가 균형 트리

트리가 불균형하면 탐색이 굉장히 오랜 시간이 걸릴 수 있다.

이 문제를 해결할 수 있는 방법은 키가 순서대로 들어오더라도 이를 대응하도록 트리를 만드는 것이다.

put 메서드를 고쳐서 트리가 불균형해질 때 이를 탐지하고 불균형하다면 노드를 재배열하는 것이다. (이 기능을 자가 균형이라고 함)

일반적인 자가 균형 트리에는 AVL 트리와 레드-블랙 트리가 있다.

자바의 TreeMap 클래스는 레드블랙트리를 이용

※나머지 구현은 https://github.com/ksh901016/thinkDataStructure/ 에서 확인

(values메스드에, BFS DFS 로 트리를 순회하게도 구현하였음)