[DS] 8. 트리

트리(Tree)?

노드 사이의 계층적인 관계를 표현하는 비선형 자료구조.

컴퓨터의 폴더 구조, 가족의 가계도, 직장의 조직도 등이 트리와 유사한 구조를 가진다.

인공지능 분야에서도 여러 조건에 따라 판단을 내리는 결정 트리 등의 형태로 사용된다.

---

트리의 용어

용어	설명
노드(Node)	트리를 구성하는 각각의 요소.
루트 노드(Root Node)	트리의 가장 위에 존재하는 노드.
간선(Edge)	두 노드 사이의 연결 관계를 나타내는 선.
부모 노드(Parent Node)	연결된 두 노드 중 상위에 있는 노드.
자식 노드(Child Node)	연결된 두 노드 중 하위에 있는 노드.
형제 노드(Sibling Node)	같은 부모를 가진 노드들.
조상 노드(Ancestor Node)	루트부터 임의의 노드까지의 경로에 존재하는 상위 노드들.
자손 노드(Descendant Node)	임의의 노드 아래에 연결된 모든 노드들.
단말 노드(Leaf Node)	자식 노드가 없는 노드.
비단말 노드(Internal Node)	하나 이상의 자식 노드를 가진 노드.
차수(Degree)	하나의 노드가 가진 자식 노드의 수.
레벨(Level)	노드의 계층 단계. (즉, 깊이)
높이(Height)	트리가 가진 최대 레벨.
서브트리(Subtree)	어떤 노드와 그 노드의 자손들로 구성된 트리.
포레스트(Forest)	서로 독립된 트리들의 집합.

이 글에서는 루트 노드의 레벨을 1로 가정한다. (즉 0으로 가정한다면 현재 그림의 레벨과 높이에서 1을 빼야 한다.)

---

이진트리(Binary Tree)?

모든 노드가 최대 두 개의 자식 노드를 갖는 트리.

이진트리의 각 노드는 왼쪽 서브트리와 오른쪽 서브트리를 가진다.

두 서브트리는 서로 구분되어야 한다. 즉, 좌/우 별로 순서의 개념이 존재한다는 것.

이진트리의 성질

• $n$개의 노드를 가진 이진트리는 $n - 1$개의 간선을 가진다.
• 높이가 $h$인 이진트리는 최소 $h$개, 최대 $2^h - 1$개의 노드를 가진다.
• $n$개의 노드를 가진 이진트리의 높이는 최소 $\lceil \log_2(n + 1) \rceil$, 최대 $n$이다.

이진트리의 종류

종류	설명
포화 이진트리 (Full Binary Tree)	모든 레벨에 노드가 가득 차 있는 이진트리.
완전 이진트리 (Complete Binary Tree)	마지막 레벨을 제외한 모든 레벨이 가득 차 있고, 마지막 레벨의 노드는 왼쪽부터 채워진 이진트리.

추상 자료형

연산	설명
create()	빈 이진트리를 생성한다.
isEmpty()	이진트리가 비어 있는지 확인한다.
getRoot()	이진트리의 루트 노드를 반환한다.
getCount()	이진트리의 총 노드의 수를 반환한다.
getHeight()	이진트리의 높이를 반환한다.
insertNode(node)	이진트리에 노드 n을 삽입한다.
deleteNode(node)	이진트리에 노드 n을 삭제한다.
display()	이진트리의 내용을 출력한다.

---

이진트리의 표현

배열 표현법

이진트리의 각 노드에 순서대로 번호를 부여하고, 이 번호를 배열의 인덱스로 사용하여 노드 정보를 저장하는 방법이다.

루트 노드의 인덱스를 1이라고 하면 각 노드의 위치는 다음과 같이 계산할 수 있다.

노드	인덱스
부모 노드	index / 2
왼쪽 자식	index * 2
오른쪽 자식	index * 2 + 1

포화 이진트리나 완전 이진트리에서는 메모리 낭비 없이 노드를 연속적으로 저장할 수 있다.

그러나 이외의 이진트리에서는 노드가 없는 빈 공간으로 인해 메모리 낭비가 발생한다. 위 이미지는 그 경우의 극단적인 예시다.

링크 표현법

각 노드가 데이터와 함께 좌/우 자식 노드의 주소를 저장하는 방법이다. 이는 연결 리스트를 이용한 자료구조와 유사하다.

struct Node
{
  int data;
  Node* left = nullptr;
  Node* right = nullptr;
};

노드들은 실제 메모리상에 연속적으로 존재하지 않아도 되며, 자식이 없는 방향에는 nullptr를 할당한다.

이진트리 구현

예제 코드

#include <iostream>

template <typename T>
class BinaryNode
{
protected:
  T data;
  BinaryNode* left;
  BinaryNode* right;

public:
  BinaryNode(
    const T& value,
    BinaryNode* leftNode = nullptr,
    BinaryNode* rightNode = nullptr)
    : data(value), left(leftNode), right(rightNode) { }

  void setData(T value)           { data = value; }
  const T getData()               { return data; }
  void setLeft(BinaryNode* node)  { left = node; }
  BinaryNode* getLeft()           { return left; }
  void setRight(BinaryNode* node) { right = node; }
  BinaryNode* getRight()          { return right; }

  bool isLeaf()
    return left == nullptr && right == nullptr;

  void display()
    std::cout << data;
};

template <typename T>
class BinaryTree
{
public:
  using Node = BinaryNode<T>;
protected:
  Node* root;
public:
  BinaryTree(Node* rootNode = nullptr)
    : root(rootNode) { }

  void setRoot(Node* node) { root = node; }
  Node* getRoot()          { return root; }

  bool isEmpty()
    return root == nullptr;

