Red-Black Tree

qwbsy·2021년 12월 2일
0

c언어를 공부하면서 처음으로 주어진 과제는 Red-Black Tree(RB tree) 구현이었다. RB tree를 구현하기 위해서는 기본적으로 malloc/free와 포인터, RB tree에 대한 개념 등을 알아야 했다.

우선 c언어와 익숙해지기 위해 난이도가 낮은 linked list 부터 구현해보았다. 그러면서 기본적인 malloc/free의 사용법을 익히고 queue, tree 등의 자료구조를 더 구현해보면서 포인터를 이해했다.

그 다음으로는 내가 어떤 코드를 구현해야 하는지를 알기 위해 RB tree의 개념을 살펴봤다. RB tree의 기본적인 설명은 다음과 같다.

이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조

이진 트리의 한 종류라는 것은 바로 알 수 있었는데 비교 가능한 자료를 정리하는 데 어떻게 쓰이는지는 다음과 같은 특성을 통해 이해할 수 있었다.

  1. 노드는 레드 혹은 블랙이다
  2. 루트 노드는 블랙이다
  3. 모든 리프 노드들(NIL)은 블랙이다.
  4. 레드 노드의 자식노드는 언제나 블랙이다.
  5. 특정 노드에서 시작하여 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 같은 수의 블랙 노드가 있다.

이 조건들을 모두 만족하면 균형 이진 트리가 되기 때문에 효율적으로 활용할 수 있는 자료구조가 되는 것이다.

typedef enum { RBTREE_RED, RBTREE_BLACK } color_t; //node 색깔

typedef int key_t; //key 값은 int

typedef struct node_t {
  color_t color;
  key_t key;
  struct node_t *parent, *left, *right;
} node_t; //node_t 구조체는 색깔, 키, 부모/왼쪽자식/오른쪽자식 노드로 이루어져 있다.

typedef struct {
  node_t *root;
} rbtree; //rbtree 구조체는 루트노드를 가리킨다.

기본적으로 주어진 구조체들에 간단한 주석을 달아보았다. 이 구조체들을 바탕으로 RB tree가 의미있는 자료구조가 될 수 있도록 삽입,삭제,찾기 등의 기능을 구현해야 한다. 기능을 구현할 때 고려해야 할 사항들을 짚어보자.

삽입

비어 있는 트리에 처음 노드를 삽입하면 그 노드는 루트가 되고 2번 규칙에 따라 Black 노드가 된다. 그 다음으로 삽입하는 루트노드의 자식은 5번 규칙에 따라 Red 노드가 된다. 5번 규칙을 지키기 위해서 루트 이후에 삽입되는 노드는 Red로 하는 것이 유리하다.

루트 노드의 자식까지는 별다른 작업 없이 일반 트리와 같이 삽입하면 되는데 루트 노드의 자식의 자식이 삽입되면서부터는 추가 조건을 고려해야 한다. 삽입되는 노드의 색깔을 Red로 고정했을 때 다음으로 고려해야 하는 상황은 삽입된 노드의 부모가 Red이면 4번 규칙이 위배된다. 이 경우는 여러가지 상황이 있을 수 있는데 각각의 상황을 살펴보자.

case1 삼촌 노드도 Red

이 경우에는 부모 노드와 삼촌 노드를 Black으로 바꾸고 조부모 노드를 Red로 바꿔준다. 그러면 4번 규칙을 해결하면서도 5번 규칙이 위배되지 않도록 해준다. 대신에 조부모 노드가 Red가 됐으니 그 노드를 기준으로 체크를 다시 해줘야 한다.

case2 조부모와 부모가 일직선

Red 노드가 부모의 왼쪽자식이면서 부모도 조부모의 왼쪽자식이거나 반대로 Red 노드가 부모의 오른쪽 자식이면서 부모도 조부모의 오른쪽 자식인 경우이다.

여기서부터 rotation이라는 개념이 필요하다.

오른쪽으로 회전을 하면 기준이 되는 P 노드가 올라가고 P 노드의 오른쪽 노드가 P의 부모였던 Q 노드의 왼쪽 자식이 되면서 Q 노드가 P의 오른쪽 노드로 바뀐다. 반대로 왼쪽으로 회전을 하면 기준이 되는 Q 노드가 올라가고 Q 노드의 왼쪽 자식이 Q 노드의 부모였던 P 노드의 오른쪽 자식이 되고 P 노드가 Q 노드의 왼쪽 자식이 된다.

