[WEEK05] C언어로 구현하는 레드-블랙 트리 (Red-Black Tree)

SW Jungle/TIL (Today I Learned) 2022. 10. 27. 01:08

스스로 생각을 정리하기 위해 적은 글입니다. 초심자가 읽기를 권하지 않습니다!
정보에 오류가 있을 수 있습니다!

레드-블랙 트리란?

레드-블랙 트리는 스스로 균형을 잡는(self-balancing) 이진 탐색 트리이다.

스스로 균형을 잡는다는 말은, 트리에 원소가 삽입 또는 삭제될 때 어느 한 쪽에 편중되지 않도록 스스로 조정한다는 말이다.

균형잡힌 트리는 실행 시간이 우수하다는 장점이 있다. (시간복잡도가 낮음)

트리에 n개의 원소가 있을 때, $O(logN)$의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

일반적인 이진 탐색 트리의 경우에는 정렬된 형태의 데이터가 순서대로 삽입 될 경우 최악의 트리 형태를 띠게 된다.

왜냐하면 데이터가 오름차순이면 계속 가장 큰 값이 들어가기 때문에 노드의 오른쪽으로만 삽입되어 높이가 $N$이 되기 때문이다.

이러면 탐색이나 삭제의 수행시간은 최악의 경우 $O(N)$이 된다. (Singly Linked-List와 동일한 수행시간을 가지게 됨)

그렇기 때문에 균형잡힌 이진 탐색 트리를 사용하려고 하는 것이다.

트리의 높이가 일정하다면, 이진트리는 이분탐색과 비슷한 특성을 지니기 때문에 탐색에 걸리는 수행시간이 $logN$으로 감소하게 된다.

레드-블랙 트리는 각 노드에 RED 또는 BLACK의 색깔을 지정해서, 이들 색깔을 가지고 몇 가지 규칙에 따라 트리를 형성하여 트리가 근사적으로 균형을 이룰 수 있도록 만들어준다.

레드-블랙 트리의 규칙

모든 노드는 적색이거나 흑색이다.
루트는 흑색이다.
모든 리프(NIL)는 흑색이다.
노드가 적색이면 그 노드의 자식은 모두 흑색이다.
각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

5번 규칙이 존재하기 때문에 레드-블랙 트리는 근사적으로 균형을 맞추게 된다.

더 엄격하게 균형을 맞추면 탐색에 걸리는 시간을 줄일 수 있겠지만, 그러면 균형을 맞추는 데에 시간을 너무 많이 쏟을 수도 있게 되므로 삽입과 삭제의 수행시간이 길어질 염려가 있다. (엄격하게 맞추는 AVL 트리라는 구조가 있다)

경계 노드(Sentinel Node)를 갖는 레드-블랙 트리

한계 조건을 다루기 편리하도록 트리의 경계 노드를 만들어 줄 수 있다.

루트의 부모와 모든 리프 노드는 NIL 노드여야 하고,

모든 리프 노드는 흑색이어야 한다.

이들 모두에 개별적으로 저장 공간을 할당하게 되면 공간이 낭비될 것이다.

그래서 우리는 이들의 포인터를 NIL 노드로 설정하여, 색깔 값으로 흑색을 준다.

그러면 '모든 리프는 흑색이다' 라는 규칙 3번을 만족시킬 수 있고, 적색 노드의 양쪽 자식이 없을 경우에도 규칙 4번을 만족시킬 수 있게 된다.

경계 노드를 굳이 만들지 않아도 구현은 가능하다.

트리 수정 시 위반되는 레드-블랙 특성 복구를 위한 회전(Rotate)

이진탐색트리의 규칙에 따라 트리에 원소를 삽입하거나 삭제할 때, 레드-블랙 특성이 위반될 가능성이 있다.

이를 복구하기 위해서 트리를 회전하는 것이 필요하다.

어떤 노드 X를 기준으로 오른쪽 회전을 수행하면,

X의 왼쪽 자식이 X의 위치에 오고

X는 X의 오른쪽 자식이 있던 위치에 가게 된다.

마치 트리 전체가 노드 X를 기준으로 한 방향으로 회전하는 것처럼 보인다.

이들 연산은 포인터의 조정을 통해 이루어진다.

각 노드의 주소는 변하지 않는다. 다만 그 노드가 가지고 있는 포인터가 가리키는 주소 값이 바뀔 뿐이다.

