결국 원소 검색의 시간 복잡도를 최적화하려면 트리의 높이가 최적화되어야 합니다. 이러한 작업을 트리의 균형 잡기라고 합니다. 트리의 균형을 잡기 위해서는 원소 삽입 또는 삭제 후에 트리 구성을 조정해야 합니다. 이렇게 조정되어 편향성이 줄어든 이진 검색 트리를 높이-균형 BST(height-balanced BST)라고 합니다.

트리의 균형을 잡는 방법은 여러 가지가 있으며, 이를 통해 AVL 트리, 레드-블랙 트리(Red-Black tree) 같은 다양한 트리를 만들 수 있습니다. AVL 트리의 기본 아이디어는 BST 속성을 유지하면서 트리 높이의 균형을 잡기 위해 약간의 회전을 수행하는 것입니다. 트리 회전의 예를 그림 2-13에 나타냈습니다.

▲ 그림 2-13 트리 회전하기

이 그림에서 오른쪽 트리가 왼쪽 트리보다 더 균형이 잡힌 상태입니다. 자세한 트리 회전 방법은 이 책의 범위를 벗어나므로 추가 설명은 생략합니다.