4. RBTREE 탐색, array 변환

1.  탐색

1) key 탐색

• tree내에 해당 key가 있는지 탐색하여 해당 노드의 포인터를 반환한다.
• 해당하는 node가 없으면 NULL을 반환한다.
• 루트 노드를 시작으로 'current' 포인터를 설정한다.
• 'current'의 key값과 찾으려는 key값을 비교하며 노드를 이동시키면서 key값과 같은 노드를 찾는다.
• 시간 복잡도: 탐색 시 자식 노드의 수가 항상 2개로 제한되기 때문에, 한 단계씩 이동할 때마다 검색 대상 노드의 수가 절반으로 줄어들게 되어 시간 복잡도는 $O(log n)$이 된다.

💻 key 탐색 CODE

/* 4️⃣ 탐색 1 - key 탐색 */

// key에 해당하는 노드를 반환하는 함수
node_t *rbtree_find(const rbtree *t, const key_t key)
{
  node_t *current = t->root;
  while (current != t->nil)
  {
    if (key == current->key)
      return current;
    else
      current = (key < current->key) ? current->left : current->right;
  }
  return NULL; // 해당 key값을 가진 노드가 없을 경우 NULL 반환
}

2) 최소값/최대값 탐색

• 루트 노드를 시작으로 'current' 포인터를 설정한다.
• 'current' 노드의 왼쪽/오른쪽 자식 노드가 'nil 노드'가 아닐 때까지 반복하여, current 노드를 왼쪽/오른쪽 자식 노드로 업데이트
• 'current' 노드는 tree에서 가장 작은/큰 key 값을 가진 노드가 되므로 current 노드를 반환한다.
• 시간 복잡도: 트리의 높이만큼 반복되므로 시간 복잡도는 $O(log n)$이 된다.

💻 최소값/최대값 탐색 CODE

/* 4️⃣ 탐색 2 - 최소값을 가진 node 탐색 */

// key가 최소값에 해당하는 노드를 반환하는 함수
node_t *rbtree_min(const rbtree *t)
{
  node_t *current = t->root;
  while (current->left != t->nil)
    current = current->left;
  return current;
}

2. array로 변환

• RB tree의 내용을 key 순서대로 주어진 array로 변환한다.
• array의 크기는 n으로 주어지며 tree의 크기가 n 보다 큰 경우에는 순서대로 n개 까지만 변환한다.
• 'rbtree_min()' 함수를 호출하여 가장 작은 값을 가진 노드를 시작으로 current 포인터를 설정한다.
• 루프를 돌면서 'current' 노드를 get_next_node 함수를 활용해 inorder traversal 하면서 다음 노드를 가져와서 key 값을 'arr'에 저장한다.
• 루프를 n번 반복하거나 'current'가 더 이상 존재하지 않을 때까지 반복한다.

💻 array로 변환 CODE

/* 5️⃣ array로 변환 */

// `t`를 inorder로 `n`번 순회한 결과를 `arr`에 담는 함수
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n)
{
  node_t *current = rbtree_min(t);
  arr[0] = current->key;
  for (int i = 1; i < n; i++)
  {
    if (current == t->nil)
      break;                             // 노드가 끝까지 탐색된 경우 loop 탈출
    current = get_next_node(t, current); // 다음 노드로 이동
    if (current == t->nil)
      break;               // 노드가 끝까지 탐색된 경우 loop 탈출
    arr[i] = current->key; // 현재 노드의 key 값을 배열에 저장
  }
  return 0;
}

1) inorder traversal

• get_next_node 함수를 활용해 다음 노드를 찾아서 inorder traversal을 수행한다.

get_next_node

