반응형
트리 : 계층형 트리구조를 시뮬레이션하는 추상자료형으로, 루트값과 부모-자식 관계의 서브 트리로 구성되며, 서로 연결된 노드의 집합이다.
<트리와 그래프 차이점>
가장 큰 차이점은 트리는 순환 구조를 갖지 않는다는 것!
그래프는 단방향, 양방향을 모두 가리킬 수 있는 반면 트리는 단방향(부모->자식)뿐. 또한 트리는 하나의 부모만을 가지고 루트 또한 하나다.
위의 세 경우는 모두 트리가 아닌 경우의 예시다.
첫번째 - C의 부모가 둘이라 트리가 될 수 없음
두번째 - (A-B)와 (D-C-E)가 연결되어 있지 않고 루트가 둘이라 트리가 될 수 없음
세번째 - 순환구조라서 트리가 될 수 없음
이진 트리(Binary Tree)
트리 중 특히 모든 노드의 차수가 2 이하일 때를 이진 트리(Binary Tree)라고 부른다.
유형 3가지가 존재
1. 정이진트리(Full Binary Tree)
- 모든 노드가 0 또는 2개의 자식 노드를 가짐.
2. 완전이진트리(Complete Binary Tree)
- 마지막 레벨을 제외한 모든 레벨이 완전히 채워져있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
3. 포화이진트리(Perfect Binary Tree)
- 모든 노드가 2개의 자식 노드를 가짐. 모든 리프 노드가 동일한 깊이 또는 레벨을 가짐.
댓글