공부시간 : 19:30 ~ 22:00

오늘의 공부
[자료구조/알고리즘] 자료구조 기초 : Tree

💡 Tree

💜 Tree 개념

• 데이터의 상-하 관계(=계층적 관계)를 저장하는 자료구조
• 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아있다고 해서 트리 구조라고 함
• 컴퓨터 폴더 구조 등이 트리 구조의 예시에 해당
• 데이터를 순차적으로 나열한 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있으므로 비선형 구조에 해당
• 계층적으로 표현이 되고 아래로만 뻗어나가므로 사이클이 없음
• 여러 개의 정점으로 구성되어 있으며, 트리는 하위 관계가 있는 정점들을 가리키는 레퍼런스를 가지며 보통 이 레퍼런스를 화살표로 나타냄
• 상-하 관계로 나누어졌을 때 상에 해당하는 정점을 부모노드, 하에 해당하는 정점을 자식노드라고 표현하며, 이렇게 나뉜 상-하 관계를 부모-자식 관계라고 표현하기도 함
• 트리 구조에서 최상단에 존재하는 정점을 나무의 뿌리에 빗대어 root 노드라고 함

💜 Tree 용어

🤍 Root 노드

• 트리의 시작 노드로 즉, 뿌리가 되는 노드
• 보통 트리를 표현할 때 최상단에 존재

🤍 부모 노드

• 특정 노드의 직속 상위 노드

🤍 자식 노드

• 특정 노드의 직속 하위 노드로, 부모 노드와 반대되는 개념

🤍 형제 노드

• 같은 부모를 갖는 노드

🤍 Leaf 노드

• 자식 노드를 가지고 있지 않은, 가장 말단에 있는 노드
• 트리의 끝에 있다고 하여 Root 노드와 반대로 Leaf 노드라고 표현

🤍 깊이

• 특정 노드가 Root 노드로부터 떨어져있는 거리

🤍 레벨

• 깊이 + 1
• 깊이와 거의 똑같은 개념으로, 특정 깊이인 노드들을 묶어서 표현할 때 사용하는 용어

🤍 높이

• 트리에서 가장 깊이 있는 노드의 깊이

🤍 부분 트리

• 현재 트리의 일부분을 이루고 있는 더 작은 트리
• 하나의 전체 트리에는 여러 개의 부분 트리들이 존재하기도 함

💜 Tree 활용

• 데이터 사이의 계층적 관계를 컴퓨터에서 나타낼 수 있도록 해주는 자료구조가 트리!
• 정렬이나 압축과 같은 컴퓨터 과학의 다양한 문제들을 해결하는 데에 트리 구조가 유용
• 딕셔너리, 우선순위 큐, 세트 등 다양한 추상 자료형을 구현하는 데에 사용가능

💜 Tree 순회

• 자료구조에 저장된 데이터를 하나씩 다 도는 것을 말함
• 트리를 순회할 때는 주로 재귀를 사용
• 트리 순회의 기본 동작 3가지
  1. 재귀적으로 왼쪽 부분트리 순회
  2. 재귀적으로 오른쪽 부분트리 순회
  3. 현재 노드의 데이터를 출력

🤍 pre-order

• 두 개의 부분트리 순회 전에 노드의 데이터를 출력하는 순회방법
• 트리 순회의 기본 동작 3가지를 아래와 같은 순서로 진행
  1. 현재 노드의 데이터를 출력
  2. 재귀적으로 왼쪽 부분트리 순회
  3. 재귀적으로 오른쪽 부분트리 순회

🤍 post-order

• 두 개의 부분트리 순회 후에 노드의 데이터를 출력하는 순회방법
• 트리 순회의 기본 동작 3가지를 아래와 같은 순서로 진행
  1. 재귀적으로 왼쪽 부분트리 순회
  2. 재귀적으로 오른쪽 부분트리 순회
  3. 현재 노드의 데이터를 출력

🤍 in-order

• 데이터를 출력하는 동작이 두 개의 부분트리들을 순회하는 동작들 사이에 끼어있는 순회방법
• 트리 순회의 기본 동작 3가지를 아래와 같은 순서로 진행
  1. 재귀적으로 왼쪽 부분트리 순회
  2. 현재 노드의 데이터를 출력
  3. 재귀적으로 오른쪽 부분트리 순회

💜 Tree 구현

class Tree {
  // tree 의 constructor 를 구현
  // tree 의 자식 노드들을 children 으로 할당하여 노드의 자식 노드들을 담을 수 있게 설정
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  // tree 의 자식 노드를 생성 한 후에, 노드의 children 에 push
  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }
  // tree 에서 value 값을 탐색
  // 현재 노드의 value 값이 찾는 값과 일치한다면 return
  contains(value) {
    if (this.value === value) {
      return true;
    }
    // 노드가 가진 자식 노드를 순회하는 반복문으로 노드의 children 배열을 탐색
    for (let i = 0; i < this.children.length; i += 1) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }
    return false;
  }
}