<PART 2> 트리 자료구조

데이터 베이스는 내부적으로 대용량 데이터 처리에 적합한 트리자료구조를 이용하여 항상 데이터가 정렬되어 있습니다.
따라서 데이터 베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠릅니다.

트리 자료구조는 노드와 노드의 연결로 표현합니다.

1. 트리는 부모 노드와 자식 노드의 관계로 표현합니다.
2. 트리의 최산당 노드를 루트 노드라고 합니다.
3. 트리의 최하단 노드를 단말노드라고 합니다.
4. 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 합니다.
5. 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합합니다.

정리하자면 큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능합니다. 그렇다면 이런 트리 구조를 이용하면 정확히 어떤 방식으로 항상 이진 탐색이 가능할까요?

- 이진 탐색 트리
트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리입니다.
이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조입니다.

이진 탐색 트리 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮으므로, 이진 탐색 트리가 미리 구현되어 있다고 가정하고 데이터를 조회하는 과정만 살펴보겠습니다.

1. 찾으려고 하는 원소의 값이 14입니다.
2. 부모노드와 찾는 '14'를 비교합니다.
3. 부모노드의 수가 더 작으므로 오른쪽 자식 노드를 방문합니다.
4. 오른쪽 자식노드인 '17'이 이번에는 부모노드입니다. 17이 14보다 크므로 왼쪽 노드에 방문합니다.
5. 현재 방문한 노드 값인 '14'와 찾는 원소값인 '14'와 동일합니다. 탐색을 마칩니다.
6. 만약에 자식 노드가 없을 때까지 원소를 찾지 못했다면, 이진 탐색 트리에 원소가 없는 것입니다.

이진 탐색 트리는 이 과정을 반복하는 것에 불과하니 위의 과정 그림을 이해하면 충분합니다.

- 빠르게 입력받기
데이터의 개수가 1000만개 이상이거나 탐색 범위의 크기가 1000억 이상이라면 이진 탐색 알고리즘을 사용해야합니다. 그리고 중요한 것은 그 만큼 입력 데이터가 많다는 것을 의미합니다. input()으로 데이터를 입력받으면 시간초과로 오답 판정을 받을 수 있습니다. 그러므로 sys 라이브러리의 readline()함수를 이용하여 시간 초과를 피해야 합니다.

위와 같이 입력받을 수 있습니다.
그러나 jupyter, spyder환경에서는 실행시 오류가 발생합니다.
jupyter notebook에는 stdin 이 제대로 구성되어 있지 않기 때문에 stdin.readline() 을 실행하면 입력을 받지 못하고 항상 빈 문자열이 반환됩니다.
따라서 jupyter환경에서 연습할때는 sydin.readline() 대신에 input() 을 사용해야 합니다.