트리(Tree) - 기초 및 용어

: 정점 (node)과 간선(edge) 을 이용하여 데이터의 배치 형태를 추상화한 자료구조

 

노드는 루트노드, 내부노드, 리프노드 로 나뉜다

 

루트노드 : 가장 최상위에 위치한 노드

 

내부노드(Internal) : 루트도 리프도 아닌 노드 (중간 노드 들)

 

리프노드 : 더 이상 하위 노드가 없는 최하위 노드

 

노드들 사이에는 부모노드와 자식 노드가 존재하고 더 선택한 노드를 기준으로

더 상위에 가까운 노드를 부모(Parent)노드

더 하위에 가까운 노드를 자식(Child) 노드라고한다

(루트 노드는 자식노드만 리프노드는 부모 노드만 존재한다)

 

형제노드 : 같은 부모 아래 존재하는 노드를 형제(sibling) 노드라고 부른다

 

조상(ancestor) 노드 : 부모의 부모(의 부모의 ...)

후손(descendant) 노드 : 자식의 자식(의 자식의 ...)

 

노드의 수준(Level)

루트노트는 level 0으로 표현하고 그 하위로 갈수록 level은 1씩 증가한다.

 

트리의 높이 (Height)

트리의 높이 (height = 최대 수준 (level) + 1

* 깊이(depth) 라고도 함.

 

부븐 트리(서브 트리 - Subtree)

트리에서의 어느 한 노드를 루트노드로 잡아서 그 노드의 자식들을 다른 트리로 잡는것

 

노드의 차수 (Degree)

 : 각 노드마다 존재하며 자식노드 (서브트리) 의 수를 말한다. Degree가 0인 노드는 리프노드임을 알 수 있다.

 

이진 트리(Binary Tree)

 : 모든 노드의 차수가 2이하인 트리 = 각 노드의 자식 노드의 수가 2 이하인 트리 구조

 

재귀적으로 정의할 수 있음:

빈 트리이거나 **

루트노드 + 왼쪽 서브트리 + 오른쪽 서브트리

(단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리여야한다.)

 

포화 이진 트리 (Full Binary  Tree)

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

 

완전 이진 트리 (Complete Binary Tree)

: 높이 k인 완전 이진 트리

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

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