이진 탐색 트리에 데이터가 정렬되어 삽입된다고 합시다. 예를 들어 1부터 차례로 6까지 삽입해보면 다음 트리를 완성할 수 있습니다.

▲ 그림 8-8 편향 이진 트리

그림 8-8은 정렬된 데이터가 삽입되었을 때 BST 모습입니다. 각 레벨마다 노드가 하나씩만 있는 편향 이진 트리입니다. 연결 리스트와 같습니다. 삽입, 삭제, 탐색 모두 O(n)입니다. 이처럼 이진 탐색 트리는 치명적인 단점이 있습니다. 이를 보완한 이진 탐색 트리가 다음 장에서 배울 레드 블랙 트리가 포함되는 균형 이진 트리입니다. 균형 이진 트리는 편향 이진 트리가 되지 않도록 자동으로 트리 높이를 낮추어 최악의 경우라도 O(log n)이 되도록 합니다. 다음 장에서 균형 이진 트리 중 가장 널리 쓰는 레드 블랙 트리를 자세히 알아보겠습니다.