트리 - 개념

1) 트리란?

- 트리란 나무를 뒤집어 놓은 모양의 자료구조입니다.

  트리는 유한한 노드들의 집합으로, 루트 라고 불리는 특별한 노드가 존재하고,

  나머지 노드들은 n개의 서브트리로 존재합니다. 

  트리에 대해 잘 알기 위해서는 트리와 관련된 용어들을 알아야 합니다. 

 

- 트리의 하나의 구성 요소를 노드라고 하며, 각 노드는 데이터를 갖고 있습니다. 

 

- 트리에서는 가장 최상위 노드를 루트 노드라고 하며, 루트 노드는 반드시 하나여야 합니다. 

  그리고 루트 노드를 기준으로 아래에 있는 트리를 루트의 서브 트리라고 합니다. 

  노드의 차수는 노드의 서브 트리의 개수를 의미하며, 

  아래 그림의 A 노드의 차수는 2입니다. 

  반면, C노드는 3개의 서브트리를 가지므로, 차수가 3입니다. 

  그리고 트리의 차수는 트리의 최대 차수를 의미하므로, 마찬가지로 3입니다. 

 

 

- 루트가 다른 트리들의 집합을 포리스트(Forest)라고 합니다. 

 

2) 노드 간의 관계

- 노드 간의 관계를 지칭할 때는, 부모, 형제, 자식, 조상, 후손 등으로 지칭합니다. 

  C노드를 기준으로, A노드는 C노드의 부모 노드이며, B노드는 C노드의 형제 노드입니다.

  F,G,H 노드는 C노드의 자식 노드이며,

  자식 노드를 포함하여 C노드의 아래에 있는 노드들을 후손 노드라고 합니다. 

  마지막으로 C노드의 위에 있는 노드를 조상 노드라고 합니다.

- 차수가 0인 노드, 즉 자식이 없는 노드를 단말 노드 혹은 리프 노드라고 부르며,

  차수가 0이 아닌 노드, 즉 자식이 있는 노드를 내부 노드 혹은 브랜치 노드라고 합니다. 

 

- 그리고 트리의 관계를 뜻하는 레벨이 있습니다. 

  루트 노드는 레벨0으로 시작하고, 자식은 레벨1, 손자는 레벨2, 이렇게 후손들까지 한 단계씩 늘어납니다. 

  루트의 레벨은 0으로 표현하는 경우도 있고, 1로 표현하는 경우도 있습니다. 

 

참고

코드라떼 자료구조