DS #4. 트리와 힙 (Tree and Heap)

 

오늘은 트리와 힙 자료구조에 대해서 알아보려고 한다.

 

트리

트리(Tree)는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 계층적(Hierarchical) 자료구조라고 표현하기도 한다. 유닉스/윈도우의 디렉터리(폴더) 구조가 대표적인 트리 구조의 예시이다. 트리와 관련된 용어들은 다음과 같다.

• 노드(Node) : 트리를 구성하는 기본 원소
• 간선(Edge) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미
• 루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드
• 부모 노드(Parent Node) : 루트 노드 방향으로 직접 연결된 노드
• 자식 노드(Child Node) : 루트 노드 반대방향으로 직접 연결된 노드
• 형제 노드(Siblings Node) : 같은 부모 노드를 갖는 노드들
• 리프 노드(Leaf Node) : 자식이 없는 노드들
• 레벨(Level) : 루트 노드(1)로부터 노드까지 연결된 간선의 수의 합
• 차수(Degree) : 각 노드의 자식의 갯수 
• 높이(Height) : 가장 긴 루트 경로의 길이
• 포레스트(Forest) : 트리들의 집합

 

이진 트리

이진 트리

트리 중에서 가장 많이 쓰이는 트리가 이진 트리(Binary Tree)이다. 부모 노드 밑에 자식 노드가 최대 2개밖에 오지 않는, 트리의 가장 간단한 형태이다. 하나의 노드 데이터와 왼쪽, 오른쪽 자식 노드를 가리키는 두 개의 포인터를 가진 구조로 구현할 수 있다. 이진 트리 중에서 높이가 k일 때, 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리를 완전 이진 트리(Complete Binary Tree)라고 한다. 완전 이진 트리의 경우 1번부터 시작하는 배열의 경우 n 번째 원소의 왼쪽 자식은 2n, 오른쪽 자식은 2n+1로 구현할 수 있다. 또한 n 번째 원소의 부모 노드는 [n/2] 번째 원소가 된다.

다음은 자바로 구현한 이진 트리 소스 코드이다.

class Node 
{ 
    int key; 
    Node left, right; 
  
    public Node(int item) 
    { 
        key = item; 
        left = right = null; 
    } 
} 
  
// A Java program to introduce Binary Tree 
class BinaryTree 
{ 
    // Root of Binary Tree 
    Node root; 
  
    // Constructors 
    BinaryTree(int key) 
    { 
        root = new Node(key); 
    } 
  
    BinaryTree() 
    { 
        root = null; 
    } 
  
    public static void main(String[] args) 
    { 
        BinaryTree tree = new BinaryTree(); 
  
        /*create root*/
        tree.root = new Node(1); 
  
        /* following is the tree after above statement 
  
              1 
            /   \ 
          null  null     */
  
        tree.root.left = new Node(2); 
        tree.root.right = new Node(3); 
  
        /* 2 and 3 become left and right children of 1 
               1 
             /   \ 
            2      3 
          /    \    /  \ 
        null null null null  */
  
  
        tree.root.left.left = new Node(4); 
        /* 4 becomes left child of 2 
                    1 
                /       \ 
               2          3 
             /   \       /  \ 
            4    null  null  null 
           /   \ 
          null null 
         */
    } 
} 

이진 트리를 순회하는 방법에는 3가지가 있다. 

1. 중위 순회 (In-order Traversal) : 왼쪽 자식, 자신, 오른쪽 자식 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
2. 전위 순회 (Pre-order Traversal) : 자신, 왼쪽 자식, 오른쪽 자식 순서로 방문하는 순서 방법.
3. 후위 순회 (Post-order Traversal) : 왼쪽 자식, 오른쪽 자식, 자신 순서로 방문하는 순서 방법.
4. 레벨 순서 순회 (Level-order Traversal) : 너비 우선 순회(BFS) 라고도 한다. 노드를 레벨 순서로 방문하는 순회 방법. 위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면, 레벨 순서 순회는 큐를 활용해 구현할 수 있다.

위의 트리를 순회하면 다음과 같다.

1. 인 오더 : 1 3 4 6 7 8 10 13 14
2. 프리 오더 : 8 3 1 6 4 7 10 14 13
3. 포스트 오더 : 1 4 7 6 3 13 14 10 8
4. 레벨 오더 : 8 3 10 1 6 14 4 7 13

 

이진 탐색 트리

이진 탐색 트리(Binary Search Tree)는 이진 트리 기반의 탐색을 위한 자료구조이다. 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성한다. 자식 노드들도 동일한 방법으로 정렬한다. 이렇게 되면 탐색 연산이 O(logN)의 시간 복잡도를 가지게 된다. 다만 이 경우는 이상적인 경우에 해당이 되고, 편향된(skew) 트리의 경우 한 쪽으로만 노드가 추가되면 최악의 경우 탐색 연산이 O(N)의 시간 복잡도를 가진다. 이렇게 되면 최악의 경우 배열보다 많은 메모리를 사용하여 데이터를 저장하고 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다. 이를 해결하기 위해서 Rebalancing 기법이 등장하게 되었다. 여러 가지 방법이 있지만 여기서는 AVL 트리와 Red-black 트리 두 가지를 보도록 한다.

