트리(sys 라이브러리)

트리

이진 탐색의 전제 조건은 데이터가 정렬되어 있어야 한다. DB는 내부적으로 대용량 데이터 처리에 적합한 트리 구조를 사용하여 데이터가 항상 정렬되어 있다. 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있다.

1. 트리는 부모, 자식 노드로 구성

2. 최상단 노드 = 루트 노드

3. 최하단 노드 = 단말 노드

4. 일부를 때어내도 트리 구조이며 서브 트리라고 부른다.

5. 파일 시스템처럼 계층적이고 정렬된 데이터를 다루기 적합하다.

 

이진 탐색 트리

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다.

1. 부모 노드보다 왼쪽 자식 노드가 작다.

2. 부모 노드보다 오른쪽 자식 노드가 크다.

 

-이진 탐색 트리

1. 위 그림에서 37를 찾기 위해서는 먼저 루트 노드부터 방문한다. 30은 37보다 작아서 오른쪽으로 간다.

2. 48은 37보다 작아서 왼쪽 노드를 방문한다.

3. 37과 동일한 노드를 찾았다.

 

빠르게 입력받기

데이터의 개수가 1,000만 개가 넘거나 탐색 범위의 크기가 1,000억 이상이면 이진 탐색으로 풀어야 하는 경우가 많다.

그런데 이렇게 입력 데이터의 개수가 많은 문제에 input()을 사용하면 동작 속도가 느려진다. 따라서 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 사용하면 된다.

 

import sys

input_data = sys.stdin.readline().rstrip()

sys 라이브러리를 사용할 때는 한 줄 입력받고 rstrip() 함수를 꼭 호출해야 한다. 왜냐하면 readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이것을 제거하기 위해서 rstrip() 함수를 사용한다.