Tree

01. 개념

  • 계층적인 자료를 표현하는데 적합한 자료구조입니다.
    • 선형 자료 구조 : 리스트, 스택, 큐
  • 이러한 구조를 Tree 라고 부르는 이유는 마치 실제 트리를 거꾸로 엎어놓은 것 같은 모양을 하고 있기 때문입니다.

02. 특징

  • 사이클이 없는 하나의 연결 그래프입니다.
  • 간선의 개수 = 정점의 개수 - 1 (E = V - 1)
  • 루트에서 어떤 노드로 가는 경로는 유일합니다.
    • 두 개의 정점 사이에 반드시 1 개의 경로만 가집니다.

03. 관련 용어들

  • 루트(Root) : 부모가 없는 노드
  • 부모(Parent) : 자식이 있는 노드
  • 자식(Children) : 부모가 있는 노드
  • 단말 노드(Leaf Node) : 자식이 없는 노드
  • 형제(Sibling) : 같은 부모를 가진 노드들
  • 조상(Ancestor) : 루트 노드를 통과하지 않고 갈 수 있는 노드들 중에서 자신 보다 루트에 가까운 노드들
  • 자손(Descendent) : 루트 노드를 통과하지 않고 갈 수 있는 노드들 중에서 자신 보다 루트에서 먼 노드들
  • 간선(edge) : 노드를 연결하는 선
  • 차수(degree) : 어떤 노드가 가지고 있는 자식 노드의 개수
  • 레벨(level) : 트리의 각 층에 번호를 매기는 것으로서 루트의 레벨은 1이 되고, 한 층씩 내려갈수록 1씩 증가합니다.
  • 높이(height) : 트리가 가지고 있는 최대 레벨을 말합니다.

04. 트리의 종류

  • 일반 트리 : 자식 노드의 개수가 일정하지 않은 트리
  • 이진 트리 : 자식 노드의 개수가 2 개인 트리

05. 이진 트리

  • 이진 트리 정의
    • 공집합이거나
    • 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의됩니다. 이진 트리의 서브 트리들은 모두 이진트리여야 합니다.
  • 트리 중에서 가장 많이 쓰이는 트리입니다.
  • 모든 노드가 2 개의 서브 트리를 가지고 있는 트리입니다. (서브 트리는 공집합일 수 있습니다.)
  • 최대 2 개까지의 자식 노드가 존재할 수 있고, 모든 노드의 차수가 2 이하가 됩니다.
  • 이진 트리에는 서브 트리 간의 순서가 존재합니다. 따라서 왼쪽 서브 트리와 오른쪽 서브 트리는 서로 구별됩니다.
  • 노드의 개수가 n 개 일때, 간선의 개수는 n - 1 개입니다.
  • 높이가 h 인 이진 트리의 경우 최소 h 개의 노드를 가지며 최대 2 ^ h - 1 개의 노드를 가집니다.
  • n 개 의 노드를 가지는 이진트리의 높이는 최대 n 이거나 최소 log(n + 1) 이 됩니다.

06. 이진 트리의 종류

  • 포화 이진 트리, 완전 이진 트리, 기타 이진 트리가 있습니다.
  • 포화 이진 트리 (Perfect Binary Tree)
    • 트리의 각 레벨에 노드가 꽉 차있는 이진 트리를 의미합니다.
    • 말단 노드를 제외한 노드의 자식의 수는 2 입니다.
    • 말단 노드의 자식의 수는 0 입니다.
    • 모든 말단 노드의 깊이가 같아야 합니다.
    • 높이가 k 인 포화 이진 트리는 정확하게 2 ^ k - 1 개의 노드를 가집니다.
  • 완전 이진 트리 (Complete Binary Tree)
    • 높이가 k 일 때, 레벨 1 부터 k - 1 까지는 노드가 모두 채워져 있고, 마지막 레벨 (k) 에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리를 의미합니다.
    • 마지막 레벨에서는 노드가 꽉차있지 않아도 되지만, 중간에 빈곳이 있어서는 안됩니다.
    • 즉, 마지막 레벨에는 오른쪽 노드가 일부 없을 수도 있습니다.

07. 이진 트리의 표현

  • 트리는 그래프이기 때문에, 그래프로 표현할 수 있습니다.
  • 단, 루트가 주어진다면, 트리만의 저장방식으로 표현할 수 있습니다.
  • 각 노드의 부모 노드를 저장하는 방법 (parent 배열)
    • 모든 노드는 부모를 1 개만 가지고 있고, 부모가 없는 노드는 1 개만 있으니까 가능합니다.
    • Union-Find
  • 이진 트리의 경우, 배열로 표현하는 방법
    • 부모 노드 : x, 자식 노드 : 2 * x, 2 * x + 1
    • 이진 트리의 경우에만 사용할 수 있습니다.
    • N 개의 노드로 이루어져 있으면 딱 1 ~ N 개까지 번호가 정해져서 효율적입니다.

  • 구조체나 클래스를 이용하는 방법

    • 데이터를 저장하는 필드와 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 2 개의 링크 필드를 구현해서 사용하는 방법입니다.
    class Node {
	constructor(data, left, right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}
}

08. 이진 트리의 순회

  • 이진 트리에 속하는 모든 노드를 한 번씩 방문하는 것을 말합니다.
  • 트리도 그래프이기 때문에 DFS, BFS 모두 가능합니다.
  • DFS 는 노드, 왼쪽 자식, 오른쪽 자식이 있을 때, 노드를 언제 방문할지에 따라서 전위 순회(preorder), 중위 순회 (inorder), 후위 순회 (postorder) 이렇게 총 3 가지 방문 순서가 있습니다.

  • 전위 순회 (Pre-Order)

    1. 노드 방문
    2. 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더
    3. 오른쪽 자식 노드를 루트로 하는 서브 트리를 프리오더
    const preOrder = (nodes, index) => {
	if (index === null) return;

	console.log(index);
	preOrder(nodes, nodes[index].left);
	preOrder(nodes, nodes[index].right);
};

  • 중위 순회 (In-Order)

    1. 왼쪽 자식 노드를 루트로 하는 서브 트리를 인오더
    2. 노드 방문
    3. 오른쪽 자식 노드를 루트로 하는 서브 트리를 인오더
    const inOrder = (nodes, index) => {
	if (index === null) return;

	inOrder(nodes, nodes[index].left);
	console.log(index);
	inOrder(nodes, nodes[index].right);
};

  • 후위 순회 (Post-Order)

    1. 왼쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더
    2. 오른쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더
    3. 노드 방문
    const postOrder = (nodes, index) => {
	if (index === null) return;

	postOrder(nodes, nodes[index].left);
	postOrder(nodes, nodes[index].right);
	console.log(index);
};

Reference.