트리의 정의
a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. wiki
트리는 계층형 트리구조를 시뮬레이션 하는 추상 자료형
ADT으로, 루트 와 부모-자식 관계의 서브트리로 구성되며 서로 연결된 노드의 집합.트리는 재귀적으로 정의된 자기 참조 자료구조이다.
개념
트리는 항상 Root Node 에서 부터 시작되며 각 트리는 루트가 최대 하나 있다
Root 는 자식노드를 가지고 있으며 간선 Edge 으로 연결되어있다.
각 노드 는 0개 이상의 자식노드를 가지고있다.
Node 는 최대 하나의 부모 노드를 가진다. 조상노드는 많을수 있다
같은 부모를 가지는 노드를 형제 Sibling 노드라고 한다.
각 노드는 자신이 루트 노드가 되는 서브트리가 될수있다.
차수 Degree 현재 노드가 가지는 자식 노드의 개수.
크기 Size 자신을 포함한 모든 자식 노드의 개수.
높이 Height 현재위치에서 부터 Leaf 까지의 거리.
깊이 Depth 루트에서부터 현재 노드까지의 거리.
리프 Leaf 자식노드가 없는 노드. External Node
내부 노드 Internal Node 적어도 하나 이상의 자식노드를 가지는 노드.
노드의 Level Root 부터 특정 노드까지 중복되지 않는 길을 이루는 간선의 개수.
트리는 항상 단방향 Uni-Directional 이므로 간선의 화살표는 생략가는하고 일반적으로 방향은 위에서 아래로 향한다.
Node 데이터와 다른노드에 대한 정보를 가지고있는 기본적인 자료구조
그래프와 트리의 차이
- 트리 는 특수한 형태의 그래프의 일종이며 크게 그래프의 범주에 포함된다.
DAGDirected Acylic Graphs 방향성이 있는 비순환 그래프의 한종류이다
| Graph | Tree | |
|---|---|---|
| Cycle | 순환,비순환 self-loop 모두 가능 | 순환구조가 없다. |
| Root | 루트노드의 개념은 없음 | 하나의 루트노드만 존재 |
| 부모-자식 | 관계의 개념은 없음 | 부모 자식 관계이므로 흐름은 위아래로만 가능하다. |
| 방향성 | 무방향 Undirected 단방향 Uni-directional 양방향 Bi-Directional 모두가능 | 부모 노드에서 자식노드를가르키는 단방향뿐이다. 노드간의 경로는 하나이다. |
| 간선의 수 | 그래프에 따라 다르다 | 항상 n-1개의 간선을 가진다. |E| = |V| - 1 |
| 모델 | 네트워크 모델 | 계층형 모델 |
| 순회 | DFS,BFS | Pre-Order, Post-Order, In-Order 중 하나로 이루어지고 모두 DFS,BFS 에 포함되어있다. |
이진 트리 Binary Tree
정의
각 노드가 m개 이하의 자식을 가지고 있으면
m-ary tree(다항트리, 다진트리) 라고 한다.
여기서 모든 노드의 차수가 2 이하일때 ( ) 특별이 이진트리라고 구문해 부른다.
정 이진 트리 Full Binary Tree 모든 오드가 0개 또는 2개의 자식노드를 가진 트리
완전 이진 트리 Complete Binary Tree 마지막 레벨을 제외하고 모든레벨이 완전히 채워져 있으며 마지막 레벨의 모든노드는 가장 왼쪽부터 채워져있는 트리
포화 이진 트리 Perfect Binary Tree 모든노드가 2개의 자식 노드를 갖고 있으며, 모든 리프노드가 동일한 깊이 또는 레벨을 갖는 트리.
