TreeMap 클래스

이진 탐색 트리

이진 탐색 트리는 각 노드가 키를 포함하며 모든 노드는 다음과 같은 속성이 있습니다.

1. 노드 왼쪽에 자식이 있다면 왼쪽 하위 트리의 모든 키는 노드에 있는 키보다 작습니다. 

2. 노드 오른쪽에 자식이 있다면 오른쪽 하위 트리의 모든 키는 노드에 있는 키보다 큽니다. 

 

트리 전체를 검색할 필요가 없어서 이진 탐색 트리에 있는 키의 검색 속도는 빠릅니다. 루트에서 시작하여 다음과 같은 알고리즘을 사용할 수 있습니다. 

1. 찾는 키인 target을 현재 노드의 키와 비교합니다. 같다면 검색이 완료됩니다. 

2. target이 현재 키보다 작으면 왼쪽 트리를 검색합니다. 왼쪽 트리에 없다면 target은 트리에 없습니다. 

3. target이 현재 키보다 크면 오른쪽 트리를 검색합니다. 오른쪽 트리에 없다면 target은 트리에 없습니다. 

 

트리의 각 수준에서 한 개의 자식 노드만 찾으면 됩니다. 

일반적으로 비교 횟수는 트리에 있는 키의 개수가 아니라 트리의 높이에 비례합니다. 

 

n = 2^h - 1

 

log₂n = h

log n에 비례하는 시간이 걸리는 알고리즘을 로그 시간이라고 합니다. 증가 차수는 O(log n)에 해당합니다.

/**
 *
 */
package com.allendowney.thinkdast;

import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

/**
 * Implementation of a Map using a binary search tree.
 *
 * @param <K>
 * @param <V>
 *
 */
public class MyTreeMap<K, V> implements Map<K, V> {

   private int size = 0;
   private Node root = null;

   /**
    * Represents a node in the tree.
    *
    */
   protected class Node {
      public K key;
      public V value;
      public Node left = null;
      public Node right = null;

      /**
       * @param key
       * @param value
       * @param left
       * @param right
       */
      public Node(K key, V value) {
         this.key = key;
         this.value = value;
      }
   }

   @Override
   public void clear() {
      size = 0;
      root = null;
   }

   @Override
   public boolean containsKey(Object target) {
      return findNode(target) != null;
   }

   /**
    * Returns the entry that contains the target key, or null if there is none.
    *
    * @param target
    */
   private Node findNode(Object target) {
      // some implementations can handle null as a key, but not this one
      if (target == null) {
            throw new IllegalArgumentException();
       }

      // something to make the compiler happy
      @SuppressWarnings("unchecked")
      Comparable<? super K> k = (Comparable<? super K>) target;

      // the actual search
       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;
   }

   /**
    * Compares two keys or two values, handling null correctly.
    *
    * @param target
    * @param obj
    * @return
    */
   private boolean equals(Object target, Object obj) {
      if (target == null) {
         return obj == null;
      }
      return target.equals(obj);
   }

   @Override
   public boolean containsValue(Object target) {
      return containsValueHelper(root, target);
   }

   private boolean containsValueHelper(Node node, Object target) {
   //이 메서드는 트리의 모든 노드를 방문하므로 실행시간은 노드의 개수에 비례합니다.
      if (node == null) {
         return false;
      }
      if (equals(target, node.value)) {
         return true;
      }
      if (containsValueHelper(node.left, target)) {
         return true;
      }
      if (containsValueHelper(node.right, target)) {
         return true;
      }
      return false;
   }

   @Override
   public Set<Map.Entry<K, V>> entrySet() {
      throw new UnsupportedOperationException();
   }

   @Override
   public V get(Object key) {
      Node node = findNode(key);
      if (node == null) {
         return null;
      }
      return node.value;
   }

   @Override
   public boolean isEmpty() {
      return size == 0;
   }

   @Override
   public Set<K> keySet() {
      Set<K> set = new LinkedHashSet<K>();
      addInOrder(root, set);
      return set;
   }

   /* Walks the tree and adds the keys to `set`.
    *
     * node: root of the tree
     * set: set to add the nodes to
     */
   private void addInOrder(Node node, Set<K> set) {
      if (node == null) return;
      addInOrder(node.left, set);
      set.add(node.key);
      addInOrder(node.right, set);
      
      //전통적인 중위 순회를 실행
      //node가 null이 아니면
      //1. 왼쪽 하위 트리를 순서대로 순회합니다.
      //2. node.key를 추가합니다.
      //3. 오른쪽 하위 트리를 순서대로 순회합니다. 
   }

   @Override
   public V put(K key, V value) {
      if (key == null) {
         throw new NullPointerException();
      }
      if (root == null) {
         root = new Node(key, value);
         size++;
         return null;
      }
      return putHelper(root, key, value);
   }
//put 메서드의 구현은 요소 개수인 n이 아닌 트리 높이인 h에 비례하는 시간이 걸립니다.
   private V putHelper(Node node, K key, V value) {
      //왼쪽 하위 트리가 비어 있으면, 즉 node.left가 null이면 키를 찾지 못하고 트리의 바닥에 이른 것입니다.
      //이때는 키가 트리에 없으며 어디로 가야 할지 알고 있습니다. 따라서 새로운 노드를 생성하고 이 노드를 node의 왼쪽 자식 노드로 추가합니다.

      //왼쪽 하위 트리가 비어 있지 않으면 왼쪽 하위 트리를 검색하기 위해 재귀 호출을 합니다. 
      @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;
   }

   @Override
   public void putAll(Map<? extends K, ? extends V> map) {
      for (Map.Entry<? extends K, ? extends V> entry: map.entrySet()) {
         put(entry.getKey(), entry.getValue());
      }
   }

   @Override
   public V remove(Object key) {
      // OPTIONAL TODO: FILL THIS IN!
      throw new UnsupportedOperationException();
   }

   @Override
   public int size() {
      return size;
   }

   @Override
   public Collection<V> values() {
      Set<V> set = new HashSet<V>();
      Deque<Node> stack = new LinkedList<Node>();
      stack.push(root);
      while (!stack.isEmpty()) {
         Node node = stack.pop();
         if (node == null) continue;
         set.add(node.value);
         stack.push(node.left);
         stack.push(node.right);
      }
      return set;
   }

   /**
    * @param args
    */
   public static void main(String[] args) {
      Map<String, Integer> map = new MyTreeMap<String, Integer>();
      map.put("Word1", 1);
      map.put("Word2", 2);
      Integer value = map.get("Word1");
      System.out.println(value);

      for (String key: map.keySet()) {
         System.out.println(key + ", " + map.get(key));
      }
   }

   /**
    * Makes a node.
    *
    * This is only here for testing purposes.  Should not be used otherwise.
    *
    * @param key
    * @param value
    * @return
    */
   public MyTreeMap<K, V>.Node makeNode(K key, V value) {
      return new Node(key, value);
   }

   /**
    * Sets the instance variables.
    *
    * This is only here for testing purposes.  Should not be used otherwise.
    *
    * @param node
    * @param size
    */
   public void setTree(Node node, int size ) {
      this.root = node;
      this.size = size;
   }

   /**
    * Returns the height of the tree.
    *
    * This is only here for testing purposes.  Should not be used otherwise.
    *
    * @return
    */
   public int height() {
      return heightHelper(root);
   }

   private int heightHelper(Node node) {
      if (node == null) {
         return 0;
      }
      int left = heightHelper(node.left);
      int right = heightHelper(node.right);
      return Math.max(left, right) + 1;
   }
}