트리는 스택/큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다. 트리라는 자료구조는 표현에 집중한다.

Tree

구성 요소는 아래와 같다.

• Node(노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
• Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
• Root Node(루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
• Terminal Node(=leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않는 노드를 의미한다.
• Internal Node(내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

차수랑 level이랑 헷갈릴 수 있는데, 차수는 루트 노드가 1이고, level은 루트 노드가 0이다.

이진 트리(Binary Tree)

루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나눠진다. 또한 나눠진 두 서브트리도 모두 이진 트리여야 한다. 공집합도 이진 트리에 포함된다. 즉 노드가 하나 뿐인 것도 이진 트리 정의에 만족한다.

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level이라고 한다. 레벨의 값은 루트노드에서 0부터 시작한다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height 높이라고 한다.

포화 이진 트리(Perfect Binary Tree)

모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다.

완전 이진 트리(Complete Binary Tree)

위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다.

정 이진 트리(Full BInary Tree)

모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가치켜 정 이진 트리라고 한다.

배열로 구성된 Binary Tree는 노드의 개수가 n개이고 root가 0이 아닌 1에서 시작할 때, i번째 노드에 대해서

• parent(i) = i/2
• left_child(i) = 2i
• right_child(i) = 2i+1

의 인덱스를 갖는다.

Python

우선 노드를 구현하자.

class Node:
  def __init__(self, item):
    self.data = item
    self.left = None
    self.right = None
    
  def size(self):
    l = self.left.size() if self.left else 0
    r = self.left.size() if self.right else 0
    return l+r+1
    
  def depth(self):
    leftDepth = self.left.depth() if self.left else 0
    rightDepth = self.right.depth() if self.right else 0
    return leftDepth + 1 if leftDepth > rightDepth else rightDepth +1
    
  def inorder(self): // 중순위
    traverse = []
    if self.left: traverse += self.left.inorder()
    traverse.append(self.data)
    if self.right: traverse += self.right.inorder()
    return traverse
    
  def preorder(self): // 후순위
    traverse = []
    if self.left: traverse += self.left.preorder()
    if self.right: traverse += self.right.preorder()
    traverse.append(self.data)
    return traverse
    
  def postorder(self):
    traverse = []
    if self.left: traverse += self.left.preorder()
    if self.right: traverse += self.right.preorder()
    traverse.append(self.data)
    return traverse
    
class BinaryTree:
  def __init__(self, r):
    self.root = r
    
  def size(self):
    if self.root: return self.root.size()
    else : return 0
    
  def depth(self):
    if self.root: return self.root.depth()
    else: return 0
    
  def inorder(self):
    if self.root: return self.root.inorder()
    else: return []
    
  def preorder(self):
    if self.root: return self.root.preorder()
    else: return []
    
  def postorder(self):
    if self.root: return self.root.postorder()
    else: return []

C++

#include <iostream>

using namespace std;

template <typename T>
class Tree;

template <typename T>
class TreeNode {
  friend class Tree<T>;
private:
  T data;
  TreeNode* left;
  TreeNode* right;
public:
  TreeNode(T data=0, TreeNode* left = null, TreeNode* right = null) {
    this->data = data;
    this->left = left;
    this->right = right;
  }
};

template <typename T>
class Tree{
  private:
    TreeNode<T>* root;
  public:
    Tree(T data = 0) {
      root = new TreeNode<T> (data);
    }
    
    void visit(TreeNode<T>* current) {
      cout<<current->data << " ";
    }
    
    void preorder(TreeNode<T>* current) {
      if (current != null) {
        visit(current);
        preorder(current->left);
        preorder(current->right);
      }
    }
    
    void inorder(TreeNode<T>* current) {
      if (current != null) {
        inorder(current->left);
        visit(current);
        inorder(current->right);
      }
    }
    
    void postorder(TreeNode<T>* current) {
      if (current != null) {
        postorder(current->left);
        postorder(current->right);
        visit(current);
      }
    }
}

BST (Binary Search Tree)

효율적인 탐색을 위해서는 어떻게 찾을지도 중요하지만 효율적인 탐색을 위한 저장방법 또한 같이 고민해야 한다. 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.

규칙은 다음과 같다.

• 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
• 1. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
• 1. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
• 1. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖느다. 정확히는 O(h)이다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두배씩 증가하기 떄문이다. 하지만 이러한 이진 탐색 트리는 편향 트리(Skewed Tree)가 될 수 있다. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 떄문이다. 이럴 경우에는 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는 O(n)이 된다.

이렇게 worst case의 경우에서는 배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다. 이를 해결하기 위해 Rebalancing 기법이 등장하였다. 균형을 잡기 위한 트리 구조의 재조정을 Rebalancing이라 한다. 이 기법을 구현한 트리에는 여러 종류가 존재하는데 그 중에서 하나가 뒤에서 살펴볼 Red-Black Tree이다.

시간복잡도

탐색, 삽입, 삭제의 시간복잡도가 O(h), O(logn)이 된다. 즉 트리의 height에 따라 수행시간이 결정된다.

위에서 극단적인 구조를 갖는 편향 트리는 시간복잡도가 O(n)이 된다고 했는데, 이런 문제를 해결한 것이 AVL 트리이다. AVL트리는 BST의 장점을 살리면서 균형이 깨진다는 단점을 해결했다.

Heap

힙은 우선순위 큐를 위해 만들어진 자료구조이다.

그렇다면 우선순위 큐는 무엇일까?

우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조이다.

데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나간다. 우선순위 큐는 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영 체제에서의 작업 스케줄링, 수치 해석적인 계산에 사용된다.

우선순위 큐의 구현은

1. 배열
2. 연결리스트
3. 힙

으로 구현이 가능하다. 이 중에서도 힙으로 구현하는 것이 가장 효율적이다.

그렇다면 힙은 무엇일까?

힙(Heap)

• 완전 이진 트리의 일종
• 여러 개의 값들 중 최댓값, 최솟값을 빨리 찾아내도록 만들어진 자료구조
• 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. (큰 값이 상위, 작은 값이 하위 레벨에 존재)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰/작은 이진트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다.(이진 탐색 트리에서는 중복된 값을 허용하지 않았다.)

종류

1. 최대 힙(max heap)
   • 부모 노드의 키 값 >= 자식 노드의 키 값 인 완전 이진 트리
2. 최소 힙(min heap)
   • 부모 노드의 키 값 <= 자식 노드의 키 값 인 완전 이진 트리

구현

힙은 보통 배열로 구현한다. 구현을 쉽게 하기 위해 배열의 0번째 인덱스는 사용되지 않는다.

힙에서의 부모 노드와 자식 노드의 관계는 다음과 같다.

• 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
• 오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1
• 부모의 인덱스 = 자식의 인덱스 / 2

삽입

1. 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환하면서 힙의 성질을 만족시킨다.

삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.)
2. 삭제된 루트 노드의 자리에 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.

특징

1. 힙으로 하는 연산은 시간 복잡도가 좋은 편이다.
2. 힙 정렬이 가장 유용할 때는 전체 자료가 아닌 가장 큰 값 몇개만 필요할 때이다.

시간복잡도

힙 트리의 전체 높이는 거의 logn(완전 이진 트리이므로) 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 logn만큼 소요된다.

요소의 개수가 n개이므로 전체적으로 O(nlogn)의 시간이 걸린다.

T(n) = O(nlogn)

먼저 정렬 알고리즘의 시간복잡도를 비교해보자.

• 단순하지만 비효율적인 방법
  • 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법
  • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

C++