트리1

[트리의 개념]

• 리스트, 스택, 큐 등이 선형 자료구조라고 한다면 트리는 비선형(계층적) 자료구조이다.

• 계층적 자료구조는 ‘회사 조직’, ‘의사 결정 트리’ 등의 형태를 표현한다.

• 리스트, 스택, 큐 등이 데이터 삽입, 삭제, 조회 등에 초점을 맞춘 자료구조라고 한다면, 트리는 어떠한 형태를 표현하는데 초점을 맞춘 자료구조다.

• 그렇다고 트리에서 삽입, 삭제, 조회가 중요하지 않다는 것이 아니다. 단순히 무언가를 표현하는 것에 최적화된 자료구조라는 뜻이다.

 

[트리의 용어]

• 노드: 트리의 구성 요소에 해당하는 A, B, C, D, E, F, G, H, I, J, K를 노드(node)라 한다.

• 루트: 계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 된다.

• 서브 트리: 전체 노트 집합 {A, B, C, D, E, F, G, H, I, J, K}중에서 루트 노드는 A이고, 나머지 노드들은 {B, E, F, G, K}, {C, H}, {D, I, J}로 3개의 집합으로 나누어지는데 이들은 A의 서브 트리라고 한다. 다시 서브 트리인 {B, E, F, G, K}의 루트는 B가 되고 나머지 노드들은 다시 3개의 서브트리, 즉 {E}, {F}, {G}, {K}로 나누어진다. 서브 트리는 재귀적인 개념임을 유념하자!

• 간선: 트리에서 루트와 서브 트리는 선으로 연결이 되는데, 이 연결선을 간선이라고 한다.

• 부모 노드: B의 부모노드는 A이다.

• 자식 노드: A의 자식노드는 B, C, D이다.

• 형제 노드: B와 C와 D는 형제 노드이다.

• 조상 노드: 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드. E의 조상노드는 B와 A이다.

• 자손 노드: 임의의 노드 하위에 연결된 모든 노드. B의 자손 노드는 E, F, G, K이다.

• 단말 노드(leaf node): 자식 노드가 없는 노드 K, F, G, H, I, J이다.

 

• 차수: 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다. A의 차수는 3이고, D의 차수는 2이다. 트리의 차수는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수이다. 위 그림에서는 3이다.

• 레벨: 트리의 각 층에 번호를 매기는 것으로서 정의에 의하여 루트 레벨은 1이 되고 한 층씩 내려갈수록 1씩 증가한다. A의 레벨은 1이고, B의 레벨은 2이다.

• 높이: 트리의 높이는 트리가 가지고 있는 최대 레벨을 말한다. 위 트리의 높이는 4이다.