안녕하세요 이번에는 비선형 자료구조인 트리에 대해서 설명해볼까 합니다. 트리란 무엇일까요?
트리는 Tree 이겁니다. 즉 나무를 뜻합니다. 이만 포스트를 마치겠습니다. 감사합니다.
1. 트리란 무엇일까?
아 죄송합니다. 장난입니다. 트리란 말그대로 나무를 뜻합니다.
이쁘죠? 이런 곳에서 여자친구와 데이트하면 좋겠네요. 전 못할꺼 같구요. 하 인생..
어쨋든 트리란 땅속에 뿌리를 내리고 나무 줄기를 타고 올라가 나무 가지가 뻗어나가며 그 곳엔 나뭇잎이 달려 있습니다.
자료구조에서 말하는 트리란 이거와 동일합니다. 나무줄기에서 여러 나무가지로 갈라져 나가면서 그 안에 또 여러 가지가
뻗어집니다. 마치 계층적으로 쭉쭉 뻗어 나가는 것처럼 말이죠.
트리에서는 계층적이라는 개념이 굉장히 중요합니다. 계층적이라는 말은 누구나 다 아실거라고 생각듭니다.
위 그림을 보시면 식사가 규칙적이라는 루트 노드에서 시작되어 좌우 가지를 늘려가며 뻗어나갑니다. 루트 노드란 이따가 설명하겠지만 말 그대로 뿌리, 즉 최초 시작 점? 이라고 생각하시면 됩니다.
식사가 규칙적이라면 오른쪽, 규칙적이지 않다면 왼쪽으로 뻗어 나갑니다. 또 그 밑으로 두가지 갈래가 있습니다. 여기서 중요 한 것은 네모박스의 내용이 아니라 네모박스가 계층적으로 뻗어 나간다는 것입니다.
위로 '뻗어가냐' 밑으로 '뻗어가냐'는 중요하지 않습니다. 중요한 것은 가지를 늘려가며 뻗어간다는 사실입니다.
2. 트리 관련 용어 소개
트리 관련 자료구조를 공부하다 보면 자주 등장하는 용어들이 있습니다. 이제 그 용어와 관련해서 간단하게 설명 드리겠습니다.
해당 용어들은 그림1을 기준으로 삼고 설명하겠습니다.
노드 : node --> 여기서 말하는 노드란 트리의 구성요소들을 말합니다. 그림1 에서 네모박스에 해당하는 것이죠.
간선 : edge --> 노드와 노드를 연결하는 선은 말합니다. 그림 1 저 위에 선들 보이시죠?
루트 노드 : root 란 뿌리를 뜻합니다. 위 그림에서 보이는 최상위 노드, 즉 ‘식사가 규칙적‘ 이라는 노드를 뜻합니다.
단말 노드 : 아래로 연결되어 있는 노드가 없는 노드를 뜻합니다. 1년이내, 1달 이내, 2년 이내, 3년 이내 노드를 뜻합니다.
내부 노드 : 단말 노드를 제외한 모든 노드를 뜻합니다. ‘식사가 규칙적’, ‘주 2회 이상 음주’, ‘주 2회 이상 운동’의 노드들이 포함됩니다.
루트 노드도 내부 노드라고 할 수 있습니다.
부모 노드 : 자식의 부모가 되는 노드로, ‘식사가 규칙적‘은 ’주2회 이상 음주’ ‘주2회 이상 운동’들의 부모노드가 됩니다.
자식 노드 : 위에서 설명한 대로 ’주2회 이상 음주’ ‘주2회 이상 운동’는 ‘식사가 규칙적’의 자식 노드입니다.
형제 노드 : 부모 노드가 같은 노드들을 모두 형제 노드가 됩니다. 서로서로가가 형제 노드가 됩니다.
레벨 : 트리에서 각 층별로 숫자를 매겨서 이를 트리의 레벨이라고 표현합니다. 0레벨,1레벨,2레벨 까지 그림은 표현됩니다.
높이 : 트리의 최고 레벨을 가리켜 높이라고 합니다. 위 그림은 레벨이 0~2 이므로 높이가 2가 됩니다.
3. 이진 트리와 서브 트리
위 그림을 보면 하나의 큰 트리는 작은 트리로 구성이 됩니다. 이렇듯 큰 트리에 속하는 작은 트리를 가리켜 서브 트리라고 합니다.
그림 2에서 루트노드가 A인 하나의 트리안에 루트노드가 B, C인 두개의 서브 트리가 있습니다. 쉽죠?
이러한 바탕으로 이진트리를 설명하겠습니다.
이진 트리란 다음과 같은 트리를 뜻합니다.
그리고 두 조건을 만족 해야 합니다.
1. 루트 노드를 중심으로 두 개의 서브 트리로 나누어진다.
2. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.
그럼 다음과 같은 트리는 이진 트리가 아닐까?
이것도 이진 트리입니다 왜냐?
지금 저기 B와 C의 오른쪽 자식 노드가 없지만
이진 트리에서는 노드가 위치할 수 있는 곳에 노드가 존재하지 않으면
공집합 노드가 존재하는 것으로 간주합니다. 공집합 노드란 다음과 같이 표현할 수 있습니다.
4. 포화 이진 트리와 완전 이진 트리
포화 이진트리란 모든 레벨이 꽉 차있는 트리를 뜻합니다.
그림과 같이 모든 노드들이 대칭으로 꽉 차 있는 트리를 말합니다.
따라서 노드를 더 추가하려면 레벨을 늘려야 합니다.
완전 이진 트리는 포화 이진 트리처럼 모든 레벨이 꽉 찬 것은 아니지만 차곡 차곡 빈 틈 없이 노드가 채워진 이진 트리를 말합니다.
다음 그림과 같이 모든 레벨이 꽉차 있지는 않지만 D의 자식 노드인 H 와 I가 둘 다 존재합니다.
둘 중 하나만 존재하게 되면 이는 완전 이진 트리가 아니게 됩니다.
'컴퓨터 관련 과목 > 자료구조&알고리즘' 카테고리의 다른 글
| 정렬 알고리즘 : 병합 정렬 (0) | 2018.08.10 |
|---|---|
| 정렬 알고리즘 : 힙 정렬 (1) | 2018.08.08 |
| 정렬 알고리즘 : 삽입정렬 (0) | 2018.08.05 |
| 정렬 알고리즘 : 선택정렬 (0) | 2018.08.05 |
| 정렬 알고리즘 : 버블 정렬 (0) | 2018.08.04 |
