[자료구조] Tree

📌  Tree (트리)

자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습인데, 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮았다고 해서 트리 구조라고 부른다.

 

마치 가계도와 흡사해 보이는 이 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조이다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클(cycle)이 없다.

 

💭 Whta is Cycle ?

시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 표현한다. 따라서 트리는 사이클(cycle)이 없는 하나의 연결 그래프 (Connected Graph)이다.

 

 

Tree의 구조와 특징

트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 맺는다. 위 그림에서 P는 Q와 R의 부모 노드(Parent Node)이고, Q와 R는 P의 자식 노드(Child Node)이다. 또한, 이러한 관계로 인해 Q와 R는 형제 노드(Sibling Node)라고 한다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.

 

Tree 구조는 계층적 구조를 가지기 때문에 그의 깊이와 높이 그리고 레벨을 측정할 수 있다. 

 

• 깊이 (depth)
  트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. 루트 노드는 지면에 있는 것처럼 깊이가 0이다. 위 그림에서 루트 P의 깊이는 0이고, Q와 R의 깊이는 1이다. A, B, C, D의 깊이는 2이다.
  
  
• 레벨(Level)
  트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다. 깊이가 0인 루트 P의 level은 1이다. 깊이가 1인 Q와 R의 level은 2이며, A, B, C, D의 레벨은 3이다. 이렇게 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node) 라고 한다.
  
  
• 높이(Height)
  트리 구조에서 리프노드를 기준으로 루트까지의 높이를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 높이 값에 +1한 값을 높이로 가진다. 트리 구조의 높이를 표현할 때는 각 리프 노드의 높이를 0으로 놓기 때문에 위 그림에서 E, F, G, B, H, I, D의 높이는 0이고, L와 M의 높이는 1이며, A와 C의 높이는 2가 된다. 
  
  
• 서브 트리(Sub tree)
  트리 구조의 루트에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다. (L, E, F,G)로 이루어진 작은 트리도 서브 트리이고, (M, H, I)나 (Q, A, B) 와 (R, C, D)도 서브 트리이다.

 

 

Tree의 실사용 예제

- 컴퓨터의 디렉토리 구조

Tree 구조의 가장 대표적인 실사용 예시는 컴퓨터의 디렉토리 구조이다. 어떤 프로그램이나 파일을 찾을 때, 루트 폴더에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다. 이 때 모든 폴더는 하나의 폴더에서 시작되어, 가지를 뻗어나가는 모양새가 바로 트리 구조이다. 이렇게 사용자들이 편하게 사용하기 위한 파일 시스템 드엥서는 트리 구조가 이용되어 만들어져 있다. 

 

이 외에는 토너먼트 대진표, 가계도 등이 트리 구조의 예시이다. 

 

 

Tree 구현

- class로 구현 

class Tree {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  // 트리의 삽입 메서드
  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

  // 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드
  contains(value) {
    if (this.value === value) {
      return true;
    }

    for (let i = 0; i < this.children.length; i++) {
      if (this.children[i].contains(value)) {
        return true;
      }
    }
    // 전부 탐색했음에도 찾지 못했다면 false를 반환
    return false;
  }
}

// const rootNode = new Tree(null);

// for(let i = 0; i <= 4; i++) {
//   if(rootNode.children[i]) {
//     rootNode.children[i].insertNode(i);
//   }
//  rootNode.insertNode(i); 
// }
// rootNode; // {value: null, children: Array(5)}
// rootNode.contains(5); // false
// rootNode.contains(1); // true