RB tree는 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)의 한 종류로, 검색, 삽입, 삭제 등의 동작을 최악의 경우에도 O(log n) 내에 처리할 수 있도록 설계되었다. RB tree는 각 노드가 빨강 또는 검정의 색깔을 가지며, root부터 leaf(NIL)까지의 모든 경로에 대해 블랙 노드의 수가 동일하게 유지되도록 규칙을 적용하여 균형을 맞춘다. RB tree를 사용하는 이유는 데이터의 삽입, 삭제, 검색 작업 시 '항상 균형 상태를 유지'함으로써, 트리의 높이가 최소한으로 유지되어 효율적인 시간 복잡도를 보장한다. Binary Search Tree란, 정렬된(ordered, or sorted) binary tree이며 노드는 2개의 서브트리를 가질 ..
