이진 탐색 트리(binary search tree)는 이진 탐색 알고리즘의 개념을 기반으로 동적 자료 구조를 생성한다.

Section 1. 이진 탐색 트리 구조

트리: 노드의 분기 사슬로 구성된 계층적인 자료 구조.
- 트리 구조: 연결 리스트를 자연스럽게 확장한 것
- 트리 노드: 서로소(disjoint)인 하부 리스트를 가리키는 2가지 next 노드를 허용한다는 점.
노드: 값(어떤 주어진 타입의)을 포함하며, 트리의 하위 노드를 가리키는 포인터를 최대 두 개 가진다.
- 내부 노드(internal node): 자식이 하나 이상 있는 노드
- 리프 노드(leaf node): 어떤 자식도 없는 노드
- 노드는 필요에 따라 다른 정보를 포함할 수 있다.

TreeNode {
	Type: value
	TreeNode: left
	TreeNode: right
	TreeNode: parent
}

트리 노드 자료 구조는 외부 정보를 직접 저장할 수도 있고, 메모리의 다른 곳에 있는 복합 자료 구조를 가리키는 포인터를 저장할 수도 있다.
이진 탐색 트리는 맨 위에 있는 하나의 ‘루트(root, 뿌리) 노드’에서 시작하고, 계층을 내려가면서 가지를 뻗어나간다.
이 구조는 프로그램이 단 하나의 포인터-루트 노드의 위치-를 사용해 이진 탐색 트리에 접근할 수 있게 해준다.
탐색 트리의 개별 노드는 컴퓨터 메모리 전체에 분산될 수 있다. 각 노드는 포인터의 강력함과 유연성을 통해 자기 자식 및 부모에게만 연결되어 있다.

모든 노드 N에 대해, N의 왼쪽 하위 트리에 속한 모든 노드의 N의 값보다 작으며, N의 오른쪽 하위 트리에 속한 모든 노드의 값은 N의 값보다 크다.

값은 두 가지 역할을 한다.