(애초에 트리 자체가 불규칙한 메모리 위치 간에 포인터를 이용해서 관계를 만들어 주는 자료구조이기 때문에...)

회전에 사용되는 코드는 다음과 같다.

// right_rotate는 left_rotate의 코드와 대칭이다.
void rbtree_left_rotate(rbtree *t, node_t *x) {
  node_t *y = x->right;

  x->right = y->left;
  if (y->left != t->nil) {
    y->left->parent = x;
  }

  y->parent = x->parent;
  if (x->parent == t->nil) {
    t->root = y;
  }
  else if (x == x->parent->left) {
    x->parent->left = y;
  }
  else {
    x->parent->right = y;
  }

  y->left = x;
  x->parent = y;
}

레드-블랙 트리의 삽입

레드-블랙 트리에서의 삽입은 이진탐색트리와 동일하게 이루어진다.

다만 새로 생성되는 노드는 적색이라는 특징이 있다.

적색 노드를 삽입해 주어야 이후에 레드-블랙 특성을 맞추기 위한 FIX-UP 작업이 가능해진다.

적색 노드가 트리에 삽입될 경우, 2가지의 규칙 위반이 발생할 수 있다.

'2. 루트는 흑색이다' 와

'4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다' 라는 규칙이다.

2번의 위반은 삽입되는 위치가 루트일 경우에 발생한다.

4번의 위반은 삽입되는 위치의 부모가 적색일 경우에 발생한다.

삽입은 다음 코드와 같이 진행된다.

node_t *rbtree_make_new_node(rbtree *t, const key_t key) {
  node_t *new_node = (node_t *)calloc(1, sizeof(node_t));

  new_node->color = RBTREE_RED;
  new_node->key = key;
  new_node->parent = t->nil;
  new_node->left = t->nil;
  new_node->right = t->nil;

  return new_node;
}

node_t *rbtree_insert(rbtree *t, const key_t key) {
  node_t *new_node = rbtree_make_new_node(t, key);

  node_t *p = t->root;  // p means current pointer
  if (p == t->nil) {  // if root is empty
    t->root = new_node;
  }
  else {
    node_t *tmp;
    char flag;
    while (p != t->nil) {
      tmp = p;
      if (key <= p->key) {
        p = p->left;
        flag = 'L';
      }
      else {
        p = p->right;
        flag = 'R';
      }
    }
    if (flag == 'L') {
      tmp->left = new_node;
    }
    else {
      tmp->right = new_node;
    }
    new_node->parent = tmp;
  }
  rbtree_insert_fix_up(t, new_node);
  return new_node;
}

특성에 맞추기 위한 FIX-UP 작업은 다음 코드와 같이 진행된다.

void rbtree_insert_fix_up(rbtree *t, node_t *p) {
  while (p->parent->color == RBTREE_RED) {
    if (p->parent == p->parent->parent->left) {
      node_t *uncle = p->parent->parent->right;
      if (uncle->color == RBTREE_RED) {
        p->parent->color = RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        p = p->parent->parent;  // move pointer to grandparent
      }
      else {
        if (p == p->parent->right) {
          p = p->parent;  // move pointer to parent
          rbtree_left_rotate(t, p);
        }
        p->parent->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        rbtree_right_rotate(t, p->parent->parent);
      }
    }
    else {
      node_t *uncle = p->parent->parent->left;
      if (uncle->color == RBTREE_RED) {
        p->parent->color = RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        p = p->parent->parent;  // move pointer to grandparent
      }
      else {
        if (p == p->parent->left) {
          p = p->parent;  // move pointer to parent
          rbtree_right_rotate(t, p);
        }
        p->parent->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        rbtree_left_rotate(t, p->parent->parent);
      }
    }
  }
  t->root->color = RBTREE_BLACK;
}

레드-블랙 트리의 삭제

삭제도 이진탐색트리의 삭제와 비슷한 방법으로 작동한다.

다만 여기서도 삭제로 인해 발생하는 레드-블랙 규칙 위반을 FIX-UP을 통해 수정해 주어야 한다.

우선 규칙위반을 고려하지 않고 삭제 자체만 보면 다음과 같다.

