미새문지

다 완성 못하고 발표하기엔 너무 아쉬워서 밤새면서 버텼다. 팀원 한 분은 삽입, 회전, minmax를 하셨고 한 분은 전체적인 rb트리 틀과 배열을 맡았다. 본인은 탐색과 삭제에 연관되있는 함수들을 구현했다. rb트리 생성 // 트리 생성 rbtree *new_rbtree(void) { rbtree *p = (rbtree *)calloc(1, sizeof(rbtree)); if (!p) { // 메모리 할당 실패 처리 return NULL; } // 센티넬(가드) 노드를 생성하고 검은색으로 설정 p->nil = (node_t *)calloc(1, sizeof(node_t)); if (!p->nil) { // 메모리 할당 실패 처리 free(p); // 이미 할당된 p 메모리 해제 return NULL; ..

레드-블랙 트리(Red-Black Tree) 자가 균형 이진 탐색 트리(Self Balance Binary Search Tree) RB트리를 만족하기 위한 조건 모든 노드는 빨간색 혹은 검은색이다. 루트 노드는 검은색이다. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 빨간색 노드의 자식은 검은색이다. 빨간색 노드가 연속으로 나올 수 없다. 모든 리프 노드에서 Black Depth는 같다 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 조건 5번 속성을 만족해야 성립하는 개념 노드 x의 black height 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수(자기 자신은 카운트..