이진 탐색 트리에서 좌우 균형이 잘 맞으면 탐색의 성능이 높고, 이 성능은 탐색 트리의 높이와 밀접한 상관이 있는데 예를 통해 그 관계를 살펴보자. [ 그림 7-44 ] 와 같이 노드가 여덟 개인 이진 탐색 트리에서 65를 탐색하기 위한 비교 연산 횟수를 구해보자.

[ 그림 7-44 ]

(a)에서는 65를 탐색하려면 루트 노드부터 비교 연산을 네 번 수행해야 한다. 반면 (b)에서는 비교 연산을 여덟 번 수행한 후에야 65를 탐색할 수 있다. n개 노드를 가진 이진 탐색 트리에서 비교 연산 횟수는 최소 높이를 가진 경우에는 O(log2n)이 되지만. (b)와 같이 최대 높이를 가진 경우에는 O(n)이 된다. 따라서 이진 탐색 트리가 한쪽으로 치우치지 않고 균형을 이루도록 맞춰주면 탐색 성능을 높일 수 있다. 이러한 원리로 이진 탐색 트리에 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이에 대한 균형 조건을 추가하여 정의한 트리를 균형 이진 트리(Balanced Binary Search Tree) 또는 균형 트리 Balance Tree라 한다. 대표적인 예로 AVL 트리를 살펴보자.