삭제할 노드가 자식이 없을 경우
- 삭제되는 노드의 색깔을 기억해둔다.
- 해당 노드를 삭제한다.
삭제할 노드의 자식이 한 개일 경우
- 삭제되는 노드의 색깔을 기억해둔다.
- 해당 노드를 삭제하고 밑의 자식을 그 위치에 올려준다.
삭제할 노드의 자식이 두 개일 경우
- 삭제되는 노드의 직후원소 (값을 오름차순으로 정렬했을 때, 삭제되는 노드 바로 다음에 오는 원소)의 색깔을 기억해둔다.
- 직후원소를 기준으로 몇 가지 조건을 따진다.
  1. 직후원소의 부모가 삭제되는 노드이면 -> 노드를 삭제하고 직후원소를 그 자리에 올려준다.
  2. 직후원소의 부모가 다른 노드이면 -> 직후원소의 오른쪽 자식을 직후원소의 자리에 올려주고, 직후원소는 삭제되는 노드의 위치로 올라간다.

삭제를 완료하고 규칙위반이 발생하는 경우는 위에서 기억해둔 색깔이 흑색일 때 발생한다.

왜냐하면 적색일 경우 삭제하거나 이동하여도 레드-블랙 특성이 유지되기 때문이다. 그 이유는 다음과 같다.

흑색 높이는 모두 그대로 유지된다.
적색 노드가 인접하게 될 가능성도 없다.
적색 노드는 루트가 아니므로 루트는 흑색으로 유지된다.

반대로 삭제하는 노드가 흑색일 경우 3가지의 규칙 위반이 발생할 수 있다.

삭제하는 노드가 루트일 경우 '2. 루트는 흑색이다'가 위반될 수 있다.
삭제된 위치에 이동시킨 노드가 적색이고, 그 부모도 적색이라면 '4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.'가 위반된다.
삭제하는 노드 또는 삭제하는 노드의 직후원소는 삭제 또는 이동되면서 흑색을 하나 줄이게 된다.
따라서 해당 경로에 대해 '5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.'가 위반된다.

삭제를 위한 코드는 다음과 같다.

삭제를 위한 TRANSPLANT 코드 :

void rbtree_transplant(rbtree *t, node_t *p, node_t *replace_p) {
  if (p->parent == t->nil) {
    t->root = replace_p;
  }
  else if (p == p->parent->left) {
    p->parent->left = replace_p;
  }
  else {
    p->parent->right = replace_p;
  }
  replace_p->parent = p->parent;
}

삭제 동작 코드 :

int rbtree_erase(rbtree *t, node_t *erased) {
  // the name of variables means : 'node' that should be *erased, *modified, *replaced
  node_t *modified = erased;
  color_t modified_origin_color = modified->color;
  node_t *replaced;
  if (erased->left == t->nil) {
    replaced = erased->right;
    rbtree_transplant(t, erased, erased->right);
  }
  else if (erased->right == t->nil) {
    replaced = erased->left;
    rbtree_transplant(t, erased, erased->left);
  }
  else {
    modified = rbtree_subtree_min(t, erased->right);
    modified_origin_color = modified->color;
    replaced = modified->right;
    if (modified->parent == erased) {
      replaced->parent = modified;
    }
    else {
      rbtree_transplant(t, modified, modified->right);
      modified->right = erased->right;
      modified->right->parent = modified;
    }
    rbtree_transplant(t, erased, modified);
    modified->left = erased->left;
    modified->left->parent = modified;
    modified->color = erased->color;
  }
  if (modified_origin_color == RBTREE_BLACK) {
    rbtree_erase_fix_up(t, replaced);
  }
  free(erased);
  return 0;
}

위반사항을 복구하기 위한 FIX-UP 코드는 다음과 같다.