이 rotation 개념을 각각의 상황에 맞게 활용해야 한다.
왼쪽으로 일직선인 경우에는 본인도 Red이고 자식도 Red인 노드를 기준으로 우회전을 하고 난 후 본인과 오른쪽 자식의 색을 바꾼다.
오른쪽으로 일직선인 경우에도 본인도 Red이고 자식도 Red인 노드를 기준으로 좌회전을 하고 난 후 본인과 왼쪽 자식의 색을 바꾼다.
1번 케이스(삼촌 노드도 Red)가 아닌 다음 케이스들이므로 Red로 바뀌는 노드의 자식노드는 black이기 때문에 새로 위배되는 규칙이 만들어지지 않는다.

case3 일직선이 아닌 경우

2번 케이스와 다르게 연속되는 Red 노드가 조부모를 기준으로 왼쪽 자식-오른쪽 자식이 되거나 오른쪽 자식-왼쪽 자식이 되는 경우가 있다. 이런 경우에는 아래 Red 노드를 기준으로 각각 좌회전, 우회전을 해주면 좌로 일직선, 우로 일직선인 경우가 된다. 일직선이 된 후에는 2번 케이스를 진행해주면 된다.

삭제

NIL노드의 부모 노드가 아닌 노드를 삭제하면 그 자리를 대체해 줄 노드를 데려와야 하는데 선택지는 삭제된 노드의 왼쪽 서브 트리의 가장 오른쪽 노드, 오른쪽 서브 트리의 가장 왼쪽 노드 이렇게 두 가지가 있다. 여기서는 전자를 우선으로 선택하기로 한다. 노드의 색은 삭제되기 전 노드의 색으로 한다. 이제 NIL노드의 부모 노드가 자리를 비운 상황만 가정하면 된다. 이 노드의 색이 Red이면 그냥 NIL노드로 대체해주면 된다. 문제는 이 노드가 Black일 때 생긴다. 이 노드의 자식 하나가 NIL이 아니면 그 노드로 대체해주기만 하면 되는데 그 외의 상황은 각각의 케이스를 살펴봐야한다.(이 노드가 부모의 왼쪽 자식일 때 기준의 설명 -> 이 노드가 오른쪽 자식이면 다음 설명들의 왼쪽,오른쪽을 바꿔서 생각).

case1 형제 노드가 빨강

삭제되기 전 4번, 5번 규칙을 만족하려면 형제 노드의 왼쪽,오른쪽 자식 둘 다 NIL이 아닌 검정 노드여야 한다. 다시 균형을 맞추려면 형제 노드를 기준으로 좌회전을 하고 부모였던 노드를 빨강, 형제였던 노드를 검정으로 처리한다.

case2 형제의 오른쪽 노드가 빨강

이는 형제 노드가 검정임을 보장받고, 부모 노드와 형제의 왼쪽 노드는 신경쓰지 않고 다음 상황을 고려하면 된다. 형제 노드를 기준으로 좌회전을 하고 부모였던 노드와 형제였던 노드의 색을 변경해주고 형제의 오른쪽 자식이었던 노드의 색을 검정으로 하면 모든 규칙을 만족한다.

case3 형제의 왼쪽 노드가 빨강

case2가 아니니 형제의 오른쪽 노드는 검정이다. 빨강인 형제의 왼쪽 노드를 기준으로 우회전하고 형제였던 노드와 색을 바꿔서 case2로 만들어준다.

case4 형제, 형제의 자식 노드들 모두 검정

case2,3을 지나왔으니 형제와 형제의 자식 노드들은 모두 검정이다. 부모 노드가 빨강이었으면 검정으로 하고 형제 노드의 색깔을 빨강으로 바꿔주면 5번 규칙을 만족한다. 하지만 부모 노드가 검정이었으면 해당 서브트리의 검정 노드 개수가 하나 줄어든 상태로 일치시킨 것이라서 부모 노드가 루트 노드가 아니라면 부모 노드를 기준으로 다시 점검을 해야한다

0개의 댓글