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