[Java / 자료구조] 트리 (Tree) 정리

트리(Tree)란?

Tree는 이름 그대로 나무를 거꾸로 뒤집어 놓은 형태를 가지고 있다. 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태이다. 

데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.

아래로만 뻗어나가기 때문에 사이클이 없다.

트리 구조는 루트(root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다. A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Childe Node)이다. 자식이 없는 노드는 리프 노드(Leaf Node)라고 부른다.

 

깊이(depth)

루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다. 루트 노드는 깊이가 0이고 B와 C의 깊이는 1, D, E, F, G의 깊이는 2이다.

 

레벨(Level)

같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있다. A의 Level은 1이다. B와 C의 Level은 2이다. D, E, F, G의 레벨은 3이다. 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다.

 

높이(Height)

리프 노드(Leaf Node)를 기준으로 루트까지의 높이(Height)를 표현할 수 있다. 부모 노드는 자식 노드의 가장 높은 height값+1 한 값을 높이로 가진다. 각 리프 노드의 높이를 0으로 놓는다. H, I, E, F, J의 높이는 0이다. D와 G의 높이는 1이다. B와 C의 높이는 2이다. 이때, B는 D의 height + 1을 C는 G의 height + 1을 높이로 가진다. 루트 A의 높이는 3이다.

 

서브 트리(Sub Tree)

root에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리를 서브 트리라고 한다. (D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E) (C, F, G, J)도 서브 트리이다.

 

 

용어 정리

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

 

트리의 실사용 예제

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