앞에서 봤던 자료구조들은 전부 선형적인 자료구조였다. 지금 알아볼 트리는 비선형적인 자료구조이기때문에 많이 다르게 느껴질 수 있다. 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. 나무처럼 가지를 늘려가며 뻗어나가는 것이다. 일상생활에서도 자주 접할 수 있다. 아래의 그림으로 트리가 어떤 형태인지 알아보자.
트리의 기본적인 용어
노드 : 트리의 구성요소에 해당하는 A, B, C, D, E, F 요소들을 노드라고 한다.
간선 : 노드와 노드를 연결하는 선을 간선이라 한다.
루트 노드 : 트리 구조에서 최상위에 존재하는 A노드를 루트 노드라고 한다.
단말 노드 : 잎 노드라고도 불리며 C, D, E, F노드를 단말 노드라고 한다.
내부 노드 : 단말 노드를 제외한 노드를 내부 노드라 하며 A, B 노드가 내부 노드가 된다.
부모 노드 : 노드 A는 B, C, D노드의 부모 노드이다.
형제 노드 : 노드 B, C, D는 부모가 같으므로 서로 형제 노드이다.
자식 노드 : 노드 B, C, D는 A의 자식 노드이다.
서브 트리
아래의 그림을 보면 큰 트리는 작은 트리로 구성이 된다. 이렇듯 큰 트리에 속하는 작은 트리를 가리켜 '서브 트리'라고 한다. 두 번째 그림을 보면 서브 트리안에 더 작은 서브 트리가 존재하는 것을 알 수 있다.
이진 트리
이진 트리의 정의
1) 루트 노드를 중심으로 두 개의 서브 트리로 나뉜다.
2) 나뉘어진 두 서브 트리 모두 이진 트리이어야 한다.
3) 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면 공집합 노드가 존재하는 것으로 간주한다. 공집합 노드도
이진 트리의 판단에 있어서 노드로 인정한다.
위의 그림을 보면 위의 정의대로 만들어진 이진 트리의 모습이다. 이제 아래의 그림을 봐보자. 아래의 그림도 이진 트리일까?? 정답은 이진 트리가 맞다! 그 이유는 3번째 정의를 보면 공집합 노드도 존재하는 것으로 간주하기 때문이다. 아래의 그림에서 확인해보자.
포화 이진 트리와 완전 이진 트리
포화 이진 트리를 알기 전에 레벨과 높이의 개념을 알고 있어야한다. 트리의 각 층별로 숫자를 매겨서 이를 트리의 '레벨'이라고 하며 트리의 최고 레벨을 가리켜 높이라 한다. 아래의 그림에서는 레벨 0에서 시작하며 최고의 레벨과 높이가 일치하기 때문에 최고 레벨을 높이라 한다.
다음 그림의 이진 트리는 모든 레벨이 꽉 차 있다. 따라서 노드를 추가하려면 레벨을 늘려야 한다. 이렇듯 모든 레벨이 꽉 찬 이진 트리를 "포화 이진 트리"라고 한다.
위의 그림에서 레벨을 증가시켜서 H와 I를 추가해보자. 위에서 아래로, 왼쪽에서 오른쪽으로 차곡 차곡 빈틈없이 채워진 상태의 이진 트리를 완전 이진 트리라고한다.
지금까지 트리의 개념을 알아보았다. 다음 포스팅에서는 트리를 구현해보고 좀 더 구체적으로 알아가보자.
'자료구조 및 알고리즘' 카테고리의 다른 글
| 우선순위 큐 (0) | 2020.08.25 |
|---|---|
| 이진 트리 (0) | 2020.07.23 |
| 큐 (리스트를 이용한 구현) (0) | 2020.07.22 |
| 큐 (배열을 이용한 구현) (0) | 2020.07.22 |
| 스택 (리스트를 이용한 구현) (0) | 2020.07.22 |