위키원
"트리"의 두 판 사이의 차이
(→구조) |
|||
| 2번째 줄: | 2번째 줄: | ||
== 구조 == | == 구조 == | ||
[[파일:트리.png|600픽셀]]<ref name='tree'>adam2,〈[https://velog.io/@adam2/TREE 자료구조 Tree]〉, 2020년 4월 5일</ref> <br> | [[파일:트리.png|600픽셀]]<ref name='tree'>adam2,〈[https://velog.io/@adam2/TREE 자료구조 Tree]〉, 2020년 4월 5일</ref> <br> | ||
| − | * node: 트리를 구성하고 있는 각 요소 | + | * '''node''': 트리를 구성하고 있는 각 요소 |
| − | * Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선 | + | * '''Edge(간선)''': 트리를 구성하기 위해 노드와 노드를 연결하는 선 |
| − | * Root Node: 최상위 계층에 존재하는 노드 | + | * '''Root Node''': 최상위 계층에 존재하는 노드 |
| − | * level: 트리의 특정 깊이를 가지는 노드의 집합 | + | * '''level''': 트리의 특정 깊이를 가지는 노드의 집합 |
| − | * degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수 | + | * '''degree(차수)''': 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수 |
| − | * Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드 | + | * '''Terminal Node''' ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드 |
| − | * Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.<ref name='tree'></ref> | + | * '''Internal Node''' (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.<ref name='tree'></ref> |
| + | |||
== 이진 트리(Binary Tree) == | == 이진 트리(Binary Tree) == | ||
* '''이진 트리(Binary Tree)''' : 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다. | * '''이진 트리(Binary Tree)''' : 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다. | ||
2020년 8월 12일 (수) 09:09 판
트리(tree)는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다. 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다.
목차
구조
- node: 트리를 구성하고 있는 각 요소
- Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선
- Root Node: 최상위 계층에 존재하는 노드
- level: 트리의 특정 깊이를 가지는 노드의 집합
- degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
- Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.[1]
이진 트리(Binary Tree)
- 이진 트리(Binary Tree) : 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다.
- 이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0)
- 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1)
- 이진트리는 완전 이진 트리(Completable Binary Tree)와 포화 이진 트리(Perfect Binary Tree), 전 이진 트리(Full Binary Tree)라고 하는 특별한 트리 구조를 정의할 수 있다.[1]
완전 이진 트리(Completable Binary Tree)
- 트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1 이하이고 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있으며, 왼쪽에서 오른쪽으로 채워지는 이진트리이다.
전 이진 트리(Full Binary Tree)
- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.
포화 이진 트리(Perfect Binary Tree)
- 모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리이다.
- 전 이진 트리이면서 완전 이진 트리인 경우이다.[1]
같이 보기
