[Data Structure] Summary 2

Seongje kim, 30 September 2020

자료구조 요약입니다.

이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)

이진 트리는 루트 노드를 중심으로 각 노드가 최대 2개의 자식 노드를 가진다. 다시 말해, 리프 노드를 제외한 각 노드들은 최대 2개의 서브 트리(이진 트리의 특성을 만족하는)를 가진다고 표현할 수 있다.

  • 포화 이진 트리 : 모든 레벨이 꽉 찬 이진 트리
  • 완전 이진 트리 : 왼쪽에서 오른쪽으로 순서대로 노드가 채워진 이진 트리
  • 이진 트리의 인덱스(1 <= i <= N) : parent(i) = i / 2, leftChild(i) = 2 * i, rightChild(i) = (2 * i) + 1

이진 탐색 트리는 효율적인 노드 탐색을 위한 이진 트리의 활용 예이다. 단, 이진 탐색 트리는 아래의 규칙을 만족해야 한다.

  1. 각 노드에 저장된 키는 유일한 값이다.
  2. 부모 노드의 키를 기준으로 왼쪽 자식 노드는 보다 작은 값, 오른쪽 자식 노드는 보다 큰 값을 가진다.
  3. 각 서브 트리는 이진 탐색 트리의 특성을 만족한다.

만일 이진 탐색 트리가 편향되어 있지 않다면 O(logN)의 시간 복잡도를 만족하지만 저장 순서에 따라 한 쪽으로만 노드가 추가되는 경우, 선형 탐색과 동일하게 O(N)을 요구하게 된다. 이는 배열과 비교하여 더 많은 메모리를 사용했음에도 탐색 시간에 이점을 누릴 수 없게된다는 것을 알 수 있다. 때문에 이를 해결하기 위한 트리의 균형을 유지할 수 있는 AVL 트리, Red-Black 트리 등이 존재한다.

힙(Heap, Binary Heap)

힙은 완전 이진 트리의 일종으로 우선순위 큐를 구현하는데 활용된다. 노드들은 우선순위에 따라 순서를 유지하고 있고, 빠르게 최댓값 또는 최솟값을 찾을 수 있다. (우선순위에 따라 최대힙(Max Heap) 또는 최소힙(Min Heap)으로 구분된다.)

이진 탐색 트리와 비교하면 힙은 비교적 느슨한 정렬 상태를 유지하는데, 부모 노드가 자식 노드들보다 더 높은 우선순위를 가지는 상태만을 만족한다. 또한, 힙은 중복된 값을 허용하기 때문에 이진 탐색 트리와 구별된다.

결과적으로 힙의 루트 노드가 가장 높은 우선순위를 가진 노드에 해당되고 O(1)의 시간으로 원하는 최댓값 또는 최솟값을 찾을 수 있다. 하지만 루트 노드를 제거한 후에도 여전히 힙의 우선순위를 만족하기 위해 트리를 재조정해야 하는 과정이 필요하다. 그 과정을 ‘Heapify‘라고 부르며, 최대 O(logN)의 시간이 소요된다. 마찬가지로 새로운 노드를 삽입하는 경우에도 동일하게 적용된다.

  • 삽입 : 새로운 노드를 힙의 마지막 노드에 이어서 삽입 후, 해당 위치부터 우선순위를 만족하는 위치까지 부모 노드와 값을 비교하며 서로 위치를 교환하는 heapify 과정이 반복하여 이루어진다.
  • 삭제 : 삭제된 루트 노드에 힙의 마지막 노드를 넣고, 아래로 heapify 과정을 반복한다.

Red-Black 트리

앞서 말한 이진 탐색 트리의 편향 위험을 해결하기 위해 트리의 균형을 유지하는 일종의 이진 탐색 트리이다. 그러므로 탐색/삽입/삭제 시 기본적으로 이진 탐색 트리의 특성을 유지하며, 최악의 경우에도 O(logN)의 시간 복잡도를 갖는다. Red-Black 트리는 아래의 정의를 만족한다.

  1. 루트 노드는 Black
  2. 모든 리프 노드들은 Black
  3. 리프 노드를 제외한 내부 노드들에 대하여 Red 노드의 자식 노드들은 Black (즉, Red 노드가 연속되지 않는다.)
  4. 모든 리프 노드들의 Black-depth(루트 노드까지의 경로 중 Black 노드 개수)는 동일하다.

