RBtree 개념부터 잡기!

rbtree.h 헤더 파일

#ifndef _RBTREE_H_
//header가 참조가 안됫으면 참조해라
#define _RBTREE_H_
//참조
#include <stddef.h>

typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;
// 숫자를 자동으로 쓸 수 있게 알려준다

typedef int key_t;
// key의 값을 알려준다

/*노드에 뭐가 있냐면~ 
1. 색
2. key값 
3. struct의 주소값
4. 이것을 node_t라고 부른다
*/
typedef struct node_t {

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

/*rebtree에는 루트 노드와 nil의 주소값이 담겨져 있다
*/

typedef struct {
  node_t *root;
  node_t *nil;  // for sentinel 이것은 아무래도 마지막 끝을 얘기하는 것 같다.
} rbtree;

// 새로운 rbtree를 만드는 것
rbtree *new_rbtree(void);
void delete_rbtree(rbtree *);

/* rbtree의 함수
1. 삽입 
2. 찾기
3. 최소값
4. 최대값 
*/ 
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_

rbtree 기초

• 이진탐색트리의 한 종류: 자기보다 작은 것을 왼쪽, 큰 것을 오른쪽으로 올리는 트리
• 스스로의 균형을 잡는 트리 O(logn)이 되도록 해준다

속성

1. 모든 노드는 red 혹은 black

2. 루트 노드는 black
   nil node: 존재하지 않음을 의미하는 노드

3. 모든 leaf노드는 nil 노드가 된다: 모든 nil 노드는 black이 된다

4. red의 자녀들은 black이다

5. 임의의 노드에서 자손의 nil노드 까지 가는 경로들의 black 수는 같다.
   (자기 자신은 제외)
   5-1. black height 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 블랙 수.
   5-2. 색을 바꿔도 5번 속성을 유지. 즉 색에 따라서도 black을 거치는 수는 같다.

삽입

1. rb트리 속성을 만족한 상태
2. BST 방식과 동일
3. 삽입후 RB트리 위반 여부 확인
4. 재조정
5. 삽입하는 노드는 항상 red이다.
   왜 5번처럼 할까? 이유는 nil 노드 두

처음 삽입했을 때

1. red가 된다 nil노드의 색 또한 black으로 고정 된다
2. 루트노드는 black으로 바꿔줘야 된다.

회전

BST특징을 유지 4번속성을 위반한다면, 넘겨주면서 회전을 사용해야 된다.
회전을 어떻게 사용할지가 관건.
1. 색을 바꿔주고 회전을 시킬지
2. 회전 시키고 바꿀지