트리 자료구조

트리 자료구조

노드와 노드의 연결로 표현하며,

노드는 정보는 단위로서 어떠한 정보를 가지고 있는 개체로 이해 가능하다.

 

트리 자료구조의 특징

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

 

 

 

 

이진 탐색 트리

트리 자료구조에서 가장 간단한 형태

이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다.

 

이진 탐색 트리의 특징

• 부모 노드보다 왼쪽 자식 노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 크다.

 

 

 

 

빠르게 입력받기

이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓다.

이런 입력 데이터가 많은 문제에 input()을 사용하여 데이터를 입력받으면 동작 속도가 느려 시간 초과가 될 수 있다.

그래서 이 문제를 해결하기 위해 sys 라이브러리의 readline() 함수를 사용한다.

sys 라이브러리는 한 줄씩 입력받는다.

sys 라이브러리를 사용할 때는 한 줄 입력받고 난 후 반드시rstrip() 함수를 꼭 호출해야 한다.

readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 한다.

 

sys 라이브러리 사용

import sys

# 하나의 문자열 데이터 입력 받기
input_data = sys.stdin.readline().rstrip()
# 입력 받은 문자열 그대로 출력하기
print(input_data)