[C 언어] RBTree 노드 / 후계자 / 최소,최대 탐색 구현

✔️ RBTree 이론 보고 오기 => 클릭

✔️ RBTree 구현 정리 노션 => 클릭

✔️ RBTree 구현 전체 코드 => 클릭

🎄 key 탐색

• ptr = tree_find(tree, key)
  => RB tree내에 해당 key가 있는지 탐색하여 있으면 해당 node pointer 반환
  => 해당하는 node가 없으면 NULL 반환

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

// 4-1. 주어진 키 값에 해당하는 노드를 탐색하여 반환하는 함수
node_t *rbtree_find(const rbtree *t, const key_t key) {
  node_t *p = t->root; // 루트 노드부터 탐색 시작

  // 노드가 nil이 아닌 동안 반복
  while(p != t->nil) {
    // 현재 노드의 키 값과 찾고자 하는 키 값을 비교
    if(p->key == key)
      return p; // 키 값이 일치하는 경우 해당 노드를 반환
    else if(p->key > key) // 찾고자 하는 키 값이 현재 노드의 키 값보다 작은 경우
      p = p->left; // 현재 노드의 왼쪽 자식으로 이동
    else // 찾고자 하는 키 값이 현재 노드의 키 값보다 큰 경우
      p = p-> right; // 현재 노드의 오른쪽 자식으로 이동
  }

  return NULL; // 키 값을 가진 노드가 없는 경우
}

🎄 후계자 탐색

• 후계자 탐색은 주어진 노드의 다음으로 큰 값을 가진 노드를 찾는 과정
• RB 트리에서는 후계자를 찾는 방법은 해당 노드의 오른쪽 자식 노드 중에서 가장 작은 값을 가진 노드를 찾는 것
• 후계자를 찾기 위해 주어진 노드의 오른쪽 자식 노드부터 시작하여 가장 작은 값을 가진 노드를 찾는다.
• 이 과정은 오른쪽 자식의 왼쪽 자식 노드가 nil이 될 때까지 반복

// 4-2. 주어진 노드의 다음 노드를 반환하는 함수 (후계자 찾기)
node_t *rbtree_successor(rbtree *t, node_t *x) {
    // 현재 노드의 왼쪽 자식이 nil이 아닌 동안 반복하여 탐색
    while(x->left != t->nil) {
      x = x->left; // 현재 노드의 왼쪽 자식으로 이동
    }
    return x; // 가장 왼쪽 자식 노드를 반환
}

🎄 최소값/최대값 탐색

ptr = tree_min(tree): RB tree 중 최소 값을 가진 node pointer 반환
ptr = tree_max(tree): 최대값을 가진 node pointer 반환

• 최소값은 트리에서 가장 왼쪽 자식에 위치한 노드
• 최대값은 트리에서 가장 오른쪽 자식에 위치한 노드

// 4-3. 트리에서 최소값을 가진 노드를 탐색하여 반환하는 함수
node_t *rbtree_min(const rbtree *t) {
  node_t* x = t->root; // 루트 노드부터 시작

  // 현재 노드의 왼쪽 자식이 nil일때까지
  while(x->left != t->nil) {
    x = x->left; // 현재 노드의 왼쪽 자식으로 이동
  }
  return x; 
}

// 4-4. 트리에서 최대값을 가진 노드를 탐색하여 반환하는 함수
node_t *rbtree_max(const rbtree *t) {
  node_t* x = t->root; // 루트 노드부터 시작

  // 현재 노드의 오른쪽 자식이 nil일때까지
  while(x->right != t->nil) {
    x = x->right; // 현재 노드의 오른쪽 자식으로 이동
  }
  return x;
}