자료구조 - 트리(Tree)

1. 트리(Tree)

• 자료 구조의 트리는 나무의 형태를 가진 단방향 그래프의 일종이다
• 하나의 데이터 아래에 여러 개의 데이터가 존재하는 비선형 구조이다
• 트리 구조는 계층적으로 표현된다
• 트리 구조는 아래로만 뻗어 나가기 때문에 사이클이 존재하지 않는다

 1) 트리 구성

• 데이터가 시작이 되는 꼭지점을 루트(Root) 라고 한다
• 데이터를 연결하는 선을 간선(Edge)라고 한다
• 각각의 개별 데이터를 노드(Node)라고 한다
• 상위-하위 관계 데이터 중에서 루트노드로부터 가까운 데이터를 부모 노드(Parent Node) 라고 한다
• 상위-하위 관계 데이터 중에서 루트노드로부터 먼 데이터를 자식 노드(Child Node)라고 한다
• 부모와 자식 노드가 한쌍으로 연결되어 관계를 형성한다
• 자식 노드가 없는 데이터를 리프 노드(Leaf Node)라고 하며, 트리구조의 끝 지점이다

 

Tree 구조

 

2. 트리 관계

 1) 깊이(Depth)

• 루트부터 하위 특정 노드까지의 깊이를 표현할 수 있다
• 루트값은 0부터 시작한다

 2) 레벨(Level)

• 동일한 깊이를 가지고 있는 데이터들을 레벨로 묶을 수 있다
• 같은 레벨의 데이터를 형제 노드(Sibling Node)라고 한다

 3) 높이(Height)

• 깊이와 반대로 리프노드부터 상위 특정 노드까지의 높이를 표현할 수 있다
• 리프노드 값은 0부터 시작한다
• 부모노드는 자식노드의 높이 값 + 1 의 값을 높이로 가진다

 4) 서브 트리(Sub Tree)

• 루트에서 뻗은 트리 구조 내에 트리구조를 가지는 작은 트리를 서브트리(Sub tree)라 한다

 

 

※ 트리구조 적용 사례

• 컴퓨터 디렉토리 구조