이진 탐색은 전제 조건이 데이터 정렬이다.
데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리(Tree) 자료구조를 이용하여 항상 데이터가 정렬되어 있다.
트리 자료구조
트리 자료구조는 노드와 노드의 연결로 표현한다. 트리 자료구조는 그래프 자료구조의 일종으로, 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용된다.
-
트리는 부모 노드와 자식 노드의 관계로 표현된다.
-
트리의 최상단 노드를 루트 노드라고 한다.
-
트리의 최하단 노드를 단말 노드라고 한다.
-
트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.
-
트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.
이진 탐색 트리
이진 탐색 트리는 트리 자료구조 중에서 가장 형태가 간단하다. 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 코드를 배제하고 간단하게 동작 원리만 이해해 보도록 한다.
이진 탐색 트리의 특징
- 부모 노드보다 왼쪽 자식 노드가 작다.
- 부모 노드보다 오른쪽 자식 노드가 크다.
→ 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
📘 이것이 취업을 위한 코딩 테스트다 with 파이썬 :: chapter 07
