트리가 자동으로 균형을 유지하도록 고안된 자기 균형 이진 탐색 트리각 노드를 Red 또는 Black루트는 Black모든 리프는 BlackRed 노드의 자식은 반드시 Black(Red 연속 불가)루트부터 리프까지 Black 노드 수는 동일 → 이를 Black-height 라고함새로 추가 되는 노드의 경우 Red위와 같은 규칙들이 트리의 높이를 최대 2·log₂(n) 수준으로 제한하여 최악 시간복잡도를 O(log n)으로 보장삽입 / 삭제 시 회전 횟수가 작고 안정적메모리 오버헤드가 적음표준 라이브러리 구현에 널리 채택됨c++ : map , set , multimap , multiset새로운 노드가 추가될 때 규칙에 맞춰 균형을 바꾸는데 이걸 회전(Rotation)이라 부른다
