일반 이진트리 대신 이진탐색트리를 사용하는 이유는 무엇인가?

정렬된 구조를 유지하여 특정 값을 빠르게 찾기 위해서다. 부모 노드를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 배치하여 탐색 범위를 지속해서 줄인다.

이진탐색트리의 탐색 시간은 트리 높이에 비례한다. 높이가 O(log N)으로 눌려 있을 때만 O(log N)이고, 한쪽으로 기울면 O(N)이 된다. 단순 이진트리는 모든 노드를 확인해야 해 O(N)이 걸린다.

다만 정렬된 데이터가 순서대로 들어오면 한쪽으로 치우친 편향 트리가 된다. 이 경우 선형 탐색과 다를 바 없어 최악의 경우 O(N)으로 성능이 저하된다.

그래서 Red-Black 트리나 AVL 트리처럼 스스로 균형을 맞추는 이진 탐색 트리를 쓴다.