트리용어

 

• root 노드(뿌리 노드): 트리의 시작 노드, 뿌리가 되는 노드를 말합니다. 보통 트리를 표현할 때 위 그림처럼 가장 위에 root 노드를 놓는 방식으로 나타냅니다.

 

• 부모 노드: 특정 노드의 직속 상위 노드입니다. 노드 G, J, K가 있는 노란색 박스를 살펴보면 G가 J와 K의 부모 노드입니다.

 

• 자식 노드: 특정 노드의 직속 하위 노드입니다. 부모 노드와 반대되는 개념인데요. 노드 G, J, K가 있는 노란색 박스를 살펴보면 J와 K가 G의 자식 노드입니다.

 

• 형제 노드: 같은 부모를 갖는 노드입니다. D와 E는 둘다 그 부모가 B죠? 이럴 때 D와 E는 서로 형제 노드입니다.

 

• leaf 노드 (잎/말단 노드): 자식 노드를 갖고 있지 않은, 가장 말단에 있는 노드입니다. 트리의 끝에 있다고 해서 root(뿌리) 노드와 반대되는 표현으로 leaf(잎) 노드라고 부릅니다. 위 그림에서 노란색 박스로 둘러싼 F가 leaf 노드입니다. F뿐만 아니라 D, H, I, J, K 모두 leaf 노드입니다.

 

• 깊이: 특정 노드가 root 노드에서 떨어져 있는 거리입니다. 깊이는 해당 노드로 가기 위해서 root 노드에서 몇 번 아래로 내려와야 하는지를 나타냅니다. 예를 들어 위 그림에서 root 노드의 자식 노드인 B와 C는 깊이가 1입니다. D, E, F, G는 깊이가 2이고, H, I, J, K는 깊이가 3입니다. 결국 깊이라는 건 특정 노드가 root 노드로부터 얼마나 멀리 떨어져 있는지를 나타냅니다.

 

• 레벨: 깊이 + 1. 깊이랑 거의 똑같은 개념입니다. 그냥 깊이에 1을 더한 값이죠. 레벨 1에 있는 노드들, 레벨 2에 있는 노드들… 이런식으로 특정 깊이인 노드들을 묶어서 표현할 때 사용하는 용어입니다.

 

• 높이: 트리에서 가장 깊이 있는 노드의 깊이입니다. 위 그림의 트리에서는 H, I, J, K가 가장 깊이 있는 노드들이고 그 깊이는 모두 3입니다. 그래서 트리의 높이는 3입니다.

 

부분 트리 (sub-tree): 현재 트리의 일부분을 이루고 있는 더 작은 트리를 말합니다. 위 그림의 트리는 root 노드가 A인 트리입니다. 그런데 이 트리를 좀더 작은 단위로 쪼개보면 더 작은 부분 트리들을 발견할 수 있습니다. 예를 들어 위 그림의 노란색 큰 박스 안을 보세요. 노란색 큰 박스 안에는 ‘C가 root 노드인 트리’가 있는데요. 이런 걸 바로 부분 트리라고 합니다. 지금 C가 A의 오른쪽 자식이죠? 그래서 노란색 큰 박스 안에 있는 부분 트리를 A의 “오른쪽 부분 트리”라고 합니다. 특정 노드를 root 노드라고 생각하고 바라본다면 여러 가지 부분 트리들을 발견할 수 있습니다. 하나의 전체 트리에 여러 부분 트리들이 존재하는 겁니다.