Red-Black 트리의 노드 삽입

우선 삽입되는 노드의 색깔은 Red로 지정하는데, 그 이유는 Black-depth의 변경을 최소화하기 위함이다. 새로운 Red 노드가 삽입됬을 때, 위 4가지 정의 중 위반될 수 있는 항목은 3번이다. 즉, Double Red가 발생할 가능성이 있다.

이때, Double Red 문제를 해결하는 전략이 2가지가 존재한다. 전략을 선택하는 방법은 새로 삽입된 노드를 기준으로 부모 노드의 형제인 ‘삼촌 노드’의 색깔에 따라 결정된다.

  • Restructuring (삼촌 노드가 Black)

먼저 자신, 부모, 조부모 노드들을 오름차순 정렬 후 가운데 노드는 부모, 나머지 노드들은 자식으로 지정한다. 마지막으로 부모로 지정된 노드는 Black, 나머지 자식 노드들은 Red로 치환한다. (마치 회전하는 것처럼 동작한다.) 이 과정은 해결 전/후의 Black 노드 개수에 변화가 없어서 다른 서브 트리에 영향을 주지 않기 때문에 정의를 다시 위반할 가능성이 없다. 또한, 이 과정의 자체의 시간 복잡도는 O(1)를 만족하지만 새로운 노드가 삽입되기 위한 위치를 탐색하는 시간인 O(logN)가 요구된다.

  • Recoloring (삼촌 노드가 Red)

Recoloring 전략은 부모 노드와 삼촌 노드를 Black으로 만들고 조부모 노드를 Red로 지정하는 방법이다. 부모 노드와 삼촌 노드를 둘 다 Black으로 만들기 때문에 4번 항목을 위반할 위험은 없지만 조부모 노드가 루트 노드가 아니라면 Double Red 문제는 다시 발생할 수 있다. Recoloring 과정이 일어난 특정 서브 트리의 부모 노드가 Red일 가능성이 있기 때문이다.

결국 특정 서브 트리의 Recoloring으로 인해 해당 서브 트리를 포함하는 더 큰 서브 트리에 영향을 주게 된다. 때문에 최악의 경우 루트 노드까지 반복하여 Restructuring 또는 Recoloring이 이루어지며, 탐색 시간이 포함되더라도 O(logN) 시간이 걸리게 된다.

결과적으로 삽입의 시간 복잡도는 O(logN)를 만족하고, 4번 항목으로 인해 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지된다.

Red-Black 트리의 노드 삭제

이진 탐색 트리와 동일한 방법으로 삭제되지만 해당 노드가 Black이라면 4번 항목에 의해 문제가 발생할 수 있다. 문제가 발생한 경우, Black-depth가 감소한 경로에 Black 노드 1개가 추가되도록 위치와 색깔을 조정해야 한다. 구체적인 경우의 수는 생략하고, 결과적으로 삭제의 시간 복잡도는 삽입과 동일한 O(logN)을 만족한다.

장점

또 다른 균형 트리인 AVL 트리는 Red-Black 트리보다 더 엄격한 균형을 요구하기 때문에 삽입/삭제 시 회전에 대한 비용이 더 필요하다. 또한 Red-Black 트리는 최악에 경우에도 일정한 실행 시간을 보장하기 때문에 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하다. 대표적으로 Java의 HashMap은 특정 버킷의 엔트리를 관리하기 위해 Red-Balck 트리를 활용한다.

B-트리

데이터베이스와 파일 시스템에서 널리 사용되는 균형 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리이다. 만일 노드 내 최대 데이터의 수가 M개라면 M차 B-트리라고 표현한다. M차 B-트리의 성립 조건은 아래와 같다.

  1. 각 노드는 최대 M개의 자식 노드를 가질 수 있다.
  2. 루트 노드와 리프 노드를 제외한 모든 노드는 반드시 최소 M/2개의 자식 노드를 가져야 한다.
  3. 모든 리프 노드들은 같은 레벨에 위치해야 하며, 최소 M/2 -1개의 데이터를 가져야 한다.
  4. 각 노드의 데이터들은 정렬된 상태를 유지한다.
  5. 노드 내 데이터 개수가 N개라면 자식 노드는 N+1개이다.

