트리(Tree)란?
값을 담고있는 노드(node), 노드들을 연결하는 간선(edge)이 계층 관계로 이루어진 자료구조이다.
관련 용어
- 루트 노드 (root node) : 부모가 없는 최상위 노드이다. 트리는 한 개의 루트노드만을 가진다.
- 부모 노드 (parent node) : 노드 D가 노드 F를 가리킬 때 D를 F의 부모노드라고 한다.
- 자식 노드 (child node) : 노드 F와 노드 G는 노드 D에서 파생되었으므로, 노드 D의 자식노드이다.
- 레벨 (level) : 루트 노드로부터의 깊이
- 노드의 차수 (degree) : 노드의 부속 트리의 개수
- 트리의 차주 (degree of tree) : 트리의 최대 차수
- 리프 노드 (leaf node) : 차수가 0인 노드, 즉 제일 아래에 달린 노드들이다. terminal node 라고도 한다.
- 내부 노드 (internal node) : 단말 노드가 아닌 노드
- 간선 (edge) : 노드를 연결하는 선, link, branch 라고도 부른다.
- 형제 (sibling) : 같은 부모를 가지는 노드
- 노드의 크기 (size) : 자신을 포함한 모든 자손 노드의 개수
- 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 트리의 높이 (height) : 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
트리의 종류
- 이진트리
자식 노드의 수가 2개 이하인 것을 이진 트리(binary tree)라고 한다.
부모 노드를 기준으로 값이 작은 것은 left child node에 값이 더 큰 것은 right child node에 저장된다.
- 스큐(skewed) 이진 트리
- 트리의 노드가 왼쪽이나 오른쪽으로 한쪽으로만 노드가 있는 트리이다.
- 정 이진 트리 (Full Binary Tree)
- 트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 경우이다. 즉 자식을 하나만 가진 노드가 없어야 한다.
- 완전 이진트리 (Complete Binary Tree)
- 마지막 레벨을 제외한 나머지 노드가 꽉 차 있어야 하며, 마지막 레벨의 노드도 왼쪽으로 몰려 있어야 한다.
- 포화 이진트리 (Perfect Binary Tree)
- 모든 레벨에서 노드가 꽉 차있는 트리를 의미한다. 즉 Perfect Binary Tree는 Complete이면서 Full인 이진트리이다.
- 노드의 개수가 정확히 (2^k)-1개여야 한다. (k: 트리의 높이)
트리구조의 필요성
계층적인 데이터 형태들은 트리에 저장하면 효율적이기 때문에 자연스럽게 표현할 수 있다.
1) 회사나 정부의 조직 구조
2) 나라, 지방, 시•군별, 계층적인 데이터의 저장
3) 인덱스 (인덱스는 계층적 자료 구조로 검색을 쉽게해준다.)
이진 트리의 검색
이진 트리의 검색은 빅 오 표기법에 의하면 O(log N) 이다. 단계를 수행할 때마다 값이 들어있을 남은 공간 중 반을 제거하기 때문이다. (다만, 최선의 시나리오인 포화 이진 트리에서만 그렇다...)
이진 트리의 삽입
삽입은 항상 검색에 한 단계 더 추가되는 성질이 있다. 즉, 삽입은 log N + 1단계가 걸리며, 빅 오 표기법은 상수를 무시하므로 O(log N) 이다.
이와 대조적으로 정렬된 배열에서는 검색뿐 아니라 매번 값을 삽입할 공간을 마련하기 위해 많은 데이터를 오른쪽으로 시프트해야 하는 번거로움이 있기에 삽입에 O(N)이 걸린다
그래서 이진 트리가 매우 효율적이다. 정렬된 배열은 검색에 O(log N), 삽입에 O(N)이 걸리는 반면, 이진 트리는 검색과 삽입 모두 O(log N) 이다.
데이터를 많이 변경할 애플리케이션이라면 특히 중요하다.
이진 트리의 삭제
1) 삭제할 노드에 자식이 없으면 그냥 삭제한다.
2) 삭제할 노드에 자식이 하나면 노드를 삭제하고 자식을 삭제된 노드가 있던 위치에 넣는다.
3) 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다. (후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드{ 삭제된 노드의 right node 로 가서 최대 leveld의 left node를 찾는다 }다.)
** 만약 후속자 노드에 오른쪽 자식이 있으면 후속자를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
이진 트리로 데이터를 변환시 주의할 점
이진 트리로 데이터를 변환하려고 한다면 무작위로 정렬된 데이터를 이용해야 균형잡힌 트리가 생성된다는 점을 유의해야 한다.
만약, 정렬된 데이터를 트리에 삽입하면 불균형이 심하고 덜 효율적일 수 있다.
예를 들어 데이터를 순서대로 즉 1, 2, 3, 4, 5로 삽입하면 스큐 이진트리가 생성될 것이다
하지만 같은 데이터를 3, 2, 4, 1, 5 순서로 삽입하면 균형 잡힌 트리가 완성될 것이다.
이러한 이유로 정렬된 배열을 이진 트리로 변환하고 싶을 때는 먼저 데이터 순서를 무작위로 만드는 게 좋다.
데이터를 무작위로 삽입한 일반적인 시나리오라면 균형이 잘 잡힌 트리일 것이며, 검색에는 약 O(log N)이 걸릴 것이다.
============================================================================
References
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
http://dblab.duksung.ac.kr/ds/pdf/Chap08.pdf
https://ddmix.blogspot.com/2016/03/binary-tree-errata.html
'Data structure' 카테고리의 다른 글
| 스택(Stack) [자료구조] (0) | 2021.10.18 |
|---|---|
| 큐(Queue) [자료구조] (0) | 2021.10.18 |
| 자료구조란? (0) | 2021.10.18 |
| 배열 [자료구조] (0) | 2021.10.18 |
