트리와 관련 용어의 개념!

트리

트리는 비선형 자료구조이며, 고급 자료구조로 구분이 된다.

트리는 계층적 관계를 표현하는 자료구조이다.

위 문장에서 계층적 관계도 중요하지만 '표현'한다는 단어도 중요하다.
우리가 선형자료구조에서는 자료구조를 무엇인가를 저장하고 꺼내는 것이 전부인 것으로 이해하는 경우가 있었다.

하지만 자료구조는 근본적으로 무엇인가를 '표현'하는 도구이다.

트리 자료구조는 왜 이름이 트리일까?
나는 모르는 용어들을 볼때마다 왜 이런 이름이 지어졌는지 궁금할 때가 있다.
보통 그럴 때 찾아보게 되면 해당 단어를 더 잘 이해할 수 있게 된다.
그럼 왜 트리는 트리일까? 트리는 나무라는 뜻이다.
트리 자료구조는 나무처럼 보이지 않는데 왜 트리지?
나무와 트리 자료구조에 공통점이 있다.
"가지를 늘려가며 뻗어나간다"는 점이다.
중요한 것은 가지를 늘려가며 뻗어간다는 사실이다. 그래서 트리 자료구조인 것이다.

트리의 용어 소개

• 노드 : 트리의 구성요소 A,B,C,D...와 같은 요소
• 간선 : 노드와 노드를 연결하는 연결선
• 루트 노드 : 트리 구조에서 최상위에 존재하는 노드, A같은 노드
• 단말 노드(잎사귀 노드) : 아래로 또 다른 노드가 연결되어 있지 않은 노드
  I,J,K,F,G,H 같은 코드
• 내부 노드 : 단말 노드를 제외한 모든 노드
• 트리의 레벨 : 루트노드에서 0레벨로 시작해서 아래로 갈 수록 레벨이 높아진다.
• 트리의 높이 : 트리의 최고 레벨이 트리의 높이이다.
• 서브 트리 : 큰 트리에 속하는 작은 트리

이진 트리

이진 트리의 조건
1. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.
2. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.

두 번째 조건을 보면 조금 위화감이 들 수도 있다.
이진 트리의 조건 자체가 재귀적이기 때문에 이렇게 정의할 수 밖에 없다.

이건 이진 트리일까?

이진 트리가 맞다.
이진 트리라는 것은 자식 노드가 두 개씩 달린 트리가 맞다.
그럼 이렇게 반문할 것이다.
"위 그림은 자식이 하나뿐인데요 D, F 봐바요;;"
맞다. 하지만 이진 트리와 관련해서 다음 내용이 추가로 정의되어 있기 때문에 위의 트리는 이진 트리이다.

노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set)노드가 존재하는 것으로 간주한다! 물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다!

위의 조건을 이해하고 위 트리를 보면 이렇게 볼 수 있다.

"헉 그렇구나"
그렇다. 이런 공집합 노드가 빈 곳에 쏙쏙 들어가기 때문에 이진 트리라고 볼 수 있다는 것이다.

생각보다 이진 트리의 폭이 넓음을 알 수 있다. 따라서 이진 트리도 그 특성에 따라서 세분화 된다.

포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)

• 포화 이진 트리
  모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라 한다.(공집합 노드 제외)

• 완전 이진 트리
  포화 이진 트리 처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리를 뜻한다.
  여기서 차곡차곡은 다음을 뜻한다.
  "노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워졌다.

트리의 개념과 용어 정리 및 이진 트리와 세분화된 이진트리에 대해 알아보았다.
까먹을 때마다 복습하도록 하자.