[자료구조] RBT(Red-Black Tree)에 대해 설명해주세요.

Reference
신입 개발자 기술면접 질문 정리 - 자료구조
레드 블랙 트리란?

💡 RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식 자료구조이며,RBT는 BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어졌습니다. 즉, 일종의 자기 균형 이진 탐색 트리(Self-Balancing BST)입니다.

BST를 기반으로 하기 때문에 당연히 BST의 특징을 모두 갖습니다.노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장합니다. 이러한 NIL들을 leaf node로 간주합니다.모든 노드를 빨간색 또는 검은색으로 색칠하며, 연결된 노드들은 색이 중복되지 않습니다.

RB Tree의 가장 큰 특징은 삽입, 삭제 동안 트리의 모양이 “균형 잡히도록" 각 노드들은 red or black 색상을 가진다는 것인데 검색, 삽입, 삭제 시 Worst Case에서도 모두 O(log n)이 보장되는 자료 구조라 볼 수 있습니다.

(출처: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)