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

데이터를 정렬된 상태로 유지하며 탐색, 삽입, 삭제를 빠르게 수행하기 위해서다.

균형이 잡혀 있으면 정렬된 배열의 이진 탐색과 같은 O(log n)이다. 기울면 O(n)이 되어 오히려 느리다. 값의 크기를 비교해 왼쪽 또는 오른쪽 자식으로 이동하며 탐색 범위를 절반씩 줄이기 때문이다.

하지만 데이터가 정렬된 순서로 들어오면 트리가 한쪽으로 치우치는 편향 트리(Skewed Tree)가 된다. 이 경우 시간 복잡도는 O(n)으로 늘어난다.

AVL 트리나 레드-블랙 트리는 스스로 높이를 조절해 편향을 막는다.