정렬된 키를 이진 탐색 트리에 차례대로 넣으면 왜 검색이 느려질 수 있나요?

이진 탐색 트리는 왼쪽 키가 작고 오른쪽 키가 크다는 순서 규칙만 보장할 뿐, 트리 높이가 작다는 보장은 기본적으로 없습니다. 정렬된 키를 순서대로 넣으면 매번 같은 방향의 자식이 생겨 노드가 한 줄로 이어질 수 있습니다. 그러면 검색·삽입·삭제가 방문한 노드 수에 비례해 느려지고, ‘검색 O(log n)’이라는 설명은 높이가 로그 수준이라는 조건이 붙은 경우에만 맞습니다.

균형 보장과 실제 비용을 비교합니다

1, 2, 3, 4를 이진 탐색 트리에 넣으면 1의 오른쪽에 2, 다시 2의 오른쪽에 3이 놓입니다. 4를 찾으려면 네 노드를 차례로 비교해야 하므로 높이는 원소 수에 가까워집니다. 반대로 중간값부터 넣으면 양쪽이 비교적 고르게 나뉩니다. 무작위 삽입의 평균적인 모양이 괜찮을 수 있어도, 입력이 정렬되거나 공격자가 삽입 순서를 정할 수 있다면 최악 사례를 피했다는 보장이 없습니다. 이를 퇴화 트리(degenerate tree) 또는 사슬 형태라고 부릅니다.

키 비교가 일관되고 중복 규칙이 고정돼야 순서 불변식도 유지됩니다. 중복을 왼쪽에 둘지 오른쪽에 둘지, 아니면 개수 필드를 둘지 정하지 않으면 삭제와 검색 결과가 흔들릴 수 있습니다. 또한 비교 함수가 같다고 판단하는 값과 실제 동등성의 기준이 다르면 삽입과 조회가 서로 다른 위치를 보게 됩니다.

균형을 보장할 것인지 선택합니다

정렬된 입력이 충분히 발생하는 서비스라면 삽입·삭제 때 회전이나 재구성을 수행하는 균형 트리를 사용하겠습니다. AVL은 높이를 더 엄격히 제한해 검색에 유리할 수 있지만 갱신 회전이 상대적으로 잦고, Red-Black Tree는 균형 조건을 조금 완화해 갱신과 검색의 균형을 잡습니다. 정적 데이터라면 정렬 배열과 이진 탐색이 더 단순하고 캐시에도 유리할 수 있으며, 갱신이 많으면 균형 트리나 B+tree를 검토합니다.

테스트는 오름차순·내림차순·무작위·중복 입력을 각각 넣고 높이, 비교 횟수, 삽입 지연, 삭제 뒤 순서 불변식을 확인하겠습니다. 노드가 둘의 자식을 가질 수 있다는 사실과 균형 트리라는 사실은 다릅니다. 성능 목표가 최악 지연인지 평균 처리량인지에 따라 자료구조를 선택하고, 라이브러리를 쓴다면 반복자 무효화와 비교자 계약도 확인하겠습니다.

기본 BST에서 높이 h가 검색 비용을 결정하므로, 정렬된 1, 2, 3, 4를 넣은 뒤 4를 찾는 비교 횟수는 균형 트리보다 훨씬 커집니다. 정렬 순서를 지키는 것과 높이를 제한하는 것은 별도 불변식입니다. 중복 키를 왼쪽·오른쪽에 둘지 개수로 합칠지 정하지 않으면 삭제 뒤에도 탐색 경로가 일관되지 않습니다.

정적 데이터는 정렬 배열을 만들어 이진 탐색하는 편이 캐시와 메모리에서 유리할 수 있고, 갱신이 있으면 AVL·Red-Black Tree처럼 회전으로 높이를 관리합니다. 하지만 균형 트리도 노드 할당과 포인터 추적, 비교자 비용을 없애지 않습니다. 오름차순·역순·중복 입력에서 높이와 비교 횟수뿐 아니라 삭제 후 중위 순서, 반복자 계약, 최대 지연을 확인하겠습니다.

정적 BST를 정렬 배열의 중간값부터 구성하면 초기 높이는 작아집니다. 그러나 이후 정렬된 키를 계속 삽입하면 다시 편향될 수 있으므로 초기 균형과 갱신 시 균형 보장을 구분합니다. 회전은 노드 사이 링크를 바꾸되 중위 순서를 보존해야 하며, 각 갱신 뒤 높이와 정렬 순서를 별도로 검사하겠습니다.