이진 탐색은 전제조건이 데이터 정렬이다.
DB는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 데이터가 정렬되어 있다.
트리 자료구조
- 트리는 부모 노드와 자식 노드의 관계로 표현된다.
- 최상단 노드: 루트노드
- 최하단 노드: 단말노드
- 트리에서 일부: 서브 트리
- 계층적이고 정렬된 데이터를 다루기에 적합하다.
트리 자료구조는 그래프 자료구조의 일종이다.
데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다.
이진 탐색 트리
가장 간단한 형태
이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다.
조건
- 부모 노드보다 왼쪽 자식 노드가 작다.
- 부모 노드보다 오른쪽 자식 노드가 크다.
왼쪽 자식 노드< 부모노드< 오른쪽 자식 노드
빠르게 입력받기
이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다.
HI there