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