자료구조 트리란?

트리는 고급 자료구조로 분류가 된다.
앞에서 공부한 선형 자료구조들과 달리 비선형 자료구조의 형식이기 때문에 다르다.

트리의 정의는 계층적 관계(Hierarchical Relationship를 표현하는 자료구조이다.

위에서 키워드는 계측정관계와 표현이다.
앞서 공부한 선형 자료구조는 데이터를 저장하고 꺼내는 것이 전부였지만, 기본적으로 자료구조는 근본적으로 무엇인가를 표현하는 도구이다. 표현을 위해서 데이터 저장, 삭제라는 기능이 제공되는 것이다.

트리의 표현

트리란 우리가 일상속에서 자주 보는 자료구조 중의 하나이다. 컴퓨터의 디렉터리 구조, 회사의 조직도 등 다양한 형태의 트리를 우리는 접한다.

또한 의사 결정 트리(decision tree)라고 하는 것도 있다.
의사 결정 트리는 다양한 데이터를 분석하는데에 있어서 유용한 도구이고, 다양한 학문에서도 사용된다.

트리의 용어

트리의 용어에 대해서 공부해보자

• 노드(node)

  • 트리의 구성요소에 해당하는 요소
  • A, B, C, D, E, F에 해당한다

• 간선(edge)

  • 노드와 노드를 연결하는 선을 의미

• 루트 노드(root node)

  • 트리의 구조에서 최상위에 존재하는 노드
  • 그림에서 A 노드에 해당

• 단말 노드(terminal node)

  • 아래에 다른 노드가 연결되어 있지 않은 노드
  • 그림에서 D, E, F에 해당
  • 다른 이름으로 잎 노드(leaf node)라고도 한다.

• 내부 노드(iternal node)

  • 단말 노드를 제외한 모든 노드
  • A, B, C에 해당

또한 부모(parent), 자식(child), 형제(sibling)의 관계로 표현하기도 한다.

• 부모 노드
  • A는 B와 C의 부모 노드
  • B는 D와 E의 부모 노드
  • C는 F의 부모 노드

• 자식 노드
  • B와 C는 A의 자식 노드
  • D와 E는 B의 자식 노드
  • F는 C의 자식 노드
• 형제 노드
  • B와 C는 형제 노드
  • D와 E는 형제 노드

부모와 자식의 관계는 서로 상대적으로 부모이면서 동시에 자식이 될 수 있다.

또 조상(Ancestor), 후손(Descendant)의 관계도 있다.
특정 노드 위에 위치한 노드를 조상 노드라고 하고, 아래에 위치한 노드를 후손 노드라고 한다.

이진 트리(Binary Tree)와 서브 트리(Sub Tree)

큰 트리는 작은 트리들의 집합이라고 볼 수도 있다.
그림과 같이 큰 트리에 속하는 작은 트리를 서브트리라고한다.

서브 트리안에는 더 작은 서브 트리가 존재한다.

그 다음은 이진 트리이다.

중점을 두고 공부해야할 트리 모형이다.

이진 트리는 두 조건을 만족해야 한다.

• 루트 노드를 중심으로 두 개의 서브트리로 나눠진다.
• 나눠진 두 서브 트리도 모두 이진 트리여야 한다.

쉽게 말하면 두 개로 갈라지는 트리를 의미한다.

위 사진도 이진트리로 볼 수 있다.
이진트리는 다음과 같은 내용이 정의되어 있기 때문이다.

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

위 정의대로 본다면 다음과 같이 볼 수 있다.

아래 그림과 같은 트리도 이진 트리가 될 수 있다.

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

앞서 레벨과 높이를 알고 넘어가야 한다.
트리의 층별로 숫자를 매긴 것을 레벨이라고 하고, 트리의 최고 레벨을 가리켜 높이라고 한다.

위 그림과 같은 트리에서 노드를 추가하기 위해서는 레벨을 늘리는 방법 밖에 없다.
따라서 모든 레벨이 꽉 찬 이진 트리를 포화 이진 트리라고 한다.

위 그림과 같이 트리에서 레벨이 꽉 찬것은 아니지만, 노드가 꽉 차있는 트리를 완전 이진 트리라고 한다.