트리(Tree)란?
데이터 사이의 계층 관계를 나타내는 자료구조
노드(node)와 가지(edge)로 구성된다.
- 루트 : 트리의 가장 윗부분에 위치하는 노드
- 리프 : 트리의 가장 아랫부분에 위치하는 노드
- 안쪽 노드 : 리프를 제외한 나머지 노드
- 자식 : 어떤 노드에서 가지로 연결된 아래쪽 노드
- 부모 : 어떤 노드에서 가지로 연결된 바로 위쪽 노드
- 형제 : 부모가 같은 노드
- 조상 : 어떤 노드에서 위쪽으로 뻗어 나간 모든 노드
- 자손 : 어떤 노드에서 아래쪽으로 뻗어 나간 모든 노드
- 레벨 : 루트로부터 얼마나 떨어져 있는지를 나타낸 값
- 차수 : 노드가 갖는 자식의 수
- 높이 : 루트에서 가장 멀리 떨어진 리프까지의 거리
- 서브트리 : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리
- 널 트리 : 노드가 전혀 없는 트리
- 순서 트리 : 형제 노드 사이의 순서 관계를 따지는 트리
- 무순서 트리 : 형제 노드 사이의 순서 관계를 따지지 않는 트리
순서 트리 탐색
e.g.) 이진트리
- 너비 우선 탐색(가로형 탐색) : 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 따라가다가 한 레벨에서 탐색이 끝나면 다음 레벨로 내려가는 방식의 탐색
- 깊이 우선 탐색(세로형 탐색) : 리프에 이를 때까지 아래로 내려가는 방식의 탐색
깊이 우선 탐색을 진행하면서 '언제 노드를 방문할지'에 대한 구분 - 전위 순회, 중위 순회, 후위 순회
- 전위 순회(preorder) : 노드 방문 → 왼쪽 자식 → 오른쪽 자식
- 중위 순회(inorder) : 왼쪽 자식 → 노드 방문 → 오른쪽 자식
- 후위 순회(postorder) : 왼쪽 자식 → 오른쪽 자식 → (돌아와) 노드 방문
이진트리(binary tree)
각 노드가 왼쪽 자식과 오른쪽 자식 둘을 갖는 트리
두 자식 가운데 한쪽이 없거나 둘 다 없는 노드가 포함되어도 이진트리의 조건을 만족한다.
cf.) 완전이진트리 : 루트에서 아래쪽 레벨로 내려가는 노드가 빠짐없이 채워져 있고, 또 같은 레벨에서는 왼쪽에서 오른쪽 노드가 빠짐없이 채워져 있는 이진트리
이진검색트리(binary search tree)
이진검색트리는 이진트리가 아래의 두 조건을 만족하면 된다.
1. 어떤 노드 N을 기준으로 왼쪽 서브트리 노드의 모든 키값은 노드 N의 키값보다 작다.
2. 오른쪽 서브트리 노드의 키값은 노드 N의 키값보다 크다.
이진검색트리의 특징 : 구조가 단순하다. 중위 순회를 하면 키값의 오름차순으로 노드를 얻을 수 있다. 이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있다. 노드를 삽입하는 것이 쉽다.
출처) Do it! 자료구조와 함께 배우는 알고리즘 입문 자바 편