void rbtree_erase_fix_up(rbtree *t, node_t *p) {
  while (p != t->root && p->color == RBTREE_BLACK) {
    if (p == p->parent->left) {
      node_t *sibling = p->parent->right;
      if (sibling->color == RBTREE_RED) {
        sibling->color = RBTREE_BLACK;
        p->parent->color = RBTREE_RED;
        rbtree_left_rotate(t, p->parent);
        sibling = p->parent->right;
      }
      if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK) {
        sibling->color = RBTREE_RED;
        p = p->parent;
      }
      else {
        if (sibling->right->color == RBTREE_BLACK) {
        sibling->left->color = RBTREE_BLACK;
        sibling->color = RBTREE_RED;
        rbtree_right_rotate(t, sibling);
        sibling = p->parent->right;
        }
        sibling->color = p->parent->color;
        p->parent->color = RBTREE_BLACK;
        sibling->right->color = RBTREE_BLACK;
        rbtree_left_rotate(t, p->parent);
        p = t->root;
      }
    }
    else {
      node_t *sibling = p->parent->left;
      if (sibling->color == RBTREE_RED) {
        sibling->color = RBTREE_BLACK;
        p->parent->color = RBTREE_RED;
        rbtree_right_rotate(t, p->parent);
        sibling = p->parent->left;
      }
      if (sibling->right->color == RBTREE_BLACK && sibling->left->color == RBTREE_BLACK) {
        sibling->color = RBTREE_RED;
        p = p->parent;
      }
      else {
        if (sibling->left->color == RBTREE_BLACK) {
        sibling->right->color = RBTREE_BLACK;
        sibling->color = RBTREE_RED;
        rbtree_left_rotate(t, sibling);
        sibling = p->parent->left;
        }
        sibling->color = p->parent->color;
        p->parent->color = RBTREE_BLACK;
        sibling->left->color = RBTREE_BLACK;
        rbtree_right_rotate(t, p->parent);
        p = t->root;
      }
    }
  }
  p->color = RBTREE_BLACK;
}

코드 보기

전체 코드는 아래와 같이 동작하게 된다. 아래 C코드에 사용되는 구조체 등을 정의하기 위한 HEADER 파일은 더보기를 눌러서 볼 수 있다.

// rbtree.h

#ifndef _RBTREE_H_
#define _RBTREE_H_

#include <stddef.h>

typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;

typedef int key_t;

typedef struct node_t {
  color_t color;
  key_t key;
  struct node_t *parent, *left, *right;
} node_t;

typedef struct {
  node_t *root;
  node_t *nil;  // for sentinel
} rbtree;

rbtree *new_rbtree(void);
void delete_rbtree(rbtree *);

node_t *rbtree_insert(rbtree *, const key_t);
node_t *rbtree_find(const rbtree *, const key_t);
node_t *rbtree_min(const rbtree *);
node_t *rbtree_max(const rbtree *);
int rbtree_erase(rbtree *, node_t *);

int rbtree_to_array(const rbtree *, key_t *, const size_t);

#endif  // _RBTREE_H_

#include "rbtree.h"

#include <stdlib.h>

rbtree *new_rbtree(void) {
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));

  node_t *nil = (node_t *)calloc(1, sizeof(node_t));
  nil->color = RBTREE_BLACK;
  nil->key = 0;
  nil->parent = NULL;
  nil->left = NULL;
  nil->right = NULL;

  p->nil = nil;
  p->root = p->nil;

  return p;
}

void delete_rbtree_DFS(rbtree *t, node_t *p) {
  if (p == t->nil) {
    return;
  }
  else {
    delete_rbtree_DFS(t, p->left);
    delete_rbtree_DFS(t, p->right);
    free(p);
  }
}

void delete_rbtree(rbtree *t) {
  delete_rbtree_DFS(t, t->root);
  free(t->nil);
  free(t);
}

void rbtree_left_rotate(rbtree *t, node_t *x) {
  node_t *y = x->right;

  x->right = y->left;
  if (y->left != t->nil) {
    y->left->parent = x;
  }

  y->parent = x->parent;
  if (x->parent == t->nil) {
    t->root = y;
  }
  else if (x == x->parent->left) {
    x->parent->left = y;
  }
  else {
    x->parent->right = y;
  }

  y->left = x;
  x->parent = y;
}

void rbtree_right_rotate(rbtree *t, node_t *y) {
  node_t *x = y->left;

  y->left = x->right;
  if (x->right != t->nil) {
    x->right->parent = y;
  }

  x->parent = y->parent;
  if (y->parent == t->nil) {
    t->root = x;
  }
  else if (y == y->parent->left) {
    y->parent->left = x;
  }
  else {
    y->parent->right = x;
  }
  
  x->right = y;
  y->parent = x;
}

