[프로그래머스 알고리즘] 17강: 트리 (Trees)

트리(Trees)

노드(node)와 에지(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료구조

 

노드들 사이에는 parent-child 관계가 존재한다. 만약, 두 노드가 에지로 연결되어 있을때, 뿌리 노드에 더 가까운 노드가 parent node, 먼 노드가 child node이다. 같은 parent node를 가지는 child node는 서로 slibling 관계에 있다고 한다. 

 

트리 주요 용어

• 루트 노드(root node) : parent node가 없는 트리의 가장 윗 노드
• 리프 노드(leaf node) : child node가 없는 트리의 가장 아래 노드
• 내부 노드(internal node) : 루트 노드, 리프 노드가 아닌 나머지 노드
• 노드의 수준(level) : 이 강의에서는 root node는 level 0으로 정의한다. 그 밑의 child node는 level 1이다. edge의 개수를 node의 수준임을 알 수 있다.

• 트리의 높이 (height / depth) : 트리의 높이 = 최대 level + 1

• 서브 트리 (subtree) : 어느 한 노드를 root node로 가정하고 그 밑의 node들을 하나의 tree로 보는 것이 subtree라 할 수 있다.

• 노드의 차수 (degree) : 어떤 한 노드의 child node의 수, 혹은 subtree의 수. 각 노드당 parent node는 단 하나만을 가지고 child node는 여러 개를 가질 수 있다. leaf node들은 차수가 0이다. (child node가 없기 때문에)

 

이진트리(Binary tree)

모든 노드의 차수가 2 이하인 트리

이진 트리는 재귀적으로 정의할 수 있음

• 빈 트리(Empty tree)이거나
• 루트노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (단, 이때 왼쪽과 오른쪽 서브트리 또한 이진트리임)

 

포화이진트리(full binary tree)

모든 레벨에서 노드들이 모두 채워져있는 이진 트리 (높이가 k이고 노드의 개수가 2^k -1인 이진트리)

 

완전이진트리(complete binary treee)

높이 k인 완전 이진 트리

레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진트리

레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리