Tree

in Algorithms
Tree

Tree에 대해 설명하는 페이지입니다.

Environment

  • OS: Windows 11

목차

Introduction

  • Definition
    • 트리(Tree)는 상위-하위의 계층적 구조를 갖는 자료 구조로, 노드(node)들이 간선(edge)으로 서로 연결되어 있는 자료 구조를 말한다.
    • 트리는 탐색형 자료 구조로 널리 사용되며, 특정 조건을 지키도록 구성된 트리에서는 배열이나 리스트를 사용하는 것보다 같은 작업을 더 빠르게 수행할 수 있다.
    • 주요 용어
      • 노드(node): 자료가 저장된 곳을 말한다. 노드 사이에는 상/하위 관계가 존재하며, 상위 노드를 부모(parent), 하위 노드를 자식(child) 노드라고 부른다. 부모 노드가 서로 같은 두 노드는 형제(sibling) 노드라고 부르며, 부모 노드와 그의 부모들을 통틀러 선조(ancestor), 자식 노드와 그의 자식들을 통틀어 자손(descendant)이라고도 부른다.
      • 루트(root): 자신과 연결되어 있는 다른 노드들을 자손으로 갖는 노드를 말한다. 트리에는 오직 단 하나의 루트만 존재한다.
      • 간선(edge): 노드들을 서로 연결하고 있는 것을 말한다.
      • 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 말한다.
      • 높이(height): 트리에서 가장 깊숙히 있는 노드의 깊이를 말한다.
      • 서브 트리: 전체 트리 구조에서 어떤 노드와 그 자손들로 구성된 트리를 말한다.
    • 이진 트리의 순회 종류
      이진 트리의 순회 순서 중 유명한 세 가지로 다음과 같은 순회 순서가 존재한다.
      • 전위 순회(Preorder Traverse): (루트)(왼쪽 서브 트리)(오른쪽 서브 트리) 순서로 순회하는 것을 말한다.
      • 중위 순회(Inorder Traverse): (왼쪽 서브 트리)(루트)(오른쪽 서브 트리) 순서로 순회하는 것을 말한다.
      • 후위 순회(Postorder Traverse): (왼쪽 서브 트리)(오른쪽 서브 트리)(루트) 순서로 순회하는 것을 말한다.
  • Characteristics
    • 재귀적 속성: 트리에서 한 노드와 그의 자손들을 모두 모으면 그들도 하나의 트리가 된다. 하나의 트리는 루트와 루트 밑에 존재하는 서브 트리의 집합이라고 할 수 있다.
    • 트리의 표현: 트리는 여러 가지 방식으로 표현할 수 있다. 가장 일반적인 형태는 각 노드를 하나의 구조체/객체로 표현하고, 이들을 서로의 포인터로 연결하는 것이다.

How to Use

  • 트리의 노드
    // TypeScript
class TreeNode<T> {
  value: T, // 저장할 자료
  parent: TreeNode<T>, // 부모 노드를 가리키는 포인터
  children: Array<TreeNode<T>> // 자식 노드를 가리키는 포인터
}
  • 트리의 순회
    트리의 재귀적 속성을 이용하면 트리의 순회를 쉽게 구현할 수 있다.
    // TypeScript
const traversal = (root: TreeNode<number>) => {
  console.log(root.value);
    
  const length: number = root.children.length;
  for (let i = 0; i < length; i++) {
    traversal(root.children[i]);
  }
}
  • 트리의 높이
    트리의 높이는 루트의 각 자식을 루트로 하는 서브 트리들의 높이를 각각 재귀 호출을 통해 계산하고, 그 중 최댓값에 1을 더한 것과 같다.
    // TypeScript
const height = (root: TreeNode<number>): number => {
  let h = 0;
  let length = root.children.length;
  for (let i = 0; i < length; i++) {
    h = Math.max(h, 1 + height(root.children[i]));
  }
  return h;
}

Examples




Comments