void rbtree_insert_fix_up(rbtree *t, node_t *p) {
  while (p->parent->color == RBTREE_RED) {
    if (p->parent == p->parent->parent->left) {
      node_t *uncle = p->parent->parent->right;
      if (uncle->color == RBTREE_RED) {
        p->parent->color = RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        p = p->parent->parent;  // move pointer to grandparent
      }
      else {
        if (p == p->parent->right) {
          p = p->parent;  // move pointer to parent
          rbtree_left_rotate(t, p);
        }
        p->parent->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        rbtree_right_rotate(t, p->parent->parent);
      }
    }
    else {
      node_t *uncle = p->parent->parent->left;
      if (uncle->color == RBTREE_RED) {
        p->parent->color = RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        p = p->parent->parent;  // move pointer to grandparent
      }
      else {
        if (p == p->parent->left) {
          p = p->parent;  // move pointer to parent
          rbtree_right_rotate(t, p);
        }
        p->parent->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        rbtree_left_rotate(t, p->parent->parent);
      }
    }
  }
  t->root->color = RBTREE_BLACK;
}

node_t *rbtree_make_new_node(rbtree *t, const key_t key) {
  node_t *new_node = (node_t *)calloc(1, sizeof(node_t));

  new_node->color = RBTREE_RED;
  new_node->key = key;
  new_node->parent = t->nil;
  new_node->left = t->nil;
  new_node->right = t->nil;

  return new_node;
}

node_t *rbtree_insert(rbtree *t, const key_t key) {
  node_t *new_node = rbtree_make_new_node(t, key);

  node_t *p = t->root;  // p means current pointer
  if (p == t->nil) {  // if root is empty
    t->root = new_node;
  }
  else {
    node_t *tmp;
    char flag;
    while (p != t->nil) {
      tmp = p;
      if (key <= p->key) {
        p = p->left;
        flag = 'L';
      }
      else {
        p = p->right;
        flag = 'R';
      }
    }
    if (flag == 'L') {
      tmp->left = new_node;
    }
    else {
      tmp->right = new_node;
    }
    new_node->parent = tmp;
  }
  rbtree_insert_fix_up(t, new_node);
  return new_node;
}

node_t *rbtree_find(const rbtree *t, const key_t key) {
  node_t *p = t->root;
  while (p != t->nil) {
    if (key == p->key) {
      return p;
    }
    else if (key < p->key) {
      p = p->left;
    }
    else {
      p = p->right;
    }
  }
  return NULL;
}

node_t *rbtree_min(const rbtree *t) {
  node_t *p = t->root;
  if (p == t->nil) {
    return NULL;
  }
  else {
    while (p->left != t->nil) {
      p = p->left;
    }
  }
  return p;
}

node_t *rbtree_max(const rbtree *t) {
  node_t *p = t->root;
  if (p == t->nil) {
    return NULL;
  }
  else {
    while (p->right != t->nil) {
      p = p->right;
    }
  }
  return p;
}

void rbtree_transplant(rbtree *t, node_t *p, node_t *replace_p) {
  if (p->parent == t->nil) {
    t->root = replace_p;
  }
  else if (p == p->parent->left) {
    p->parent->left = replace_p;
  }
  else {
    p->parent->right = replace_p;
  }
  replace_p->parent = p->parent;
}

node_t *rbtree_subtree_min(rbtree *t, node_t *sub_root) {
  node_t *sub_min = sub_root;
  while (sub_min->left != t->nil) {
    sub_min = sub_min->left;
  }
  return sub_min;
}

void rbtree_erase_fix_up(rbtree *t, node_t *p) {
  while (p != t->root && p->color == RBTREE_BLACK) {
    if (p == p->parent->left) {
      node_t *sibling = p->parent->right;
      if (sibling->color == RBTREE_RED) {
        sibling->color = RBTREE_BLACK;
        p->parent->color = RBTREE_RED;
        rbtree_left_rotate(t, p->parent);
        sibling = p->parent->right;
      }
      if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK) {
        sibling->color = RBTREE_RED;
        p = p->parent;
      }
      else {
        if (sibling->right->color == RBTREE_BLACK) {
        sibling->left->color = RBTREE_BLACK;
        sibling->color = RBTREE_RED;
        rbtree_right_rotate(t, sibling);
        sibling = p->parent->right;
        }
        sibling->color = p->parent->color;
        p->parent->color = RBTREE_BLACK;
        sibling->right->color = RBTREE_BLACK;
        rbtree_left_rotate(t, p->parent);
        p = t->root;
      }
    }
    else {
      node_t *sibling = p->parent->left;
      if (sibling->color == RBTREE_RED) {
        sibling->color = RBTREE_BLACK;
        p->parent->color = RBTREE_RED;
        rbtree_right_rotate(t, p->parent);
        sibling = p->parent->left;
      }
      if (sibling->right->color == RBTREE_BLACK && sibling->left->color == RBTREE_BLACK) {
        sibling->color = RBTREE_RED;
        p = p->parent;
      }
      else {
        if (sibling->left->color == RBTREE_BLACK) {
        sibling->right->color = RBTREE_BLACK;
        sibling->color = RBTREE_RED;
        rbtree_left_rotate(t, sibling);
        sibling = p->parent->left;
        }
        sibling->color = p->parent->color;
        p->parent->color = RBTREE_BLACK;
        sibling->left->color = RBTREE_BLACK;
        rbtree_right_rotate(t, p->parent);
        p = t->root;
      }
    }
  }
  p->color = RBTREE_BLACK;
}

