이진 탐색 트리가 한쪽으로 늘어지지 않도록 스스로 모양을 고치는 변종. 평범한 탐색 트리는 평균 O(log N)이지만 최악에 O(N)이고, 그 최악이 정렬된 데이터를 순서대로 넣는 흔한 상황에서 나온다. 균형 트리는 삽입과 삭제 때마다 높이를 log N으로 되돌려 최악에도 O(log N)을 보장한다.
회전으로 높이 줄이기
회전(rotation)이다. 부모와 자녀의 위치를 바꿔 한쪽으로 쏠린 무게를 반대편으로 옮긴다. 탐색 트리의 순서 규칙은 그대로 유지되면서 높이만 줄어든다. 언제 회전할지를 무엇으로 판단하느냐에서 종류가 갈린다.
AVL 트리
각 노드가 balance factor를 들고 있다. 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이다. 이 값이 -1, 0, 1을 벗어나면 그 자리에서 회전한다.
레드-블랙 트리
노드마다 빨강 아니면 검정 색을 칠하고, 색에 관한 규칙으로 균형을 간접적으로 맞춘다. 균형 조건이 AVL만큼 빡빡하지 않아 회전이 덜 일어나고, 그래서 실무 라이브러리는 대부분 이쪽을 쓴다.
회전 빈도와 자바의 선택
AVL은 균형 조건이 엄격해서 높이가 가장 낮게 유지되고 검색이 빠르다. 대신 삽입과 삭제 때 회전이 자주 일어난다. 레드-블랙은 높이가 조금 더 높을 수 있지만 삽입과 삭제가 빠르다.
자바에서 TreeMap과 TreeSet이 레드-블랙 트리다. 키가 정렬된 채로 유지되는 것이 이 때문이다. HashMap도 한 버킷에 값이 몰리면 그 버킷만 레드-블랙 트리로 바꾼다. 그 조건과 임계값은 해시 충돌에 적어두었다.