트리 (Tree)

Jun 2k (Jun2)·2023년 9월 27일

자료구조&알고리즘

목록 보기

10/19

트리

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조이다.

출처: 이선협 강사님 데브코스 강의 자료

용어 정리

Root(루트) : 가장 상위 노드

Node(노드) : 각 정점을 노드라고 부른다.

Leaf Node(리프 노드) : 자식이 없는 노드

Level(레벨) : 루트로 부터 몇 번째 깊이인지 나타내는 지표

Degree(차수) : 한 정점에서 뻗어 나가는 간선의 갯수

트리는 조직도 또는 디렉터리 구조에서 가장 많이 사용된다.

트리의 특징

루트를 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
루트에서 특정 정점으로 가는 경로는 유일하다. (간선 1개)

이진 트리

각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.
이진 트리는 탐색에 많이 사용하므로 잘 알아두는 것이 좋다.

이진트리의 종류
1. 완전 이진 트리 : 리프 노드를 제외한 모든 정점이 자식을 가지는 이진 트리
1. 포화 이진 트리 : 리프 노드를 제외한 모든 정점이 2개의 자식을 가지는 이진 트리
2. 편향 트리 : 한 방향으로만 자식 노드를 가지는 트리

이진 트리의 특징

정점이 N개의 이진 트리는 최악의 경우 높이가 N이 될 수 있다.
=> N개의 정점을 가진 편향트리가 된다.
정점이 N개인 포화 or 완전 이진 트리의 높이는 log N이 된다.
=> 레벨이 증가하면 두 개의 정점이 생기기 때문이다.
높이가 h인 포화 이진 트리는 2^h - 1개의 정점을 가진다.

일반적으로 이진 트리를 바로 사용하는 경우는 많지 않다. 다음과 같은 자료구조로 응용한다.
- 이진 탐색 트리
- 힙
- AVL 트리
- 레드 블랙 트리

트리의 구현 방법

그래프와 마찬가지로 인접 행렬, 인접 리스트로 두 가지 방식이 존재한다.
1차원 배열 또는 요소에 링크가 2개 존재하는 연결 리스트로 각각 구현이 가능하다.

출처: 이선협 강사님 데브코스 강의 자료

JavaScript에서 구현하는 법

배열로 이진 트리 구현

출처: 이선협 강사님 데브코스 강의 자료

// 인덱스 0은 비워둔다. 헷갈리므로
// Left = index * 2, Right = index * 2 + 1
// Parent = floor(index / 2)
const tree = [
  undefined,
  // 1
  9,
  // 1*2, 1*2+1
  3, 8,
  // 2*2, 2*2+1, 3*2, 3*2+1
  2, 5, undefined, 7,
  // 4*2, 4*2+1, 5*2, 5*2+1
  undefined, undefined, undefined, 4
]

연결 리스트로 이진 트리 구현

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class Tree {
  constructor(node) {
    this.root = node;
  }

  display() {
    const queue = new Queue(); // 큐 사용
    queue.enqueue(this.root);
    while (queue.size) {
      const currentNode = queue.dequeue();
      console.log(currentNode.value);
      if (currentNode.left) queue.enqueue(currentNode.left);
      if (currentNode.right) queue.enqueue(currentNode.right);
    }
  }
}

const tree = new Tree(new Node(9));
tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);