[JavaScript] Tree(트리) - 이론학습

트리의 정의

  계층적 관계를 표현하는 자료구조를 트리라고 한다. 회사내의 조직도, 의사결정을 하는데 필요한 알고리즘 등을 트리 형태로 나타내고 있다.

 

 

조직도

 

 

트리의 용어 정리

트리 구조

- 노드(node) : 트리를 구성하는 각 요소 A, B, C, D, E, F

 

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

 

- 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드 A

 

- 단말 노드(terminal node) or leaf : 트리 구조에서 아래로 또 다른 노드(자식 노드)가 존재하지 않는 노드 C, D, E, F

 

- 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 A, B

 

노드간의 관계

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

 

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

 

- 노드 B, C, D는 부모 노드가 A로 형제 노트(sibing node)이다.

 

 

서브 트리

서브 트리

  서브 트리란 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리를 가리킨다. 서브 트리 역시 또 다른 서브 트리를 가질 수 있다.

 

서브 트리로 알 수 있듯이 트리 구조는 재귀적인 특징이 있다.

 

 

이진 트리(Binary Tree)

  이진 트리의 조건으로는 다음 두가지가 있다.

 

- 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

- 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다.

이진 트리

  트리는 그 구조가 재귀적이기 때문에 트리와 관련된 연산은 재귀적으로 사고해야 하고 그 구현 또한 재귀적으로 해야할 필요가 있다.

 

 

이진 트리와 공집합 노드

  공집합(empty set)도 이진 트리에서는 노드로 간주한다.

 

공집합 노드의 이해

  위의 그림처럼 한 쪽이 비어있는 트리라고 할지라도 공집합이라는 개념을 넣어 이진 트리로 간주해야 한다.

 

 

트리의 높이와 레벨

트리의 높이와 레벨

  트리에서 높이와 최대 레벨의 값은 같다. 레벨의 기준은 루트 노드를 0으로 잡는다.

 

 

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

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

  왼쪽 그림은 포화 이진 트리를 나타낸 것이다. 포화 이진 트리는 최고 레벨 제외 모든 레벨에서 각 노드에 두 개의 자식 노드가 모두 있는 특징을 가지고 있다.

 

  오른쪽 그림은 완전 이진 트리로 모든 레벨의 각 노드에 두 개의 노드가 있을 필요는 없지만 단말 노드(leaf)의 부모 노드가 두 개의 자식 노드를 가지고 있는 특징이 있다.

 

따라서 모든 포화 이진 트리는 완전 이진 트리지만 완전 이진 트리가 꼭 포화 이진 트리라는 것은 아니다.