"Red Black Tree"(RB Tree)란 이진 검색 트리의 일종으로 자가 균형 이진 검색 트리(Self-Balancing BST)이다. BST의 경우 평균적으로 $O(logN)$에 동작하지만, 최악의 경우 $O(N)$이 소요된다. 최악의 경우는 균형이 무너져 편향트리가 되었을 때 발생한다. 따라서, 최악의 경우에도 $O(logN)$을 보장하는 자가 균형 이진 검색트리인 AVL, Red-Black Tree를 사용한다. 특징 "Red Black Tree"는 다음과 같은 규칙을 만족하는 BST이다.#1: 모든 노드는 빨간색 혹은 검은색이다. #2: 루트노드는 검은색이다.#3: 리프(NIL)노드는 검은색이다. #4: 빨간색 노드의 자식은 검은색이다.  (즉, 2 연속으로 빨간색이 나올 수 없다.)#5: ..