int rbtree_erase(rbtree *t, node_t *erased) {
  // the name of variables means : 'node' that should be *erased, *modified, *replaced
  node_t *modified = erased;
  color_t modified_origin_color = modified->color;
  node_t *replaced;
  if (erased->left == t->nil) {
    replaced = erased->right;
    rbtree_transplant(t, erased, erased->right);
  }
  else if (erased->right == t->nil) {
    replaced = erased->left;
    rbtree_transplant(t, erased, erased->left);
  }
  else {
    modified = rbtree_subtree_min(t, erased->right);
    modified_origin_color = modified->color;
    replaced = modified->right;
    if (modified->parent == erased) {
      replaced->parent = modified;
    }
    else {
      rbtree_transplant(t, modified, modified->right);
      modified->right = erased->right;
      modified->right->parent = modified;
    }
    rbtree_transplant(t, erased, modified);
    modified->left = erased->left;
    modified->left->parent = modified;
    modified->color = erased->color;
  }
  if (modified_origin_color == RBTREE_BLACK) {
    rbtree_erase_fix_up(t, replaced);
  }
  free(erased);
  return 0;
}

void rbtree_to_array_mid_DFS(const rbtree *t, key_t *arr, int *i_pointer, node_t *p) {
  if (p == t->nil) {
    return;
  }
  else {
    rbtree_to_array_mid_DFS(t, arr, i_pointer, p->left);
    arr[*i_pointer] = p->key;
    *i_pointer += 1;
    rbtree_to_array_mid_DFS(t, arr, i_pointer, p->right);
  }
}

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
  node_t *p = t->root;
  int i = 0;
  int *i_pointer = &i;
  rbtree_to_array_mid_DFS(t, arr, i_pointer, p);
  return 0;
}

참고문헌

Thomas H. Cormen., Charles E. Leiserson., Ronald L. Rivest., & Clifford Stein. (2014). Introduction to Algorithms (3rd ed.). (문병로, 심규석, & 이충세 역). 한빛 아카데미. (Original work published 2009)

저작자표시 비영리 변경금지

'SW Jungle > TIL (Today I Learned)' 카테고리의 다른 글

[WEEK07] C언어에서 문자열 다루기. 근데 이제 포인터와 파싱(parsing)을 곁들인 (0)	2022.11.10
[WEEK06] Malloc Lab 설명서 번역 (CS:APP) (2)	2022.10.28
[WEEK04/DAY02] 백준 9084번: 동전 (0)	2022.10.15
[WEEK03/DAY04] 백준 21606번 : 아침 산책 (2)	2022.10.10
[WEEK02/DAY06] 백준 문제 : 뱀 (1)	2022.10.05

ABOUT ME

ProdYou

목차

레드-블랙 트리란?

레드-블랙 트리의 규칙

경계 노드(Sentinel Node)를 갖는 레드-블랙 트리

트리 수정 시 위반되는 레드-블랙 특성 복구를 위한 회전(Rotate)

레드-블랙 트리의 삽입

레드-블랙 트리의 삭제

코드 보기

'SW Jungle > TIL (Today I Learned)' 카테고리의 다른 글

티스토리툴바

ABOUT ME

목차

레드-블랙 트리란?

레드-블랙 트리의 규칙

경계 노드(Sentinel Node)를 갖는 레드-블랙 트리

트리 수정 시 위반되는 레드-블랙 특성 복구를 위한 회전(Rotate)

레드-블랙 트리의 삽입

레드-블랙 트리의 삭제

코드 보기

'SW Jungle > TIL (Today I Learned)' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바