트리 자료구조 - 이진 탐색 트리

노드와 노드의 연결로 표현된 형태를 말하며 여기서 말하는 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체이다.

 

# 특징

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

-이진탐색트리

• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 탐색 방법 : 부모 노드와 타켓 비교(더 작은 경우 왼쪽으로 이동, 더 클 경우 오른쪽으로 이동) -> 찾을 때까지 반복
• 방문 순서 ex)37 : 30 - 48 -37