의의
대상 정보의 각 항목들을 계층적으로 연관되도록 구조화할 때 사용 (비선형 자료구조)
나무가 거꾸로 된 형태로 저장하는 자료구조
가장 기본이 되는 유형은 이진트리 (binary tree) 자료구조 : 두개의 자식 노드를 가진 트리 형태
- Node : 트리 구조의 교점.
- Root Node : 시작점이 되는 노드
- Edge : 트리를 구성하기 위해 노드 간 연결하는 선
- level : 특정 깊이를 가지는 노드의 집합
- degree : 하위 트리 개수
- internal Node : leaf 노드를 제외한 중간에 위치한 노드들
- leaf Node : 하위에 다른 노드가 연결되어 있지 않는 노드
=> 트리의 가장 중요한 속성은 루트 노드를 제외한 모든 노드는 하나의 부모 노드만을 가진다.
데이터 저장의 의미보다는 저장된 데이터를 효과적으로 탐색하기 위해 사용되는 툴
트리의 탐색
이진 트리 : 최대 2개의 자식 노드를 가질 수 있음
이 두 개의 자식노드를 left node와 right node라고 하며 left node는 부모의 node값보다 적은 값이 저장/ right node는 크거나 같은 값이 저장
이진 트리는 log N이므로 리스트보다 검색이 훨씬 효율적임
Adventurer