적흑 트리

색이 나타내는 제약

표준 정의에서는 루트를 검정으로 두고 빨강 노드의 자식이 빨강이 되지 않게 한다. 각 노드에서 자손의 빈 말단까지 가는 경로에는 같은 수의 검정 노드가 있어야 한다. 빈 말단도 검정으로 취급한다. 실제로 잎 데이터만 검정이어야 한다는 뜻은 아니다.

균형의 정도

빨강 노드가 연속할 수 없으므로 검정 노드 수가 같은 경로들의 길이가 무제한으로 벌어지지 않는다. 이 제약이 높이를 로그 수준으로 제한한다. 모든 잎의 깊이가 같거나 왼쪽과 오른쪽 부분 트리의 높이 차가 항상 1 이하일 필요는 없다는 점에서 AVL 트리와 조건이 다르다.

삽입과 삭제

키를 넣거나 지우는 기본 작업은 이진 탐색 트리의 순서를 따른다. 그 뒤 깨진 색 조건을 색 변경과 회전으로 복구한다. 회전은 키의 정렬 관계를 보존한다. 색만 붙였다고 균형이 저절로 유지되는 것이 아니므로 연산 뒤 불변식이 만족되는지 확인해야 한다.

어떤 문제를 해결하는가

일반 이진 탐색 트리에 정렬된 키가 계속 들어오면 한쪽으로 긴 경로가 생길 수 있다. 적흑 트리는 입력 순서에 따른 이런 편향을 제한한다. 정렬된 키 순회와 키 탐색이 필요할 때 활용할 수 있으며, 해시 테이블처럼 키의 순서를 무시한 저장 방식과 구분된다.