[Algorithm] TreeMap

★TreeSet과 그 원리는 같으나 Node에 뭔가 하나가 더 딸려서 저장된다는 것이 조금 다르다. TreeSet은 key가 정렬 기준이고, 저장된 데이터였지만 TreeMap은 데이터 Object를 key로 정렬하는 것이다. 따라서 TreeMap은 <OBJECT, KEY>의 Entry형태로 만든다.

★TreeMap

public class MyTreeMap implements Map {
	
	private Node root = null;
	
	public MyTreeMap() {
		this.root = null;
	}

	@Override
	public boolean contains(int key) {
		Node cur = root;
		while (cur != null) {
			if (cur.key == key) return true;
			else if (cur.key > key) {
				cur = cur.left;
			} else {
				cur = cur.right;
			}
		}
		return false;
	}
	
	@Override
	public String get(int key) {
		Node cur = root;
		while (cur != null) {
			if (cur.key == key) return cur.value;
			else if (cur.key > key) {
				cur = cur.left;
			} else {
				cur = cur.right;
			}
		}
		return null;
	}
	
	@Override
	public boolean insert(int key, String value) {
		Node newNode = new Node(key, value);
		if (root == null) {
			root = newNode;
			return true;
		}
		
		Node parent = null;
		Node cur = root;
		while (true) {
			if (cur.key == key) {
				cur.value = value;
				return true;
			}
			else if (cur.key > key) {
				parent = cur;
				cur = cur.left;
				if (cur == null) {
					parent.left = newNode;
					return true;
				}
			} else {
				parent = cur;
				cur = cur.right;
				if (cur == null) {
					parent.right = newNode;
					return true;
				}
			}
		}
	}
	
	@Override
	public boolean remove(int key) {
		Node parent = null;
		Node cur = root;
		boolean isLeftChild = false;
		
		while (true) {
			if (cur == null) return false;
			if (cur.key == key) {	//	탐색 종료
				break;
			}
			else if (cur.key > key) {	//	좌측 트리 탐색
				parent = cur;
				cur = cur.left;
				isLeftChild = true;
			} else {	//	우측 트리 탐색
				parent = cur;
				cur = cur.right;
				isLeftChild = false;
			}
		}
		
		//	cur : 삭제할 노드
		//	parent : 삭제할 노드의 부모 노드
		//	isLeftChild : 삭제할 노드가 부모노드의 좌측 자식이면 true
		//	자식 노드가 없을 때
		if (cur.left == null && cur.right == null) {
			if (cur == root) {
				root = null;
			} else if (isLeftChild) {
				parent.left = null;
			} else {
				parent.right = null;
			}
		}
		//	왼쪽에만 자식 노드가 있을 때
		else if (cur.left != null && cur.right == null) {
			if (cur == root) {
				root = cur.left;
			} else if (isLeftChild) {
				parent.left = cur.left;
			} else {
				parent.right = cur.left;
			}
		}
		//	오른쪽에만 자식 노드가 있을 때
		else if (cur.left == null && cur.right != null) {
			if (cur == root) {
				root = cur.right;
			} else if (isLeftChild) {
				parent.left = cur.right;
			} else {
				parent.right = cur.right;
			}
		}
		//	양쪽에 자식 노드가 있을 때
		else {
			//	대체할 노드를 찾고 트리에서 제거.
			//	삭제 노드의 왼쪽 서브트리의 최대노드를 대체 노드로 하기로 한다.
			//	대체 노드는 반드시 자식이 하나 뿐이므로 위의 알고리즘으로 삭제할 수 있다.
			Node replace = detachReplacementNode(cur);
			if (cur == root) {
				root = replace;
			} else if (isLeftChild) {
				parent.left = replace;
			} else {
				parent.right = replace;
			}
			replace.left = cur.left;
			replace.right = cur.right;
		}
		return true;
	}
	
	//	대체할 노드를 찾아 트리에서 제거
	private Node detachReplacementNode(Node root) {
		Node parent = root;
		Node node = root.left;
		while (node.right != null) {
			parent = node;
			node = node.right;
		}
		
		if (parent == root) {
			parent.left = node.left;
		} else {
			parent.right = node.left;
		}
		
		return node;
	}
	
	public void print() {
		if (root == null) {
			System.out.println("empty");
			return;
		}
		print(root);
		System.out.println();
	}
	
	private void print(Node node) {
		if (node == null) return;
		print(node.left);
		System.out.print(node.key + "[" + node.value + "]");
		print(node.right);
	}

	private class Node {
		private int key;
		private String value;
		private Node left;
		private Node right;
		
		public Node(int key, String value) {
			this.key = key;
			this.value = value;
		}
	}
}