이진 탐색 트리가 가지는 문제점을 보완한 트리로 균형 이진 트리(balanced binary tree)가 나왔습니다. 균형 이진 트리에는 AVL 트리, 레드 블랙 트리, B 트리 등 다양한 트리가 있습니다. AVL 트리가 가장 먼저 나왔지만 현재 집합이나 딕셔너리 같은 자료 구조에 쓰는 트리는 레드 블랙 트리이며, 데이터베이스에서 쓰는 트리는 B 트리 혹은 B+ 트리입니다. 이 장에서는 레드 블랙 트리를 다루어 보겠습니다.