- 트리
트리는 한 개 이상의 노드로 이루어진 유한 집합이다.
-트리의 용어
트리의 시작점을 루트라고 하며 나머지 노드들은 서브 트리라고 말한다.
어떤 노드의 서브 트리에 속하는 모든 노드들은 후손 노드이다.
자식 노드가 없는 노드를 단말 노드 자식 노드를 가진 노드를 비단말 노드라고 한다.
노드의 차수는 자식 노드의 개수를 의미한다.
트리의 높이는 트리가 가지고 있는 최대 레벨을 말한다.
트리들의 집합을 포레스트라고 한다.
- 이진트리
트리중에서 가장 많이 사용되는 트리이고 모든 노드가 최대 2개까지의 서브 트리만 가질 수 있다 → 모든 노드의 차수가 2 이하가 된다.
n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가지며 루트를 제외한 노드들은 정확하게 하나의 부모 노드를 가진다. 또한 부모와 자식 간에는 정확하게 하나의 간선만 존재한다. 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2h -1개의 노드를 가진다.
n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 | log2(n+1) | 이 된다.
- 이진트리의 분류
이진트리는 크게 3가지로 분류할 수 있다.
포화 이진트리, 완전 이진트리, 기타 이진트리
포화 이진트리는 용어 그대로 트리의 각 레벨에 노드가 꽉 차 있는 이진트리를 의미한다.
완전 이진트리는 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 순서대로 채워져 있는 이진트리이다. 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있어서는 안 된다. 따라서 포화 이진트리는 항상 완전 이진트리이지만 완전 이진트리라고 포화 이진트리는 아니다.
이진트리에서 노드에 번호를 부여할때는 레벨단위로 왼쪽에서 오른쪽으로 번호를 붙이면 된다.
'ETC. > 자료구조' 카테고리의 다른 글
| 자료구조 9(이진탐색트리) (0) | 2023.01.09 |
|---|---|
| 자료구조 8(이진트리) (0) | 2023.01.09 |
| 자료구조 6(연결리스트) (0) | 2023.01.09 |
| 자료구조 5(큐) (0) | 2023.01.09 |
| 자료구조 4(스택) (0) | 2023.01.09 |
