트리 (Tree)
태그 :
- 개념
- 트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음과 같은 조건을 만족함. (1) 트리에는 루트(root)라고 부르는 특별한 노드가 있음. (2) 다른 노드들은 원소가 중복되지 않는 n개의 부속트리(subtree)로 나누어짐.
I. 트리 (Tree)의 개요
가. 트리의 정의
- 트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음과 같은 조건을 만족함.
(1) 트리에는 루트(root)라고 부르는 특별한 노드가 있음.
(2) 다른 노드들은 원소가 중복되지 않는 n개의 부속트리(subtree)로 나누어짐.
나. 트리의 특징
- 계층적인 데이터 형태를 저장하기에 적합함. (조직구조, 지역구분 등)
- 인덱스 파일의 생성에 적합함.
Ⅱ. 트리의 관련된 용어 및 트리 순회 방식
가. 트리에 관련된 용어
용어 |
설명 |
|
한글 |
영어 |
|
노드의 차수 |
degree |
노드의 부속 트리의 개수 |
트리의 차수 |
degree of tree |
트리의 최대 차수 |
단말 노드 |
leaf, terminal |
차수가 0인 노드, 즉 맨 끝에 달린 노드 |
내부 노드 |
internal |
차수가 1이상인 노드 |
부모 |
parent |
부속 트리를 가진 노드 |
자식 |
child |
부모에 속하는 부속 노드 |
형제 |
sibling |
부모가 같은 자식 노드들 |
조상 |
ancestor |
노드의 부모 노드들의 총 집합 |
자손 |
descendant |
노드의 부속 트리에 있는 모든 노드들 |
레벨 |
level |
루트 노드들로부터 깊이 |
트리의 깊이 |
depth of tree |
트리에 속한 노드의 최대 레벨 |
나. 트리 순회 방식
방식 |
트리 순회 순서 |
방향 및 표식 |
---|---|---|
전위 (Preorder) |
||
중위 (Inorder) |
||
후위 (Postorder) |
Ⅲ. 이진 트리 (Binary Tree)의 개요
가. 이진 트리의 정의
- 노드의 차수(degree)가 2 이하로 구성된 트리
나. 이진 트리의 특성
- 깊이가 k인 이진 트리의 최대 노드의 수: 2k-1
- 이진 트리의 레벨 i에서 최대 노드의 수: 2(i-1)
- n0 = n2 + 1 (n0 : 이진 트리의 터미널노드, n2 :차수가 2인 노드 수)
Ⅳ. 이진 트리의 저장
가. 배열을 이용한 저장
- 트리의 레벨 순서대로 배열에 저장하는 방법 - T[] 배열에 루트노드는 T[0]에, 레벨2의 첫째노드는 T[1]에,,, 저장하는 방식
(1) 부모 노드의 위치: parent(i) = (i-1)/2 (단, i=0 인 경우는 parent(i) = 0) (2) 왼쪽 자식의 위치: left_child(i) = 2*i +1 (3) 오른쪽 자식의 위치: right_child(i) = 2*i +2 |
||
⇒ |
||
⇒ |
나. 연결 리스트를 이용한 저장
- 데이터, 왼쪽 자식에 대한 포인터, 오른쪽 자식에 대한 포인터로 구성하는 방법
struct tnode { int data; struct tnode * left_child; struct tnode * right_child; }; typedef struct tnode node; typedef node * tree_ptr; |
||
⇒ |
||
⇒ |
다. 이진 트리 저장 방식의 비교
배열을 이용한 저장 |
연결리스트를 이용한 저장 |
- 저장이 편함. - 노드의 위치를 쉽게 알 수 있음. |
- 트리의 크기와 깊이에 관계없이 노드 수 만큼의 데이터를 저장함. - 트리 전체를 탐색하는 알고리즘이 배열보다 복잡함. |
Ⅴ. AVL 트리의 개요
가. AVL 트리의 정의
- 좌우 서브트리의 높이 차이가 1이하인 이진 탐색 트리
나. AVL 트리의 특성
- O(log N)의 검색 성능 보장
- AVL 형태로 트리 유지
- Balanced Factor: +1,0,-1 경우만 허용, 그 외의 경우는 Rotation
Ⅵ. AVL 트리의 회전
가. AVL트리의 회전방식
나. LL 회전
다. LR 회전
라. RL 회전
마. RR 회전