1) 삭제할 노드를 대체할 노드 찾기삭제할 키를 가진 노드인 delete를 삭제하면 해당 노드가 삭제되고, 삭제된 자리에 다른 노드가 채워지게 된다.delete를 대체하면서 사라지는 노드를 'remove', 'remove'의 자식이던 노드를 'replace_node'로 정한다.'replace_node'가 'remove'의 자리를 대체하게 된다.삭제할 노드 'delete'의 양쪽 자식 노드가 모두 존재하는 경우remove : 삭제할 노드의 오른쪽 서브트리에서 가장 작은 노드인 후계자(successor) 노드가 제거된다.replace_node : 후계자 노드의 자식 노드가 remove의 기존 자리를 대체한다. (후계자 노드는 항상 왼쪽 자식이 없으므로 오른쪽 자식 노드 하나만 존재한다.)삭제할 노드 'del..

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){ nod..

key 추가1) 새 노드 생성새 노드를 동적으로 생성한다.노드의 key를 입력받고, color를 RED로, 자식 노드들은 nil 노드로 설정한다.이미 같은 key의 값이 존재해도 하나 더 추가 한다. (multiset)2) 새 노드를 삽입할 위치 탐색루트 노드부터 탐색을 시작하여 탐색 중인 노드보다 key값이 작은 경우 왼쪽 자식으로, 큰 경우 오른쪽 자식으로 이동한다.탐색 중인 노드의 자식 노드가 nil 노드인 경우, 새 노드를 해당 자식 노드로 추가하고, 반복문을 종료한다.반복문 종료 후 새 노드의 부모를 지정한다.💻 새 노드 생성, 위치 탐색 CODE/* 3️⃣ key 추가 */// 노드를 삽입하고 불균형을 복구하는 함수node_t *rbtree_insert(rbtree *t, const key_..

1. Tree 생성1) tree 구조체 동적 할당여러 개의 tree를 생성할 수 있어야 하며 각각 다른 내용들을 저장할 수 있어야 한다.트리의 루트 노드(root)와 nil 노드(nil)를 저장할 수 있는 공간을 가지고 있어야 한다.calloc함수를 통해 메모리 동적 할당하고 값을 0으로 초기화한다.📢 트리의 전체적인 상태와 구조를 정의하는 핵심적인 데이터 구조로, 이를 잘 관리하기 위해 메모리를 동적으로 할당하고, 프로그램이 끝나면 메모리를 해제하는 작업이 중요하다. 2) nil 노드 생성 및 초기화RB tree에서 리프 노드는 'nil 노드'로 표시한다.tree가 빈 경우 root는 nil노드어야 한다.'nil 노드'는 일종의 가상 노드로서, 트리에서 실제로 존재하지 않는 노드이다.일반 노드와는 다..

🔎 Red-Black Tree란?self-balancing binary search tree의 일종이다.각 노드 당 한 비트의 추가 기억 공간을 가지는데, 이 비트는 노드의 색상 정보를 빨간색 또는 검은색으로 저장한다.루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하게 되어 근사적으로 균형을 이룬 트리가 된다.트리를 self-balancing 하게 만들어주어 검색, 삽입, 삭제 연산을 모두 **O(log n)**의 시간 복잡도를 보장하며, 이진 탐색 트리와 달리 최악의 경우에도 균형이 깨지지 않도록 보장한다.unpredictable tree: 삽입 연산이 항상 일정한 속도로 실행되는 것을 보장하지 않는다.🚨 Red-Blac..