[자료구조] 트리(tree)
1. 트리(tree)란?
계층적 형태의 자료구조를 뜻한다.
트리라고 부르는 이유는 나무를 거꾸로 엎어놓은 모양을 하고 있기 때문이다.
2. 용어 정리
(1) 노드(node) : 트리의 구성요소
(2) 루트(root) : 트리의 가장 윗 부분 노드
(3) 서브트리(subtree) : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리
(4) 간선(edge) : 투르와 서브트리를 연결하는 선
(5) 부모(parent) : 어떤 노드에서 가지로 연결된 위쪽 노드
(6) 자식(child) : 어떤 노드로부터 가지로 연결된 아래쪽 노드
(7) 형제(sibling) : 같은 부모를 가지는 노드
(8) 조상(ancestor) : 어떤 노드에서 가지로 연결된 위쪽 노드 모두
(9) 자손(descendant) : 어떤 노드에서 가지로 연결된 아래쪽 노드 모두
(10) 단말 노드(terminal node or leaf node) : 자식 노드가 없는 노드
(11) 비단말 노드(nonterminal node) : 단말 노드의 반대말
(12) 차수(degree) : 노드가 갖는 자식의 수
(13) 레벨(level) : 루트로부터 얼마나 떨어져 있는지에 대한 값.
가지가 아래로 한 층씩 내려갈때마다 레벨이 1씩 늘어난다.
(14) 높이(height) : 트리가 가지고 있는 최대 레벨
(15) 포리스트(forest) : 트리들의 집합
3. 이진 트리(binary tree)
(1) 이진 트리의 정의
- 이진 트리란 자식 노드가 2개인 트리를 말한다.
실제로 트리 중 이진 트리가 가장 많이 쓰인다.
- 이진트리의 서브 트리는 공집합일 수 있다.
따라서 노드는 최대 2개까지 자식 노드가 있을 수 있다.
그러므로 모든 노드의 차수가 2 이하 이다.
- 이진트리는 서브 트리간의 순서가 정해져있다.
즉 왼쪽 서브 트리, 오른쪽 서브 트리가 서로 구별된다.
이러한 순서는 이진 트리를 순환적으로 써야하기 때문에 중요하다.
(2) 이진 트리의 성질
- n개의 노드를 가진 이진트리는 n-1개의 간선을 가진다.
왜냐면 루트를 제외한 나머지 노드들이 하나의 부모 노드를 가지니까
(루트만 간선이 없으니까 루트를 뺀 나머지 노드 개수랑 같다)
- 높이가 h인 이진트리는
최소 h개의 노드를 가지며
최대 2^h-1개의 노드를 가진다.
- n개의 노드를 가진 이진트리는
높이가 최대 n이거나
최소 log2(n+1)이다.
(3) 이진 트리 분류
1) 포화 이진 트리(full binary tree)
각 레벨에 노드가 꽉 차 있는 트리.
높이 k인 포화 이진 트리는 2^k-1개의 노드를 가진다.
이러한 이진트리는 왼쪽에서 오른쪽으로 번호를 붙인다.
2) 완전 이진 트리(complete binary tree)
높이가 k일 때 레벨 1부터 k-1까지는 노드가 꽉 채워져 있는데
마지막 레벨 k에서 왼쪽부터 오른쪽까지 순서대로 채워져 있는 상태.
(포화 이진 트리에서 마지막 레벨이 모자라게 채워져 있으면 된다.)
4. 이진 트리 표현
(1) 배열 표현법
이진 트리는 노드들의 순서가 있기 때문에
각 노드들의 index를 매겨서 배열에 저장할 수도 있다.
- 노드 i의 부모 노드 인덱스 : i/2
- 노드 i의 왼쪽 자식 노드 인덱스 : 2i
- 노드 i의 오른쪽 자식 노드 인덱스 : 2i+1
(2) 링크 표현법
노드를 구조체로 표현한다.
구조체에는 노드의 데이터 값과
왼쪽 자식 노드를 가리키는 포인터와 오른쪽 자식 노드를 가리키는 포인터를 가진다.
5. 이진 트리의 순회(traversal)
1) 너비 우선 탐색(BFS)
2) 깊이 우선 탐색(DFS)
1) 전위 순회(preorder traversal)
노드 출력 → 왼쪽 노드 방문 → 오른쪽 노드 방문
A B D H E I J C F K L G 순으로 출력
2) 중위 순회(inorder traversal)
왼쪽 노드 방문 → 노드 출력 → 오른쪽 노드 방문
H D B I E J A K F L C G 순으로 출력
3) 후위 순위(postorder traversal)
왼쪽 노드 방문 → 오른쪽 노드 방문 → 노드 출력
H D I J E B K L F G C A 순으로 출력