차수

그래프 용어에서 차수(degree)를 배운 적이 있습니다. 트리에도 차수 개념이 있는데, 트리에서는 좀 더 특정 지어서 차수란 ‘어떤 노드의 자식 노드 개수’를 의미합니다. 트리의 차수(degree of a tree)는 트리에 있는 노드의 최대 차수를 의미합니다.

리프 노드(leaf node)는 차수가 0인 노드를 의미합니다. 즉, 자식이 없다는 것이지요. 그림 7-1에서 노드 4, 노드 5, 노드 6, 노드 7, 노드 8은 모두 리프 노드입니다. 내부 노드는 루트 노드와 리프 노드를 제외한 노드를 의미합니다. 레드 블랙 트리에서는 외부 노드(external node)라는 개념을 따로 두어 그에 대응되는 개념으로도 사용합니다. 이는 레드 블랙 트리를 배울 때 다시 한 번 언급하겠습니다.