Tree
Tree의 정의
그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부름.
데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조임. 트리 구조는 계층적으로 표현이 되고 아래로만 뻗어나가기 때문에 사이클이 없음.
Tree의 구조와 특징
트리 구조는 루트(root)라는 하나의 꼭지점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결함. 각 데이터를 노트(node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가짐. 위 그림에서 A는 B와 C의 부모 노드(parent node)이고, B와 C는 A의 자식 노드(child node)임. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf node)라고 부름.
깊이(depth)
루트로부터 하위 계층의 특정 노트까지의 깊이(depth)를 표현할 수 있음. 루트 노드는 지면에 있는 것처럼 깊이가 0임. 위 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1임. D, E, F, G의 깊이는 2임.
레벨(level)
같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있음. depth가 0인 루트 A의 level1은 1임. depth가 1인 B와 C의 level은 2임. D, E, F, G의 레벨은 3임. 같은 레벨에 나란히 있는 노드를 형제 노드(sibling node)라고 함
높이(height)
리프 노트를 기준으로 루트까지의 높이(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): 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
Tree의 실사용 예제
가장 대표적인 예제는 컴퓨터의 디렉토리 구조임. 어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾음. 모든 폴더는 하나의 폴더(루트 폴더, /)에 시작되어 가지를 뻗어나가는 모양새를 띔.
연습 문제 - 트리 구현
import java.util.*;
public class Solution {
private String value;
private ArrayList<Solution> children;
public Solution() { //전달인자가 없을 경우의 생성자
this.value = null;
this.children = null;
}
public Solution(String data) { //전달인자가 존재할 경우의 생성자
this.value = data;
this.children = null;
}
public void setValue(String data) {
this.value = data;
}
public String getValue() { //현재 노드의 데이터를 반환
return value;
}
public void addChildNode(Solution node) {
if(children == null) children = new ArrayList<>();
children.add(node);
}
public void removeChildNode(Solution node) {
String data = node.getValue();
if(children != null) {
for(int i = 0; i < children.size(); i++) {
if(children.get(i).getValue().equals(data)) {
children.remove(i);
return;
}
if(children.get(i).children != null) children.get(i).removeChildNode(node);
}
}
}
public ArrayList<Solution> getChildrenNode() {
return children;
}
public boolean contains(String data) { //재귀를 사용하여 값을 검색합니다.
if(value.equals(data)) return true;
boolean check;
if(children != null) {
for(int i = 0; i < children.size(); i++) {
check = children.get(i).contains(data, false);
if(check) return true;
}
}
return false;
}
public boolean contains(String data, boolean check) { //재귀를 사용하여 값을 검색합니다.
if(value.equals(data)) return true;
if(children != null) {
for(int i = 0; i < children.size(); i++) {
check = children.get(i).contains(data, check);
}
}
return check;
}
}