Tree
트리는 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로, 부모 - 자식 관계로 표현된다.
스택, 큐와는 달리 2차원의 자료 구조로, 정점(node)와 간선(edge)를 이용해 데이터의 배치 형태를 추상화시킨다.
트리의 기본 특징
- 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다.
- 트리내에 또 다른 트리가 있는 재귀적 자료구조이다.
- 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조이다.
- 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다.
- 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다,
트리의 구성 요소
- 정점(node): 데이터를 직접적으로 담고 있는 요소
- 간선(edge): 노드를 잇는 연결선
- 뿌리(root) 노드: 최상위 노드로, 부모 노드가 없이 자식 노드만 가질 수 있다.
- 잎(leaf) 노드: 최하위 노드로, 자식 노드가 없다.
- 내부(internal) 노드: 자식이 있는 노드
- 부모(parent) 노드: 위아래로 연결된 두 노드 중 상위 계층의 노드
- 자식(child) 노드: 위아래로 연결된 두 노드 중 하위 계층의 노드
- 형제(sibling) 노드: 같은 부모 노드를 가진 노드들
- 조상(ancestor): 부모의 부모노드를 타고 가며 만나는 노드들
- 후손(descendant): 자식의 자식노드를 타고 가며 만나는 노드들
- 깊이(Depth) : 루트 노드에서 해당 노드까지 도달하는 데 사용하는 간선의 갯수
- 레벨(Level) : 노드의 깊이(depth+1) : 해당 트리 내 모든 노드의 높이 중 최댓
- 차수(degree) : 노드의 자식 수. 트리의 차수라고 하면 해당 트리 내 모든 차수 중 최댓값이라는 의미다.
트리의 장점
- (Dynamic) Array나 Linked List에서는 삽입이나 삭제를 수행하는데 O(N) 시간이 소요되지만, 트리는 편향 트리가 아닌 이상 일반적으로 삽입/삭제 수행 시 O(logN) 시간이 소요된다. 그래서 삽입/삭제 및 검색에 유용하다.
- 계층적 관계를 표현하는 데 용이하다. (파일, 폴더 저장 등)
트리순회
다음과 같은 트리가 있을 때를 예시로 들어 트리의 순회 과정을 살펴보자.
- 전위 순회 : 각 루트(Root)를 순차적으로 먼저 방문하는 방식 (Root → 왼쪽 자식 → 오른쪽 자식)
1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14 - 중위 순회 : 왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식 (왼쪽 자식 → Root → 오른쪽 자식)
8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7 - 후위 순회 : 왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식 (왼쪽 자식 → 오른쪽 자식 → Root)
8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1
Binary Tree
Binary Tree란 자식을 최대 2개만 가지는 트리를 말한다.
Binary Tree에는 전이진트리, 완전이진트리, 포화이진트리, 균형이진트리, 편향이진트리가 있다.
먼저 전 이진트리란, 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리를 말한다.
완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리를 말한다. 또한 마지막 레벨은 노드가 왼쪽에서 오른쪽으로 채워져야 한다. (꽉 차있지는 않아도 된다.)
포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는 트리를 말한다.
균형 이진 트리는 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리를 말한다.
편향이진트리는 노드들이 한 쪽으로 편향되어 생성된 이진트리를 말한다. 이 때 하나의 노드를 탐색하기 위해 모든 노드를 탐색해야 하므로 탐색속도가 저하될 수 있는 단점이 있다.
이진트리의 특성
- 이진 트리의 레벨 l에서 노드의 최대 수는 2^l 이다.
- 높이가 h이고 하나의 노드를 가진 트리의 높이가 1이라면 최대 노드 수는 2^ℎ−1이다.
출처
'Computer Science > 알고리즘, 자료구조' 카테고리의 다른 글
| 그래프와 탐색 (0) | 2023.04.01 |
|---|---|
| 시간 복잡도 (0) | 2023.03.31 |
| 자료구조 - 선형 자료구조 (0) | 2023.03.31 |
| Quick Sort vs Merge sort (1) | 2023.01.31 |
| 정렬 알고리즘 (0) | 2023.01.31 |
