[윤성우의 열혈 자료구조]트리(Tree) - 트리의 이해

선형 자료구조의 초점

• 데이터의 저장

• 데이터의 삽입, 삭제, 조회 만으로 이야기할 수 있다.

 

비선형 자료구조의 초점

• 데이터의 표현(저장+@)
  • 데이터의 저장을 고민하지만 이는 데이터를 어떻게 해야 더 잘 표현할 것인가에 대한 고민이다.

• 데이터의 삽입, 삭제, 조회 만으로 비선형 자료구조를 이야기하기에는 부족하다. 추가적으로 자료구조를 직접 컨트롤 하는 함수가 등장한다.
  • 자료구조를 직접 컨트롤 하는 함수는 비선형 자료구조를 만드는 도구라고 생각할 수 있다. 이 도구를 통해 비선형 자료구조를 표현한다.

 

트리

• 계층적 관계((Hierarchical Relationship)를 표현하는 자료구조

• 트리는 단순한 데이터의 저장을 넘어서 데이터의 표현을 위한 도구이다.

 

트리 용어정리

• 노드(node)
  • 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소

• 간선(edge)
  • 노드와 노드를 연결하는 연결선

• 루트 노드(root node)
  • 트리 구조에서 최상위에 존재하는 A와 같은 노드

• 단말 노드(terminal node)
  • 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드

• 내부 노드(internal node)
  • 단말 노드를 제외한 모든 노드로 A, B와 같은 노드

 

트리 노드간 관계

• 노드 A는 노드 B, C, D의 부모 노드(parent node)이다.

• 노드 B, C, D는 노드 A의 자식 노드(child node)이다.

• 노드 B, C, D는 부모 노드가 같으므로, 서로가 서로에게 형제 노드(sibling node)이다.

 

트리의 레벨과 높이

• 트리의 높이와 레벨의 최대 값은 같다.

 

서브 트리의 이해

• 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리를 가리켜 서브 트리라 한다.

• 서브 트리 역시 또 다른 서브 트리로 이루어져 있다.
  • 트리는 구조가 재귀적이다.

 

이진 트리의 이해

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

• 트리 그리고 이진 트리는 그 구조가 재귀적이다. 따라서 트리와 관련된 연산은 재귀적으로 사고하고 재귀적으로 구현할 필요가 있다.

• D, E, F, G는 하나의 노드이지만 이진 트리이다.
  • 공집합(empty set) 노드도 이진 트리에서는 노드로 간주한다.
  • 이진 트리에 공집합 노드를 넣어 표현하는 이유는 두 개의 노드만을 자식 노드로 갖는 이진 트리의 규칙을 벗어나지 않도록 만들어 주기 위해서이다.
  • 이진 트리와 공집합 노드 

  

• 하나의 노드에 두 개의 노드가 달리는 형태의 트리는 모두 이진 트리이다.

 

포화 이진 트리, 완전 이진 트리

포화 이진 트리

• 포화 이진트리는 모든 레벨에 노드가 가득 찬 트리를 의미한다.완전 이진 트리는 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리를 의미한다.

완전 이진 트리

• 완전 이진 트리는 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리를 의미한다.

• 포화 이진 트리는 동시에 완전 이진 트리이지만 그 역은 성립하지 않는다.

---

[참고자료]

윤성우의 열혈 자료구조