6장 탐색

• 데이터를 찾아서

  컴퓨터에서의 탐색이란 '데이터'를 찾는다라는 의미

  각각의 자료구조(배열,링크드리스트,트리 등등)에서 탐색의 방법이 다를 수 있다

• 순차 탐색

  순차 탐색(Sequential Search)은 데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘이다.

  정렬되어 있지 않은 데이터 집합에서 원하는 데이터를 찾을 수 있는 유일한 방법이고 구현이 간단해 버그를 만들 가능성이 적다는 장점이 있다.

  자기 구성 순차 탐색

  자주 사용되는 항목을 데이터 집합의 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법이다. 자주 사용되는 항목을 어떻게 선별하는가에 따라 세 가지 방법으로 나뉜다.

  • 전진 이동법(Move To Front)

    전진 이동법은 어느 항목이 한 번 탐색되고 나면 그 항목을 데이터 집합의 가장 앞에 위치시키는 방법이다.

    

    한번 탐색된 항목이 이어서 다시 검색될 가능성이 높은 데이터 집합에서만 사용해야 한다.

    • 링크드 리스트에 사용 가능한 전진 이동 순차 탐색법

      NODE* SSL_moveToFront(NODE** head, int taget)

      {

      NODE* current = (*head);

      NODE* previous = NULL;

      NODE* match = NULL;

         

      while( current != NULL )

      {

      if( current->data == target )

      {

      match = current;

      if( previous != NULL )

      {

      // 자신의 앞 노드와 다음 노드 연결

      previous->next = current->next;

         

      // 자신을 리스트의 가장 앞으로 옮기기

      current->next = (*head);

      (*head) = current;

      }

      break;

      }

      else

      {

      previous = current;

      current = current->next;

      }

      }

      return match;

      }

  • 전위법(Transpos)

    탐색된 항목을 바로 이전 항목과 교환

    

    전진 이동법은 탐색된 항목을 무조건 앞으로 옮기는데 반해, 전위법은 '자주' 탐색된 항목을 점진적으로 앞으로 옮긴다

    • 리스트로 구현한 전위법

      NODE* SLL_transpose(NODE** head, int target)

      {

      NODE* current = (*head);

      NODE* prevprev = NULL; // 이전노드의 이전

      NODE* prev = NULL; // 이전 노드

      NODE* match = NULL;

         

      while( current != NULL )

      {

      if( current->data == target )

      {

      match = current;

      if( prev != NULL )

      {

      if( prevprev != NULL )

      prevprev->next = current;

      else

      (*head) = current;

         

      prev->next = current->next;

      current->next = prev;

      }

      break;

      }

      else

      {

      if( prev != NULL )

      prevprev = prev;

      prev = current;

      current = current->next;

      }

      }

      return match;

      }

  • 빈도 계수법(Frequency Count)

    계수법은 데이터 집합 내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장해 두고, 탐색된 횟수가 높은 순으로 데이터 집합을 재구성하는 전략의 알고리즘이다.

• 이진 탐색

  탐색 익스프레스: 이진 탐색

  이진 탐색(Binary Search)은 정렬된 데이터 집합에서 사용할 수 있는 '고속' 탐색 알고리즘이다. 이진 탐색의 핵심은 탐색 범위를 1/2씩 줄여나가는 방식이다.

  • 이진 탐색 과정
    • 데이터 집합의 중앙에 있는 요소를 선택
    • 중앙 요소의 값과 찾고자 하는 목표 값을 비교
    • 목표 값이 중앙 요소의 값보다 작으면 중앙을 기준으로 데이터 집합의 왼편에 대해 새로 검색을 수행하고 크다면 오른편에 대해 이진 탐색을 수행
    • 찾고자 하는 값을 찾을 때까지 1~3을 반복

  이진 탐색의 성능 측정

  

  

  

  

  이진 탐색의 구현

  데이터 집합, 데이터 집합의 크기, 목표값을 매개변수로 받는다

  ElementType binarySearch(ElementType dataSet[], int size, ElementType target)

  {

  int left, right, mid;

     

  left = 0;

  right = size - 1;

     

  while( left <= right )

  {

  // 중앙 요소 위치 계산

  mid = (left + right) / 2;

  // 중앙 요소가 담고 있는 값과 목표 값이 일치하면 해당 요소 반환

  if( target == dataSet[mid] )

  return dataSet[mid];

  else if( target > dataSet[mid] )

  left = mid+1;

  else

  right = mid - 1;

  }

  return NULL;

  }

  C 표준 라이브러리의 이진 탐색 함수 : bsearch()

  • bsearch 함수 원형

    void* bsearch(

    const void *key, /* 찾고자 하는 목표 값 데이터의 주소 */

    const void *base, /* 데이터 집합 배열의 주소*/

    size_t num, /* 데이터 요소의 개수*/

    size_t width, /* 한 데이터 요소의 크기*/

    int (__cdecl *compare)(const void*, const void*) /* 비교 함수 포인터*/

    );

  • 예제 BinarySearch2.c

