이진 탐색 트리가 가지는 문제점이 무엇이었습니까? 데이터가 정렬된 상태로 들어오면 각 레벨마다 노드를 하나씩만 가져 결국 연결 리스트가 되는 것이었죠. 이를 해결하려면 어떻게 하면 될까요?

다음 그림과 같은 간단한 발상을 할 수 있습니다.

▲ 그림 9-1 균형을 맞추는 간단한 아이디어

그림 9-1을 보면 키 1이 들어오고 키 2가 들어와 오른쪽 자식이 되었을 때 키 3이 들어오면 이진 탐색 트리일 경우 키 3이 키 2의 오른쪽 자식이 되어 편향 이진 트리가 되어야 합니다. 하지만 어떤 알고리즘을 이용해서 노드 2가 회전(rotation)하여 노드 1이 노드 2의 왼쪽 자식이 되고 노드 3이 노드 2의 오른쪽 자식이 된다면 균형이 맞추어진 트리가 될 것입니다. AVL 트리나 레드 블랙 트리도 알고리즘은 다르지만 기본적인 발상은 이와 같습니다. 특정 상황에서 회전을 하여 트리 균형을 맞추게 됩니다.