이진 탐색(2) 이진 탐색 트리

이진 탐색 트리

• 모든 트리가 다 이진 탐색 트리는 아니다
• 이진 탐색 트리는 부모 노드보다 왼쪽 자식 노드가 작고, 오른쪽 자식 노드가 크다는 특징을 갖는다
• 간단하게 표현하면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 성립해야 이진 탐색 트리라고 말할 수 있다

• 37을 찾는 탐색을 이진 탐색 트리로 진행해보자
• 이진 탐색은 루트 노드부터 방문한다. 루트 노드는 30이고, 찾는 원소 값은 37이다
• 이진 탐색 트리의 특징에 의해, 찾는 원소값인 37은 루트 노드보다 크기 때문에 왼쪽 노드는 확인할 필요가 없다
• 따라서 오른쪽 노드를 방문한다. 오른쪽 노드의 값은 48이다
• 찾는 원소값인 37은 48보다 작으므로, 왼쪽 노드를 방문한다
• 현재 방문한 노드의 값이 찾는 원소 값과 동일하므로 탐색을 종료한다.

 

빠르게 입력 받기

• input() 함수는 동작 속도가 느려서 시간 초과가 발생할 수도 있다
• 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 사용해 시간 초과를 피할 수 있다

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

• sys 라이브러리를 사용해 입력받는 경우, 한 줄 입력받고 반드시 rstrip() 함수를 호출해야 한다
• readline()으로 입력받은 경우 엔터가 개행 문자로 입력된다
• 이 공백 문자를 제거하기 위해 rstrip() 함수를 사용해야 한다