트리(Tree)에서 자주 까먹는 용어 및 파생 개념

[경로 길이(length of path)

문서에 따라서의 경로의 길이가 [노드들의 수]가 아니라, [간선들의 수]일 때가 있다. 

lefth of path 라는 용어가 나오면 어느 맥락에서 사용되는 말인지를 먼저 파악을 해야 한다. 

노드의 높이(height)

그러나, 관련 문서에 따라서는 [edge의 수]가 아니라, leaf까지의 가장 많은 [노드의 수]인 경우도 있다. 

문서마다 서로 다르니, 트리의 height이라는 말을 보면, 어느 의미로 쓰인 지를 파악하는 것이 중요하다. 

트리의 높이

노드의 레벨도 어떤 문서에서는 레벌 0이 아니라, [레벨 1]부터 카운팅하는 경우도 있다. 

노드의 크기(size)

트리의 크기

 

트리의 특징 

1. 노드는 단 하나의 부모 노드를 가진다. 

 

 

형태에 따른 이진 트리(binary tree)의 종류

 

full binary tree(정 이진 트리)

complete binary tree(완전 이진 트리)

perfect binary tree(포화 이진 트리)

편향 이진 트리(degenerate binary tree, pathological binary tree)

편향 이진 트리 = 왼쪽 편향 이진 트리 or 오른쪽 편향 이진 트리

왼쪽 편향 이진 트리(left skewed binary tree)

오른쪽 편향 이진 트리(right skewed binary tree)