AVL 트리는 이진 탐색 트리가 최악의 경우 O(N)의 시간이 걸리는 것을 보완한 트리이다. AVL 트리는 모든 노드에서 오른쪽 트리의 높이와 왼쪽 트리의 높이 차이가 1 이하로만 나야 한다. 이 때 탐색, 삽입, 삭제의 시간 복잡도는 O(N)이다. 단, 삽입 및 삭제 시 균형이 안 맞을 수 있기 때문에 그럴 때 마다 트리의 일부를 왼쪽 혹은 오른쪽으로 회전 시켜야 한다. 아래에서 살펴볼 Red-black 트리보다 균형이 더 잘 잡히고 탐색 자체는 빠르지만 삽입과 제거가 느리다. 

Red-Black Tree

AVL 트리의 단점을 보완하기 위해 나온 자료구조가 Red-black 트리이다. 자가 균형 이진 탐색 트리의 일종으로 노드에 색깔 속성이 붙은 트리이다. Red-black 트리 역사 항상 탐색/삽입/삭제 모두 시간 복잡도가 O(logN)이다. 이 자료구조는 표현 시 다른 트리와 다르게, 자식이 하나도 없는 리프 노드 끝에 널(NULL) 리프 노드를 붙인다. 그리고 다음과 같은 조건을 만족해야 한다.

• 모든 노드는 레드 아니면 블랙이다.
• 루트 노드는 블랙이다.
• 모든 널 리프 노드는 블랙이다.
• 레드 노드의 자식은 언제나 블랙이다. 즉, 블랙 노드만이 레드 노드의 부모가 될 수 있다.
• 임의의 한 노드에서 널 리프 노드까지 도달하는 모든 경로에는 널 리프 노드를 제외하고 항상 같은 수의 블랙 노드가 있다.

레드 블랙 트리 삽입은 분량이 많아서 나중에 다른 포스팅에서 별도로 다루려고 한다.

 

---

 

힙

힙(Heap)은 항상 완전 이진 트리를 띄고 있으며, 부모의 값이 항상 자식들의 값보다 크거나(Max Heap) 작아야(Min Heap) 한다. 힙 트리는 우선순위 큐(Priority Queue)를 구현하거나, 힙 정렬(Heap Sort)을 하는데 사용된다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. 최대 힙의 경우 큰 값이 상위에 있고 작은 값이 하위에 있다는 정도로 말이다.

출처 : GeeksforGeeks

당연한 이야기이지만 Min Heap은 최솟값을, Max Heap은 최댓값을 O(1)의 시간으로 찾을 수 있다. 루트 노드이기 때문이다. 그리고 데이터의 삽입과 삭제는 모두 O(logN)이 소요된다. 힙의 구조를 계속 유지하기 위해서는 삽입과 삭제 이후 heapify 과정을 거쳐야 한다. 

삽입의 경우 1. 새로운 노드가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. 2. 그리고 새로운 노드를 부모 노드와 교환해서 힙의 성질을 만족시키는 과정을 반복한다. 아래는 자바를 이용한 최대 힙의 삽입 연산이다.

/* 최대힙 삽입 */
void insert_max_heap(int x){
  maxHeap[++heapSize] = x; // 힙 크기를 하나 증가하고 마지막 노드에 x를 넣는다.

  for (int i=heapSize; i>1; i/=2) {
    // 마지막 노드가 자신의 부모 노드보다 크면 swap
    if (maxHeap[i/2] < maxHeap[i]) {
      swap(i/2, i);
    } else {
      break;
    }
  }
}

삭제의 경우 1. 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. 2. 삭제된 루트 노드에 합의 마지막 노드를 가져온다. 3. 힙을 재구성한다.(Heapify) 아래는 자바를 이용한 최대 힙의 삭제 연산이다.

/* 최대힙 삭제 */
int delete_max_heap(){
  if (heapSize == 0) // 배열이 빈 경우
    return 0;

  int item = maxHeap[1]; // 루트 노드의 값을 저장한다.
  maxHeap[1] = maxHeap[heapSize]; // 마지막 노드의 값을 루트 노드에 둔다.
  maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드를 0으로 초기화한다.

  for (int i=1; i*2<=heapSize;) {
    // 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 반복문을 나간다.
    if (maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
      break;
    }
    // 왼쪽 노드가 더 큰 경우, 왼쪽 노드와 마지막 노드를 swap
    else if (maxHeap[i*2] > maxHeap[i*2+1]) {
      swap(i, i*2);
      i = i*2;
    }
    // 오른쪽 노드가 더 큰 경우, 오른쪽 노드와 마지막 노드를 swap
    else {
      swap(i, i*2+1);
      i = i*2+1;
    }
  }
  return item;
}

 

 

참고 자료

1. https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure
2. https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)
3. <C언어로 쉽게 풀어쓴 자료구조>, 천인국 저
4. https://www.geeksforgeeks.org/heap-data-structure/
5. https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html