[알고리즘] Tree 3 - Binary Serch Tree

- 각 노드에 값이 있으며 키값은 모두 달라야 한다. 값들은 순서가 있다.
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 가진 노드로 구성된다.
- 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 가진 노드로 구성된다.
- 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
- 중복된 노드가 없어야 한다.

노드 추가


노드 검색

노드 삭제
1. 자식 노드가 없으면 그냥 삭제한다.
2. 자식 노드가 하나면 자식 노드를 해당 노드 자리에 대체하고 삭제한다.
3. 자식 노드가 두개면 왼쪽 서브 트리의 가장 오른쪽 값이나, 오른쪽 서브 트리의 가장 왼쪽 값으로 대체하고 삭제한다.

노드 삭제 3번째 경우

최악의 경우

구현