Tree
노드들의 집합을 말한다. 각 노드들은 값(value)과 다른 노드들을 가리키는 레퍼런스들로 구성되어있다.
tree의 용어
-
간선(edge)
노드와 노드를 연결하는 선, 구현 관점에서는 레퍼런스를 의미한다. -
루트(root) 노드
트리의 최상단에 있는 노드를 말하며 트리의 시작점이다. -
자녀(child) 노드
모든 노드는 0개 이상의 자녀 노드를 가진다. -
부모(parent) 노드
자녀 노드를 가지는 노드를 말한다. -
형제(sibling) 노드
같은 부모를 가지는 노드들을 말한다. -
조상(ancestor) 노드
부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드들을 말한다. -
자손(descendant) 노드
자녀 노드를 따라 내려가며 만나는 모든 노드들을 말한다. -
내부(internal) 노드
자녀 노드를 가지는 노드를 말한다. -
외부(external) 노드
자녀 노드가 없는 노드를 말한다 = leaf node -
경로(path)
한 노드에서 다른 노드 사이의 노드들의 순서를 의미한다. -
경로 길이(length of path)
경로에 있는 노드들의 수를 말한다. -
노드의 높이(height)
노드에서 리프 노드까지의 가장 긴 경로의 간선 수를 의미한다.
트리의 높이는 루트 노드의 높이 이다. -
노드의 깊이(depth)
루트 노드에서 해당 노드까지의 경로의 간선 수를 의미한다.
트리에 있는 노드들의 깊이 중 가장 긴 깊이를 트리의 깊이라고 한다.
트리높이 = 트리깊이 -
노드의 차수(degree)
노드의 자녀 노드 수를 말한다. -
노드의 레벨(level)
노드와 루트 노드 사이의 경로에서 간선의 수를 말한다. -
width
임의의 레벨에서 노드의 수를 말한다. -
노드의 크기(size)
자신을 포함한 자손 노드의 수를 말한다.
트리의 모든 노드의 수를 트리의 크기라고 한다. -
서브 트리(subtree)
각 노드의 자녀 노드들을 재귀적으로 서브트리를 구성한다.
트리의 특징
루트 노드는 하나만 존재한다.
트리간에 사이클이 존재하지 않는다.
자녀 노드는 하나의 부모 노드만 존재한다.
데이터를 순차적으로 저장하지 않는 비선형(nonlinear)구조이다.
이진(binary) 트리
각 노드의 자녀 노드 수가 최대 두 개인 트리를 말한다.
left child(왼쪽 자녀 노드), right child(오른쪽 자녀 노드)로 나누어 진다.
이진 트리 종류
- full binary tree (정 이진 트리)
- 모든 노드는 자녀 노드가 없거나 두 개인 트리
- complete binary tree (완전 이진 트리)
- 마지막 레벨을 제외한 모든 레벨에서 노드가 채워져 있고
- 마지막 레벨은 왼쪽부터 빠짐없이 채워져 있는 트리
- perfect binary tree (포화 이진 트리)
- 모든 레벨에서 노드가 빠짐없이 채워져 있는 트리
- degenerate binary tree (변질 이진 트리)
- 모든 부모 노드는 하나의 자녀 노드만 가지는 트리
- left skewed binary tree, right skewed binary tree
- balanced binary tree (균형 이진 트리)
- 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1인 트리