정리하자면 B-트리의 기본 개념은 내부 노드의 자식 노드의 수가 미리 정해진 범위 내에서 변경된다는 점에서 시작한다. 특정 노드가 삽입되거나 삭제될 때, 내부 노드는 해당 범위의 자식 노드 수를 만족하기 위해 분리되거나 다른 노드와 합쳐 재구성된다. 이렇게 자식 노드의 수가 일정 범위 내에서 유지가 된다면 트리의 균형을 맞추는 과정이 감소될 수 있다.

만일 특정 노드로의 접근 시간이 노드 내의 연산 시간에 비해 훨씬 길 경우, B-트리를 활용하면 많은 이점을 가질 수 있다. 일반적으로 대부분의 노드가 2차 저장장치(예 : 하드디스크)에 위치해 있을 경우를 말한다. 결과적으로 저장 공간에서의 손실을 감수하고 각 내부 노드가 가질 수 있는 자식 노드 개수를 최대화함으로써(각 노드가 완전한 하나의 디스크 블록을 차지하도록) 트리의 높이를 줄이고, 균형을 맞추는 과정을 감소시켜서 효율성을 높일 수 있다.

B-트리의 데이터 삽입

일반적인 이진 탐색 트리의 삽입은 하향식으로 구성되는 반면, B-트리는 상향식으로 구성된다. 즉, 삽입하려는 데이터의 위치에 해당하는 리프 노드를 탐색하여 데이터를 삽입하고 시작한다.

그다음 새로운 데이터가 삽입된 후 B-트리의 성립 조건을 만족할 때까지 노드를 분리하거나 다른 노드와 병합해야 하는데, 만일 리프 노드의 데이터가 가득 차 오버플로우가 발생된다면 M/2 -1번째 데이터를 부모로 올리고 노드를 분리한다. 이후 분리한 서브 트리가 B-트리 조건에 맞지 않는다면 부모 노드로 올려 병합한다.

B-트리의 데이터 삭제

B-트리의 삭제 연산은 항상 리프 노드에서 이루어진다. 만일 삭제하려는 노드가 내부 노드라면 해당 노드를 리프 노드로 이동시켜야 한다.

  • CASE 1 : 내부 노드의 데이터를 삭제하는 경우

삭제하려는 데이터가 내부 노드에 위치한 경우 대체키를 찾아야하는데, 이는 왼쪽 서브 트리의 최댓값 또는 오른쪽 서브 트리의 최솟값이다. 결과적으로 리프 노드의 삭제 연산을 수행하면 된다.

  • CASE 2 : 리프 노드의 데이터를 삭제하는 경우

우선 해당 데이터를 삭제하여도 B-트리의 조건을 위배하지 않는다면(언더 플로우가 발생하지 않음) 그대로 종료된다. 하지만 언더 플로우가 발생한다면 이를 해결하기 위해 2가지의 방법이 사용된다.

  1. 재분배 : 형제 노드가 보유한 데이터의 수가 재분배 이후 최소 개수를 유지할 수 있는 경우, 형제 노드에서 빌린다. 형제 노드가 왼쪽인 경우 최댓값을, 오른쪽인 경우 최솟값이 대상이 되며 해당 값을 부모 노드의 값으로 치환한다. 그다음 원래의 값을 언더 플로우가 발생한 노드에게 빌려줌으로써 문제를 해결한다.

  2. 병합 : 재분배가 불가능할 경우, 형제 노드와의 병합을 통해 문제를 해결한다. 이때, 부모 노드의 값까지 포함하며 병합 이후 부모 노드에서 다시 언더 플로우가 발생할 수 있다. 때문에 B-트리의 조건을 만족할때까지 재귀적으로 재분배 또는 병합의 방법을 사용한다.