#include <stdlib.h> #include <stdio.h>     int compareScore(const void* _elem1, const void* _elem2) { int* elem1 = (int*)_elem1; int* elem2 = (int*)_elem2;     if( *elem1 > *elem2 ) return 1; else if ( *elem1 < *elem2 ) return -1; return 0; }     void main() { int dataSet[] = { 6,2,3,4,1,5,7,9,10,8 }; int length = sizeof(dataSet) / sizeof(dataSet[0]); int target; int* found = NULL;     qsort( (void*)dataSet, length, sizeof(int), compareScore);     target =10;     found = (int*)bsearch( (void*)&target, (void*)dataSet, length, sizeof(int), compareScore);     printf("founc : %d \n", *found); }

• 이진 탐색 트리

  이진 탐색을 위한 이진 트리

  이진 탐색 트리(Binary Search Tree)는 '이진 탐색'을 위한 트리이자, 탐색을 위한 '이진 트리'이다.

  이진 탐색은 사전에 정의된 크기의 데이터 집합에 대해서만 사용이 가능하고, 동적으로 그 크기가 달라지는 데이터 집합에는 적용이 불가능하다. 이 문제를 이진 탐색 트리로 해결할 수 있다.

  이진 탐색 트리는 어떻게 생겼을까?

  왼쪽 자식 노드는 자신보다 작고 오른쪽 자식 노드는 크다.

  

  이진 탐색 트리의 기본 연산

  • 이진 탐색 트리에서의 이진 탐색

    

    위의 이진 트리에서 67을 찾고자 한다

    

    67은 23보다 크기 때문에 오른쪽 자식 노드에 데이터가 있을 것이다.

    

    67은 139보다 작기 때문에 왼쪽 자식에 값이 있을 것이다.

    

    BSTNode* BST_searchNode(BSTNode* tree, ElementType target)

    {

    if( tree == NULL )

    return NULL;

       

    if( tree->data < target)

    // target이 현재 노드보다 크면

    return BST_searchNode(tree->left, target);

    else if( tree->data > target )

    // target이 현재 노드보다 작으면

    return BST_searchNode(tree->right, target);

    else

    // 현재 값이 노드와 같으면

    return tree;

  • 이진 탐색 트리의 노드 삽입

    이진 탐색 트리에서의 노드 삽입 연산은 "어디에 삽입할 것인가"를 찾아내는 것이 핵심이다.

    

    위의 트리에 14를 삽입한다고 생각해보면 23보다 작으므로 왼쪽 자식 노드에 삽입될 것이다. 그리고 11보다는 크므로 11의 오른쪽 자식 노드에 연결하면 된다.

    

    void BST_insertNode( BSTNode** tree, BSTNode* child)

    {

    // 새노드가 현재 노드보다 크면

    if( (*tree)->data < child->data )

    {

    if( (*tree)->right == NULL )

    (*tree)->right = child;

    else

    BST_insertNode( &(*tree)->right, child);

    }

    // 새 노드가 현재 노드보다 작으면

    else if( (*tree)->data > child->data)

    {

    if( (*tree)->left == NULL )

    (*tree)->left = child;

    else

    BST_insertNode( &(*tree)->left, child);

    }

    }

  • 이진 탐색 트리의 노드 삭제

    찾는 데이터 노드의 자식이 없으면 찾는 노드를 지우고 NULL로 데이터를 채우면 된다.

    

    자식이 있는 경우에는 두 가지 경우로 나뉜다

    • 왼쪽/오른쪽 중 하나의 자식 노드만 갖고 있는 경우

      

      지우고자하는 노드가 한쪽 자식만 가지고 있다면 해당 노드를 지우고 부모 노드에 연결시키면 된다.

    • 양쪽 자식 노드를 모두 가지고 있는 경우

      

      삭제된 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드를 삭제된 노드의 위치에 옮겨 놓아야 이진 탐색 트리의 기능을 유지할 수 있다.

      

      옮겨 놓는 '최소값 노드'가 자식이 없는 경우라면 이렇게 작업이 완료된다

      자식이 있는 경우라면 최소값 노드는 자식이 있더라도 오른쪽 자식만 있다. 이 경우 최소값 노드의 오른쪽 자식은 최소값 노드의 원래 부모에게 연결해주면 삭제 작업이 끝난다.

      

      BSTNode* BST_removeNode( BSTNode* tree, BSTNode* parent, ElementType target)

      {

      BSTNode* remove = NULL;

         

      if( tree == NULL )

      return NULL;

         

      if( tree->data > target )

      remove = BST_removeNode(tree->leftt, tree, target);

      else fi( tree->data < target )

      remove = BST_removeNode(tree->right, tree, target);

      // 목표 값 찾음

      else

      {

      remove = tree;

         

      // 잎 노드인 경우 바로 삭제

      if( tree->left == NULL && tree->right == NULL )

      {

      if( parent->left == tree )

      parent->left = NULL;

      else

      parent->right = NULL;

      }

      else

      {

      // 자식이 양쪽 다 있는 경우

      if( tree->left != NULL && tree->right != NULL )

      {

      // 최소값 노드를 찾아 제거한 뒤 현재 노드의 위치시킨다

      BSTNode* minNode = BST_searchMinNode(tree->right);

      // minNode에 대해 제거 후 뒤처리

      minNode = BST_removeNode( tree, NULL, minNode->data);

      tree->data = minNode->data;

      }

      else

      {

      // 자식이 하나인 경우

      BSTNode* temp = NULL;

      if( tree->left != NULL )

      temp = tree->left;

      else

      temp = tree->right;

         

      if( parent->left == tree )

      parent->left = temp;

      else

      parent->right = temp;

      }

      }

      }

      return remove;

      }

  이진 탐색 트리 예제 프로그램

  • 예제 BinarySearchTree.h

#ifndef BINARY_SEARCH_TREE_H__ #define BINARY_SEARCH_TREE_H__     #include <stdio.h> #include <stdlib.h>     typedef int ElementType; typedef struct tagBSTNODE { tagBSTNODE* left; tagBSTNODE* right; ElementType data; }NODE;     NODE* BST_createNode(ElementType data); void BST_destroyNode(NODE* node); void BST_destroyTree(NODE* tree);     NODE* BST_searchNode(NODE* tree, ElementType target); NODE* BST_searchMinNode(NODE* tree); void BST_insertNode(NODE* tree, NODE* child); NODE* BST_removeNode(NODE* tree, NODE* parent, ElementType target); void BST_inorderPrintTree(NODE* node);     #endif

• 예제 BinarySearchTree.c

#include "BinarySearchTree.h"     NODE* BST_createNode(ElementType data) { NODE* newNode = (NODE*)malloc(sizeof(NODE)); newNode->left = NULL; newNode->right = NULL; newNode->data = data;     return newNode; } void BST_destroyNode(NODE* node) { free(node); } void BST_destroyTree(NODE* tree) { if( tree->right != NULL ) { BST_destroyTree(tree->right); } if( tree->left != NULL ) { BST_destroyTree(tree->left); }     tree->left = NULL; tree->right = NULL;     BST_destroyNode(tree); }     NODE* BST_searchNode(NODE* tree, ElementType target) { if( tree == NULL ) return NULL;     if( tree->data < target ) { return BST_searchNode(tree->right, target); } else if( tree->data > target ) { return BST_searchNode(tree->left, target); } else { return tree; } } NODE* BST_searchMinNode(NODE* tree) { if( tree == NULL ) return NULL;     if( tree->left == NULL ) return tree; else return BST_searchMinNode(tree->left); } void BST_insertNode(NODE* tree, NODE* child) { if( tree->data < child->data ) { if( tree->right == NULL ) tree->right = child; else BST_insertNode(tree->right, child); } else if( tree->data > child->data ) { if( tree->left == NULL ) tree->left = child; else BST_insertNode(tree->left, child); } } NODE* BST_removeNode(NODE* tree, NODE* parent, ElementType target) { NODE* remove = NULL;     if( tree == NULL ) return NULL;     if( tree->data > target ) remove = BST_removeNode(tree->left, tree, target); else if( tree->data < target ) remove = BST_removeNode(tree->right, tree, target); // 목표값을 찾은 경우 else { remove = tree;     // 잎노드이면 바로 삭제 if( tree->left == NULL && tree->right == NULL ) { if( parent->left == tree ) parent->left = NULL; else parent->right = NULL; } else { // 자식이 양쪽 다 있는 경우 if( tree->left != NULL && tree->right ) { // 최소값 노드를 찾아 제거하고 현재의 노드에 위치시킴 NODE* minNode = BST_searchMinNode(tree->right); minNode = BST_removeNode(tree, NULL, minNode->data); tree->data = minNode->data; } // 자식이 하나인 경우 else { NODE* temp = NULL; if( tree->left != NULL ) temp = tree->left; else temp = tree->right;     if( parent->left == tree ) parent->left = temp; else parent->right = temp; } } } return remove; }     void BST_inorderPrintTree(NODE* node) { if( node == NULL ) return;     // 왼족 하위 트리 출력 BST_inorderPrintTree(node->left);     // 루트 노드 출력 printf("%d ", node->data);     // 오른쪽 하위 트리 출력 BST_inorderPrintTree(node->right); }

• 예제 main.c

#include "BinarySearchTree.h"     void main(void) { // 노드 생성 NODE* tree = BST_createNode(123); NODE* node = NULL;     // 트리에 노드 추가 BST_insertNode(tree, BST_createNode(22)); BST_insertNode(tree, BST_createNode(9918)); BST_insertNode(tree, BST_createNode(424)); BST_insertNode(tree, BST_createNode(17)); BST_insertNode(tree, BST_createNode(3));     BST_insertNode(tree, BST_createNode(98)); BST_insertNode(tree, BST_createNode(34));     BST_insertNode(tree, BST_createNode(760)); BST_insertNode(tree, BST_createNode(317)); BST_insertNode(tree, BST_createNode(1));     // 트리 출력 BST_inorderPrintTree(tree); printf("\n");     // 특정 노드 삭제 printf("removing 98\n");     node = BST_removeNode(tree, NULL, 98); BST_destroyNode(node);     // 트리 출력 BST_inorderPrintTree(tree); printf("\n");     // 새 노드 삽입 printf("inserting 111\n"); BST_insertNode(tree, BST_createNode(111));     // 트리 출력 BST_inorderPrintTree(tree); printf("\n");     // 트리 소멸 BST_destroyTree(tree); }

뒤늦게 생각해보는 이진 탐색 트리의 문제점

다음 그림처럼 이진 탐색 트리가 가형적으로 성장해서 검색의 효율을 극단적으로 떨어뜨리는 것이다.

다음에 배우는 '레드 블랙 트리'가 이 문제를 해결해 줄 것이다.

• 레드 블랙 트리

  레드 블랙 트리(Red Black Tree)는 이진 탐색 트리이다.

  레드 블랙 트리는 노드를 빨간색 또는 검은색으로 표시한다는 정도가 이진 탐색 트리와 다르다. 레드 블랙 트리에서 노드의 색은 트리 전체의 균형을 유지할 수 있게 하는 중요한 비결이다.

  • 레드 블랙 트리의 노드

    typedef struct tagRBTNode

    {

    tagRBTNode* parent;

    tagRBTNode* left;

    tagRBTNode* right;

    enum { RED, BLACK } color;

    ElementType data;

    }NODE;

  레드 블랙 트리가 균현을 유지하는 비결

  • 모든 노드는 빨간색 아니면 검은색이다
  • 루트 노드는 검은색이다
  • 잎 노드는 검은색이다
  • 빨간 노드의 자식들은 모두 검은색이다. 하지만 검은색 노드의 자식이 빨간색일 필요는 없다.
  • 루트 노드에서 시작해 잎 노드 사이에 있는 모든 경로의 검은색 노드 수는 모두 동일하다

    

  레드 블랙 트리의 기본 연산

  노드를 삽입하거나 삭제할 때 레드 블랙 트리의 규칙이 무너지기 때문에 이 규칙을 바로 잡아주는 것이 레드 블랙 트리 구현의 핵심이다.

  • 회전

    회전은 부모-자식 노드의 위치를 서로 바꾸는 연산이다. 회전의 방향에 따라 우회전(Right-Rotate)과 좌회전(Left-Rotate)으로 나뉜다.

    

    회전을 할 때 다음과 같이 자식 노드를 처리해줘야 한다.

    • 우회전을 할 때는 왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 연결한다.(왼쪽 그림) 이 트리를 우회전하고 나니 노드 6이 노드 8의 왼쪽 자식으로 왔다.
    • 좌회전을 할 때에는 오른쪽 자식 노드의 왼쪽 자식 노드를 부모 노드의 오른쪽 자식으로 연결한다.(오른쪽 그림) 이 트리를 좌회전해서 노드 6이 다시 노드 5의 오른쪽 자식이 되었다.

      void RBT_rotateRight(NODE** root, NODE* parent)

      {

      NODE* leftChild = parent->left;

      // 왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 이동

      parent->left =leftChild->right;

         

      if( leftChild->right != Nil )

      leftChild->right->parent = parent;

         

      leftChild->parent = parent->parent;

         

      // 부모가 NULL이면 이 노드는 root

      // 이 경우에는 왼쪽 자식을 root 노드로 만들어 회전

      if( parent->parent == NULL )

      (*root) = leftChild;

      else

      {

      // 왼쪽 자식 노드를 부모 노드가 있는 곳에 위치

      if( parent == parent->parent->left )

      parent->parent->left = leftChild;

      else

      parent->parent->right = leftChild;

      }

      leftChild->right = parent;

      parent->parent = leftChild;

      }

  • 레드 블랙 트리의 노드 삽입

    이진 탐색을 통해 삽입할 장소(노드)를 찾아 여기에 새 노드를 자식 노드로 연결한다는 점에서 레드블랙트리와 이진탐색트리의 노드 삽입 연산은 비슷하다. 레드블랙트리는 노드 삽입 때문에 무너졌을지 모르는 규칙들을 살펴봐야 한다.

    레드 블랙 트리에 새 노드가 삽입되고 나면 이 노드를 빨간색으로 칠한 다음 양쪽 자식에 NIL노드를 연결해야 한다.

    void RBT_insertNode(NODE** tree, NODE* newNode)

    {

    // 이진 탐색 트리의 노드 삽입을 수행

    RBT_insertNodeHelper(tree, newNode);

       

    // 새 노드를 빨간색으로 칠하고 양쪽 자식에 Nil을 연결

    newNode->color = RED;

    newNode->left = Nil;

    newNode->right = Nil;

       

    // 무너진 레드 블랙 트리 규칙을 바로 잡기

    RBT_rebuildAfterInsert(tree, newNode);

    }

    Nil노드를 잎 노드당 두 개씩 할당해서 사용하는 것은 낭비이기 때문에 Nil노드를 한 개만 전역으로 생성해서 새 노드를 생성할 때마다 동일한 Nil 노드를 사용한다.

    

    새 노드를 이진 탐색을 통해 삽입하고 빨간색으로 칠한 다음 양쪽 자식에 NIL 노드까지 연결했다. 이제 레드 블랙 트리의 규칙이 안전한지 확인하고 이를 복구하는 작업을 해야 한다.

    • 모든 노드는 빨간색 아니면 검은색이다.
    • 루트 노드는 검은색이다.
    • 잎 노드는 검은색이다.
    • 빨간 노드의 자식들은 모두 검은색이다.
    • 루트 노드와 잎 노드 사이에 있는 검은색 노드의 수는 경로마다 동일하다.

    1번은 절대 위반되지 않는다.

    3번도 NIL노드로 연결했으므로 절대 위반되지 않는다.

    5번도 새 노드(빨간색)를 삽입할 때는 부모 노드에 연결되어 있던 NIL노드(검은색)를 떼어내고 그 자리에 연결하기 때문에 규칙이 무너지지 않는다.

    그럼 2, 4번을 확인해보아야 한다.

    2번의 경우 루트 노드를 검은색으로 칠하면 되기때문에 뒤처리가 간단하다.

    4번의 경우 이 규칙이 위반되었다는 것은 삽입한 노드와 부모 노드의 색이 모두 빨간색이라는 의미이다. 이 상황은 삽입한 노드의 삼촌, 즉 부모 노드의 형제 노드가 어떤 색이냐에 따라 그 경우가 세가지로 나뉜다.

    • 삼촌도 빨간색인 경우

      삼촌도 빨간색인 경우에는 부모 노드와 삼촌 노드를 검은색으로 칠하고, 할아버지를 빨간색으로 칠한다.

      

      삼촌이 빨간색인 경우에 후속처리는 끝났지만 이 작으로 인해 생긴 부작용이 없는지 봐야한다. 그래서 할아버지 노드를 새로 삽입한 노드로 간주하고 다시 처음부터 4번 규칙을 위반하는 세 가지 경우를 따져봐야 한다. 이렇게 위로 올라가면서 부모 노드가 검은색이거나 새로 삽입한(도는 새로 삽인한 것으로 간주한) 노드가 루트여야 끝이 난다.

    • 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우

      삼촌이 검은색이고 삽입한 노드가 부모 노드의 오른쪽 자식인 경우에는 부모 노드를 왼쪽으로 회전시켜 이 상황을 세 번째 경우의 문제로 바꾼다.

      

      문제가 세 번째 경우로 바뀌면서 새로 삽입한 노드 D가 부모가 되고 부모 노드였던 B가 자식이 되었다.

      첫 번째 경우를 처리한 다음에 할아버지 노드를 새로 삽입한 노드로 간주했던 것처럼, 이번에는 부모였던 노드를 새로 삽인한 노드로 간주시키고 세 번째 경우의 문제로 현재 상황을 넘긴다.

    • 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우

      부모 노드를 검은색, 할아버지 노드를 빨간색으로 칠한 다음 할아버지 노드를 오른쪽으로 회전 시킨다.

      

      세 번째 경우를 처리하고 난 다음에는 4번 규칙이 위반되지 않는다. 새로 삽입한 노드 B의 부모 D가 검은색이기 때문이다. D에게 부모가 있다고 간주해 보아도 그 부모 노드의 색이 빨간색이어도 검은색이어도 4번 규칙은 위반되지 않는다.

      void RBT_rebuildAfterInsert(NODE** root, NODE* x)

      {

      // 4번 규칙을 위반하고 있는 동안 계속 반복

      while( x != (*root) && x->parent->color == RED )

      {

      // 부모 노드가 할아버지 노드의 왼족 자식인 경우

      if( x->parent == x->parent->parent->left )

      {

      NODE* uncle = x->parent->parent->right;

      // 삼촌이 빨간색인 경우

      if( uncle->color == RED )

      {

      x->parent->color = BLACK;

      uncle->color = BLACK;

      x->parent->parent->color = RED;

         

      x = x->parent->parent;

      }

      else

      {

      // 삼촌이 검은색이고 x가 오른쪽 자식일 때

      if( x == x->parent->right )

      {

      x = x->parent;

      RBT_rotateLeft(root, x);

      }

         

      x->parent->color = BLACK;

      x->parent->parent->color = RED;

      RBT_rotateRight(root, x->parent->parent);

      }

      }

      else

      {

      // 부모가 할아버지의 오른쪽 자식인 경우

      // 왼쪽 자식인 경우의 코드에서 좌우만 바꾸면 된다.

      }

      }

      // 루트 노드는 반드시 검은색이어야 한다.

      (*root)->color = BLACK;

      }

  • 레드 블랙 트리의 노드 삭제

    이진 탐색 트리는 어느 한 노드가 삭제되었을 때 왼쪽 자식 노드는 부모 노드보다 작아야 하고 오른쪽 자식 노드는 부모 노드보다 커야 한다는 규칙이 무너지는 것을 막기 위한 처리를 해야 한다. 레드 블랙 트리의 노드 삭제 연산은 이진 탐색 트리의 삭제 연산을 그대로 사용하다. 삭제를 하고나서 레드 블랙 트리의 규칙이 무너졌는지 알아보고 무너졌으면 다시 잡아 주어야 한다.

    빨간색 노드를 삭제한다고 해서 다른 노드의 색이 바뀌는 일은 없다.(1번 규칙 유지) 루트 노드나 잎 노드는 원래 검은색이니 이들은 빨간색 노드를 삭제하는 경우에 해당하지 않는다.(2, 3번 규칙 유지) 빨간 노드의 부모와 자식들은 원래 검은색이니 4번 규칙도 유지 된다. 마지막으로 루트 노드-잎 사이의 경로 위에 있는 검은색 노드를 셀 때 원래부터 빨간색 노드는 포함되지 않으므로 빨간색 노드를 삭제해도 5번 규칙이 유지된다.

    한마디로 "삭제한 노드가 빨간색인 경우에는 뒷처리가 필요 없다" 물론 이진 탐색 트리로서의 뒤처리는 해줘야 한다.

    검은색 노드를 삭제하면 5번 규칙이 가장 먼저 무너져 내린다. 삭제한 노드의 부모와 삭제 노드의 자식이 모두 빨간색인 경우에는 4번 규칙도 위반 된다. 1,2,3번 규칙은 안전하게 지켜진다.

    

    무너진 4, 5번 규칙을 한번에 보완할 수 있는 방법이 있다. 바로 삭제된 노드를 대체하는 노드를 검은색으로 칠하는 것이다.

    

    그럼 C노드가 검은색이었다면 5번 규칙을 위반하게 된다. 이 경우에는 대체 노드 C에 검은색으르 덧입힌다. 그래서 C노드는 예외적으로 검은색을 '두 개' 가지게 되고 5번 규칙을 복원한다. 이렇게 검은색을 2개 가지는 노드를 '이중 흑색'노드라고 부른다.

    

    무너진 규칙은 이제 5번이 아니라 1번으로 바뀌었다. C노드는 검은색도 빨간색도 아닌 '이중흑색'이 되어버렸기 때문이다. 검은색을 2개 가졌다는 것은 어디까지나 개념적인 표현이다. 다시 말해, 이중 흑색은 실제로는 5번 규칙이 무너졌지만 1번 규칙이 무너진 것으로 간주함으로써 문제를 더 쉬운 상태로 만들기 위한 도구인 것이다. 따라서 실제 코드에서는 노드를 이중흑색으로 표시하거나 하는 일은 없을 것이다.

    이중흑색 노드를 처리하는 방법은 이중흑색 노드의 형제(Sibling)와 조카들의 상태에 따라 모두 네 가지 경우로 나뉜다.

    • 형제가 빨간색인 경우

      이중흑색 노드의 형제가 빨간색인 경우에는 먼저 형제를 검은색, 부모를 빨간색으로 칠한다. 그 다음에 부모를 기준으로 좌회전하고 이중흑색 노드를 검은색으로 칠하면 뒤처리가 끝난다. 아래 그림은 오른쪽 자식일 경우에 대해 설명하고 있다. 왼쪽 자식인 경우에는 그림의 좌우를 반전시켜 연산하면 된다.

      

    • 형제가 검은색이고 형제의 양쪽 자식이 모두 검은색인 경우

      이중 흑색 노드의 형제가 검은색이고 형제의 양쪽 자식(조카 노드)이 모두 검은색인 경우에는 형제 노드만 빨간색으로 칠한 다음, 이중 흑색 노드가 갖고 있던 두 개의 검은색 중 하나를 부모 노드에게 넘겨주면 된다. 부모노드도 부모 노드의 형제의 상황에 따라 대처하면 된다. 즉, 우리가 지금 다루고 있는 네 가지 경우 중에 어떤 경우에 해당되는지를 따져서 그에 맞게 처리해야 한다.

      

    • 형제가 검은색이고 형제의 왼쪽 자식이 빨간색, 오른쪽 자식이 검은색인 경우

      이 경우에는 형제 노드를 빨간색으로 칠하고 왼쪽 자식을 검은색으로 칠한 다음, 형제 노드를 기준으로 우회전을 수행한다.

      

    • 형제가 검은색이고 형제의 오른쪽 자식이 빨간색인 경우

      이 경우에는 가장 먼저 이중흑색 노드의 부모 노드가 갖고 있는 색을 형제 노드에 칠한다. 그 다음에 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 칠하고 부모 노드를 기준으로 좌회전하면 1번 규칙이 복원된다.

      

  레드 블랙 트리 예제 프로그램

  이번 예제는 사용자가 입력하는 명령에 따라 동작한다. 명령어의 종류는 노드 생성, 노드 삭제, 노드 탐색, 트리 출력, 종료가 있다.

  • 예제 RedBlackTree.h

#ifndef REDBLACKTREE_H__ #define REDBLACKTREE_H__     #include <stdio.h> #include <stdlib.h>     typedef int ElementType; typedef enum { RED, BLACK } Color;     typedef struct tagRBTNode { tagRBTNode* parent; tagRBTNode* left; tagRBTNode* right;     Color color;         ElementType data; }NODE;     void RBT_destroyTree(NODE* tree); NODE* RBT_createNode(ElementType data); void RBT_destroyNode(NODE* node);     NODE* RBT_searchNode(NODE* tree, ElementType data); NODE* RBT_searchMinNode(NODE* tree); void RBT_insertNode(NODE** tree, NODE* newNode); void RBT_insertNodeHelper(NODE** tree, NODE* newNode); NODE* RBT_removeNode(NODE** root, ElementType data); void RBT_rebuildAfterInsert(NODE** tree, NODE* x); void RBT_rebuildAfterRemove(NODE** root, NODE* x);     void RBT_printTree(NODE* node, int depth, int blackCount); void RBT_rotateLeft(NODE** root, NODE* parent); void RBT_rotateRight(NODE** root, NODE* parent);     #endif

• 예제 RedBlackTree.c

#include "RedBlackTree.h"     extern NODE* Nil;     NODE* RBT_createNode(ElementType data) { NODE* newNode = (NODE*)malloc(sizeof(NODE)); newNode->parent = NULL; newNode->left = NULL; newNode->right = NULL; newNode->data = data; newNode->color = BLACK;     return newNode; }     void RBT_destroyNode(NODE* node) { free(node); }     void RBT_destroyTree(NODE* tree) { if( tree->right != Nil ) RBT_destroyTree(tree->right);     if( tree->left != Nil ) RBT_destroyTree(tree->left);     tree->left = Nil; tree->right = Nil;     RBT_destroyNode(tree); }     NODE* RBT_searchNode(NODE* tree, ElementType data) { if( tree == Nil ) return NULL;     if( tree->data > data ) return RBT_searchNode(tree->left, data); else if(tree->data < data) return RBT_searchNode(tree->right, data); else return tree; } NODE* RBT_searchMinNode(NODE* tree) { // 데이터가 없으면 if(tree == Nil) return Nil;     // 트리에 왼쪽에 작은값이 있으므로 왼쪽에서만 찾기 if( tree->left == Nil ) return tree; else return RBT_searchMinNode(tree->left); } void RBT_insertNode(NODE** tree, NODE* newNode) { RBT_insertNodeHelper(tree, newNode);     newNode->color = RED; newNode->left = Nil; newNode->right = Nil;     RBT_rebuildAfterInsert(tree, newNode); }     void RBT_insertNodeHelper(NODE** tree, NODE* newNode) { // root가 널이면 if ( (*tree) == NULL ) (*tree) = newNode;     // root->data가 작으면 오른쪽으로 삽입 if( (*tree)->data < newNode->data ) { if( (*tree)->right == Nil ) { (*tree)->right = newNode; newNode->parent = (*tree); } else RBT_insertNodeHelper( &(*tree)->right, newNode ); } // root->data 크면 왼쪽에 삽입 else if( (*tree)->data > newNode->data ) { if ((*tree)->left == Nil) { (*tree)->left = newNode; newNode->parent = (*tree); } else RBT_insertNodeHelper( &(*tree)->left, newNode); } } void RBT_rotateRight(NODE** root, NODE* parent) { // 왼쪽 자식 노드 NODE* leftChild = parent->left;     // 왼쪽 자식노드의 오른쪽 자식 노드 parent->left = leftChild->right;     if( leftChild->right != Nil ) leftChild->right->parent = parent;     leftChild->parent = parent->parent;     if( parent->parent == NULL ) (*root) = leftChild; else { if( parent == parent->parent->left ) parent->parent->left = leftChild; else parent->parent->right = leftChild; }     leftChild->right = parent; parent->parent = leftChild; } void RBT_rotateLeft(NODE** root, NODE* parent) { NODE* rightChild = parent->right;     parent->right = rightChild->left;     if( rightChild->left != Nil ) rightChild->left->parent = parent;     rightChild->parent = parent->parent;     if( parent->parent == NULL ) (*root) = rightChild; else { if( parent == parent->parent->left ) parent->parent->left = rightChild; else parent->parent->right = rightChild; }     rightChild->left = parent; parent->parent = rightChild; }     void RBT_rebuildAfterInsert(NODE** tree, NODE* x) { // 새로운 노드가 루트가 아니고 // 새로운 노드의 부모가 RED이면 while( x != (*tree) && x->parent->color == RED ) { // 새로운 노드의 부모가 할아버지의 왼쪽이면 if( x->parent == x->parent->parent->left ) { // 삼촌은 할아버지의 오른쪽 노드 NODE* uncle = x->parent->parent->right; // 삼촌이 RED이면 if( uncle->color == RED ) { x->parent->color = BLACK; uncle->color = BLACK; x->parent->parent->color = RED;     x = x->parent->parent; } // 삼촌이 BLACK이면 else { // 새 노드가 오른쪽 노드이면 if( x == x->parent->right ) { x = x->parent; RBT_rotateLeft(tree, x); }     x->parent->color = BLACK; x->parent->parent->color = RED;     RBT_rotateRight(tree, x->parent->parent); } } // 새로운 노드의 부모가 할아버지의 오른쪽이면 else { // 삼촌은 할아버지의 왼쪽 노드 NODE* uncle = x->parent->parent->left; // 삼촌이 RED이면 if( uncle->color == RED ) { x->parent->color = BLACK; uncle->color = BLACK; x->parent->parent->color = RED;     x = x->parent->parent; } // 삼촌이 BLACK이면 else { // x가 왼쪽 노드이면 if( x == x->parent->left ) { x = x->parent; RBT_rotateRight(tree, x); }     x->parent->color = BLACK; x->parent->parent->color = RED; RBT_rotateLeft(tree, x->parent->parent); } } } (*tree)->color = BLACK; }     NODE* RBT_removeNode(NODE** root, ElementType data) { NODE* removed = NULL; NODE* successor = NULL; NODE* target = RBT_searchNode( (*root), data );     if ( target == NULL ) return NULL;     if( target->left == Nil || target->right == Nil ) { removed = target; } else { removed = RBT_searchMinNode( target->right ); target->data = removed->data; }     if(removed->left != Nil) successor = removed->left; else successor = removed->right;     successor->parent = removed->parent;     if(removed->parent == NULL) (*root) = successor; else { if(removed == removed->parent->left) removed->parent->left = successor; else removed->parent->right = successor; }     if(removed->color == BLACK) RBT_rebuildAfterRemove(root, successor);     return removed; }     void RBT_rebuildAfterRemove(NODE** root, NODE* x) { NODE* sibling = NULL;     while( x->parent != NULL && x->color == BLACK ) { if(x == x->parent->left) { sibling = x->parent->right;     if(sibling->color == RED) { sibling->color = BLACK; x->parent->color = RED; RBT_rotateLeft(root, x->parent); sibling = x->parent->right; } else { if(sibling->left->color == BLACK && sibling->right->color == BLACK) { sibling->color = RED; x = x->parent; } else { if(sibling->left->color == RED) { sibling->left->color = BLACK; sibling->color = RED;     RBT_rotateRight(root,sibling); sibling = x->parent->right; }     sibling->color = x->parent->color; x->parent->color = BLACK; sibling->right->color = BLACK; RBT_rotateLeft(root, x->parent); x = (*root); } } } else { sibling = x->parent->left;     if(sibling->color == RED) { sibling->color = BLACK; x->parent->color = RED; RBT_rotateRight(root, x->parent); sibling = x->parent->left; } else { if(sibling->right->color == BLACK&& sibling->left->color == BLACK) { sibling->color = RED; x = x->parent; } else { if(sibling->right->color == RED) { sibling->right->color = BLACK; sibling->color = RED;   RBT_rotateLeft(root, sibling); sibling = x->parent->left; } sibling->color = x->parent->color; x->parent->color = BLACK; sibling->left->color = BLACK; RBT_rotateRight(root, x->parent);   x = (*root); } } } } x->color = BLACK; }     void RBT_printTree(NODE* node, int depth, int blackCount) { int i = 0; char c = 'X'; int v = -1; char cnt[100];     if( node == NULL || node == Nil ) return;     if( node->color == BLACK ) blackCount++;     if (node->parent != NULL) { v = node->parent->data;     if(node->parent->left == node) c = 'L'; else c = 'R'; }     if(node->left == Nil && node->right == Nil) sprintf(cnt, "------- %d", blackCount); else sprintf(cnt, "");     for( i = 0 ; i < depth ; i++ ) printf(" ");     printf("%d %s [%c, %d] %s\n", node->data, (node->color == RED) ? "RED" : "BLACK", c, v, cnt);     RBT_printTree(node->left, depth+1, blackCount); RBT_printTree(node->right, depth+1, blackCount); }

• 예제 main.c

#include "RedBlackTree.h" NODE* Nil;     void main() { NODE* tree = NULL; NODE* node = NULL;     Nil = RBT_createNode(0); Nil->color = BLACK;     while(1) { int cmd = 0; int param = 0; char buffer[10];     printf("Enter Command Number : \n"); printf("(1)createNdoe, (2)RemoveNode, (3)SearchNode\n"); printf("(4)DisplayTree, (5)Quit\n"); printf("commnad number : ");     fgets(buffer, sizeof(buffer)-1, stdin); sscanf(buffer, "%d", &cmd);     if( cmd < 1 || cmd > 5 ) { printf("Invaild command number.\n"); continue; } else if( cmd == 4 ) { RBT_printTree(tree, 0, 0); printf("\n"); continue; } else if( cmd == 5 ) break;     printf("EnterParamter (1~200) :\n");     fgets(buffer, sizeof(buffer)-1, stdin); sscanf(buffer, "%d", &param);     if( param < 1 || param > 200 ) { printf("Invaild parameter.%d\n", param); continue; }     switch(cmd) { case 1: { RBT_insertNode(&tree, RBT_createNode(param)); }                         break; case 2: { node = RBT_removeNode(&tree,param);     if( node == NULL ) printf("Not found to delete:%d\n", param); else RBT_destroyNode(node); }                         break; case 3: { node = RBT_searchNode(tree, param);     if( node == NULL ) printf("Not found node:%d\n", param); else printf("Found Node: %d(color:%s)\n", node->data, (node->color==RED)?"RED":"BLACK"); } break; printf("\n"); } } RBT_destroyTree(tree); }