2022-01-20 자료구조/tree

 - 그래프의 여러 구조 중 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조의 한 구조

 

- 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조 

 

- 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없음.

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

 

트리구조의 특징

 

- 깊이 : 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있음.

예를 들어 루트 A의 깊이는 0이고, B와 C의 깊이는 1, D, E, F, G 의 깊이는 2

 

- 레벨 : 같은 깊이를 가지고 있는 노드를 묶어서 레벨이라 부름

깊이가 0인 루트 A의 레벨은 1, 깊이가 1인 B와 C의 레벨을 2, D . E . F. G의 레벨은 3.

같은 레벨에 나란히 있는 노드를 형제 노드라 부름 

 

- 높이 : 리프 노트를 기준으로 루트까지의 높이를 표현 할 수 있음.

부모 노드는 자식 노드의 가장 높은 높이 값에 + 1의 높이를 가짐.

 

예를들어 H, I, E, F, J의 높이는 0 , D와 G의 높이는 1, B와 C의 높이는 2

루트 A의 높이는 3.

 

 

트리의 실사용 예제

 

컴퓨터의 디렉토리 구조 , 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등.