• 'p' 노드의 오른쪽 자식 노드를 시작으로 'current' 포인터를 설정한다.
• 'p' 노드의 오른쪽 자식 노드가 없다면 'current' 변수를 'p' 노드로 초기화하고, 'while' 루프를 통해 다음과 같이 작업한다.
  • 'current' 노드가 부모 노드의 오른쪽 자식 노드인 경우, 부모 노드로 이동한다.
  • 'current' 노드가 부모 노드의 왼쪽 자식 노드인 경우, 부모 노드를 반환한다.
• 'current' 노드의 왼쪽 자식 노드가 없을 때까지 'current' 노드를 왼쪽 자식 노드로 업데이트한다.
• 최종적으로 'current' 노드를 반환한다.

💻 get_next_node CODE

// 키 값을 기준으로 다음 노드를 반환하는 함수
node_t *get_next_node(const rbtree *t, node_t *p)
{
  node_t *current = p->right;
  if (current == t->nil) // 오른쪽 자식이 없으면
  {
    current = p;
    while (1)
    {
      if (current->parent->right == current) // current가 오른쪽 자식인 경우
        current = current->parent;           // 부모 노드로 이동 후 이어서 탐색
      else
        return current->parent; // current가 왼쪽 자식인 경우 부모 리턴
    }
  }
  while (current->left != t->nil) // 왼쪽 자식이 있으면
    current = current->left;      // 왼쪽 끝으로 이동
  return current;
}// 키 값을 기준으로 다음 노드를 반환하는 함수
node_t *get_next_node(const rbtree *t, node_t *p)
{
  node_t *current = p->right;
  if (current == t->nil) // 오른쪽 자식이 없으면
  {
    current = p;
    while (1)
    {
      if (current->parent->right == current) // current가 오른쪽 자식인 경우
        current = current->parent;           // 부모 노드로 이동 후 이어서 탐색
      else
        return current->parent; // current가 왼쪽 자식인 경우 부모 리턴
    }
  }
  while (current->left != t->nil) // 왼쪽 자식이 있으면
    current = current->left;      // 왼쪽 끝으로 이동
  return current;
}// 키 값을 기준으로 다음 노드를 반환하는 함수
node_t *get_next_node(const rbtree *t, node_t *p)
{
  node_t *current = p->right;
  if (current == t->nil) // 오른쪽 자식이 없으면
  {
    current = p;
    while (1)
    {
      if (current->parent->right == current) // current가 오른쪽 자식인 경우
        current = current->parent;           // 부모 노드로 이동 후 이어서 탐색
      else
        return current->parent; // current가 왼쪽 자식인 경우 부모 리턴
    }
  }
  while (current->left != t->nil) // 왼쪽 자식이 있으면
    current = current->left;      // 왼쪽 끝으로 이동
  return current;
}// 키 값을 기준으로 다음 노드를 반환하는 함수
node_t *get_next_node(const rbtree *t, node_t *p)
{
  node_t *current = p->right;
  if (current == t->nil) // 오른쪽 자식이 없으면
  {
    current = p;
    while (1)
    {
      if (current->parent->right == current) // current가 오른쪽 자식인 경우
        current = current->parent;           // 부모 노드로 이동 후 이어서 탐색
      else
        return current->parent; // current가 왼쪽 자식인 경우 부모 리턴
    }
  }
  while (current->left != t->nil) // 왼쪽 자식이 있으면
    current = current->left;      // 왼쪽 끝으로 이동
  return current;
}// 키 값을 기준으로 다음 노드를 반환하는 함수
node_t *get_next_node(const rbtree *t, node_t *p)
{
  node_t *current = p->right;
  if (current == t->nil) // 오른쪽 자식이 없으면
  {
    current = p;
    while (1)
    {
      if (current->parent->right == current) // current가 오른쪽 자식인 경우
        current = current->parent;           // 부모 노드로 이동 후 이어서 탐색
      else
        return current->parent; // current가 왼쪽 자식인 경우 부모 리턴
    }
  }
  while (current->left != t->nil) // 왼쪽 자식이 있으면
    current = current->left;      // 왼쪽 끝으로 이동
  return current;
}