  void inorder()     { /* ... */ }
  void preorder()    { /* ... */ }
  void postorder()   { /* ... */ }
  void levelorder()  { /* ... */ }
  int getCount()     { /* ... */ }
  int getHeight()    { /* ... */ }
  int getLeafCount() { /* ... */ }
};

---

이진트리의 순회

트리에 속한 모든 노드를 한 번씩 방문하여, 노드가 가진 데이터를 목적에 맞게 처리하는 것.

순환 구조를 이용하면 현재 노드를 기준으로 왼쪽과 오른쪽 서브트리를 같은 방법으로 순회할 수 있다.

전위 순회

루트 → 왼쪽 → 오른쪽 순으로 방문한다.

부모 노드를 자식 노드보다 먼저 처리해야 하는 경우에 사용한다.

void preorder(Node* node)
{
  if (node == nullptr) return;

  visit(node);
  preorder(node->left);
  preorder(node->right);
}

중위 순회

왼쪽 → 루트 → 오른쪽 순으로 방문한다.

void inorder(Node* node)
{
  if (node == nullptr) return;

  inorder(node->left);
  visit(node);
  inorder(node->right);
}

이진 탐색 트리를 중위 순회하면 노드들을 오름차순으로 방문할 수 있다.

후위 순회

왼쪽 → 오른쪽 → 루트 순으로 방문한다.

자식 노드를 부모 노드보다 먼저 처리해야 하는 디렉토리 용량 계산이나 트리 삭제 등에 사용할 수 있다.

void postorder(Node* node)
{
  if (node == nullptr) return;

  postorder(node->left);
  postorder(node->right);
  visit(node);
}

레벨 순회

루트부터 같은 레벨에 있는 노드들을 차례대로 방문한다.

앞의 순회와는 다르게 순환 호출이 아닌 큐를 사용하며, 트리에 대한 너비 우선 탐색(BFS)이라고 보면 된다.

트리는 노드 사이에 순환되는 연결이 없으므로, 따로 방문 여부를 저장할 필요가 없다.

#include <queue>

void levelOrder(Node* root)
{
  if (root == nullptr)
    return;

  std::queue<Node*> queue;
  queue.push(root);

  while (!queue.empty())
  {
    Node* node = queue.front();
    queue.pop();

    visit(node);

    if (node->left != nullptr)
      queue.push(node->left);
    if (node->right != nullptr)
      queue.push(node->right);
  }
}

---

이진트리의 연산

전체 노드 개수

전체 노드 개수는 왼쪽 서브트리의 노드 개수와 오른쪽 서브트리의 노드 개수에 현재 노드 하나를 더한 값이다.

int getCount(Node* node)
{
  if (node == nullptr)
    return 0;

  return 1
    + getCount(node->getLeft())
    + getCount(node->getRight());
}

단말 노드 개수

왼쪽과 오른쪽 자식이 모두 nullptr인 노드는 단말 노드이다.

int getLeafCount(Node* node)
{
  if (node == nullptr)
    return 0;

  if (node->getLeft() == nullptr &&
      node->getRight() == nullptr)
    return 1;

  return getLeafCount(node->left)
       + getLeafCount(node->right);
}

트리의 높이

트리의 높이는 왼쪽과 오른쪽 서브트리의 높이 중 큰 값에 현재 노드의 높이 1을 더한 값이다.

(빈 트리의 높이를 0, 루트 노드 하나만 있는 트리의 높이를 1로 계산)

int getHeight(Node* node)
{
  if (node == nullptr)
    return 0;

  return 1 + std::max(
    getHeight(node->getLeft()),
    getHeight(node->getRight())
  );
}

---

이진트리의 응용

수식 트리

수식 트리는 연산자를 부모 노드에, 피연산자를 자식 노드에 저장하여 수식을 트리 형태로 표현한다.

수식 트리의 순회 방법에 따라 서로 다른 표기법을 얻을 수 있다.

순회	표기법	$a + b$	$a - (b \times c)$
전위 순회	전위 표기법	+ a b	- a * b c
중위 순회	중위 표기법	a + b	a - b * c
후위 순회	후위 표기법	a b +	a b c * -

수식 트리를 계산할 때는 자식 노드를 먼저 계산해야 하므로 후위 순회 구조를 사용할 수 있다.

디렉토리 용량 계산

디렉토리는 하위 파일과 디렉토리들을 자식 노드로 갖는 트리 구조로 표현할 수 있다.

하위 항목들의 크기를 먼저 계산한 뒤 부모 디렉토리에 합산해야 하므로, 후위 순회가 적절하다.

---

스레드 이진트리

각 노드가 후속자를 갖는 스레드 이진트리의 예

링크 표현법의 이진트리는, 자식 노드가 없는 링크 필드에 nullptr을 저장한다.

스레드 이진트리는 이 빈 필드를, 중위 순회에서의 선행자나 후속자를 가리키는 용도로 재활용한다. 이로써 순환(재귀) 구조 없이 트리 순회를 구현할 수 있게 된다.

대신, 해당 필드가 실제 자식 노드인지를 판단하기 위해, 구분을 위한 별도 필드가 필요하다.

용어	설명
중위 선행자	중위 순회에서, 현재 노드의 바로 앞에 방문하는 노드. 즉, 앞 순서 노드.
중위 후속자	중위 순회에서, 현재 노드의 바로 뒤에 방문하는 노드. 즉, 뒷 순서 노드.

struct ThreadedNode
{
  int data;

  ThreadedNode* left = nullptr;   // 자식 노드 대신, 선행자 삽입 가능
  ThreadedNode* right = nullptr;  // 자식 노드 대신, 후속자 삽입 가능

  bool isLeftThread = false;      // 좌측 자식 or 선행자 구분용 필드
  bool isRightThread = false;     // 우측 자식 or 후속자 구분용 필드
};