Binary Search Tree (이진 탐색 트리)

이진 탐색 트리란?
노드기반 이진 트리 데이터 구조.
속성
 * 노드의 왼쪽 하위트리는 노드의 키보다 작은 키를 가진 노드들만 가지고 있음.
 * 노드의 오른쪽 하위트리는 노드의 키보다 큰 키를 가진 노드들만 가지고 있음.
 * 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 함.
 * 중복된 노드가 없어야 함.


검색방법.
1. root 노드부터 시작
2. 트리가 null이면 값이 없음.
3. root와 키가 같으면 찾기 성공
4. 키가 루트보다 작으면 왼쪽 하위트리검색, 키가 루트보다 크면 오른쪽 하위트리 검색
5. 하위트리가 null이 될때까지 이 과정 반복.

검색 시간복잡도
평균 : O(log n)
나쁜경우 : O(n)

삽입
삽입은 검색부터 시작.
트리를 검색한 후 키와 맞는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입.

삭제
3가지 경우가 있음.
* 리프노드(자식노드가 없는 노드) 삭제 : 리프를 삭제하면 됨.
* 자식이 하나인 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 집어넣음.
* 자식이 2개인 노드 삭제 : 해당 노드의 왼쪽 자식노드에서 가장 큰값으로 대체하거나, 오른쪽 자식노드중 가장 작은 값으로 대체하고나서 선택된 노드를 삭제함.

참조
1. http://en.wikipedia.org/wiki/Binary_search_tree
2. http://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC