왼쪽 서브트리의 모든 값은 root보다 작고 오른쪽은 모두 크므로, "왼쪽 전부 → root → 오른쪽 전부" 순서로 방문하면 자연스럽게 오름차순이 됩니다. 각 서브트리 안에서도 같은 논리가 재귀적으로 성립합니다.

이 성질은 실전 문제에서 자주 활용됩니다. 어떤 트리가 유효한 BST인지 검증할 때 inorder 순회 결과가 오름차순인지 확인하면 되고, k번째로 작은 원소를 찾을 때는 inorder 순회를 k번째까지만 진행하면 됩니다. 정렬되지 않은 배열을 BST에 전부 삽입한 뒤 inorder로 꺼내면 정렬이 되는데, 이것이 tree sort입니다.

치우침을 만드는 대표 입력이 정렬된 데이터입니다. 1, 2, 3, 4를 순서대로 삽입하면 매번 "더 크다" 판정만 나와 모든 노드가 오른쪽 자식으로만 이어집니다. 이미 정렬됐거나 거의 정렬된 데이터는 실무에서 흔한 입력이라, 순진한 BST는 하필 흔한 입력에서 최악이 됩니다.

반대로 삽입 순서가 무작위라면 기대 높이가 O(log n)으로 유지된다는 것이 증명되어 있습니다. 문제는 입력 순서를 통제할 수 없다는 점이고, 그래서 입력 운에 맡기는 대신 트리 스스로 모양을 고치는 자가 균형(self-balancing) 트리가 필요해집니다.

BST의 모든 연산 비용은 결국 "root에서 얼마나 내려가는가", 즉 높이에 비례합니다. n개 노드로 만들 수 있는 이진 트리의 높이는 최소 log₂n(완전 균형)에서 최대 n(한 줄)까지 벌어지므로, 같은 자료구조라도 모양에 따라 백만 개 기준 20번 비교와 백만 번 비교의 차이가 납니다.

실무 자료구조는 이 문제를 이미 해결한 형태로 제공됩니다. C++의 map/set과 Java의 TreeMap은 Red-Black Tree로 구현되어 있고, 데이터베이스 인덱스는 디스크 접근에 맞게 한 노드의 분기 수를 크게 늘린 균형 트리인 B-Tree를 씁니다. 모두 "삽입 순서와 무관하게 높이를 보장한다"는 같은 목표의 변형입니다.

삭제는 자식 수에 따라 세 경우로 나뉩니다. 자식이 없으면 그냥 제거하고, 하나면 그 자식을 끌어올리면 됩니다. 문제는 자식이 둘일 때입니다. 노드를 빼면 두 서브트리가 갈 곳을 잃는데, 아무 노드나 그 자리에 올리면 크기 규칙이 깨집니다.

해법은 삭제할 노드의 successor(오른쪽 서브트리에서 가장 작은 값)나 predecessor(왼쪽 서브트리에서 가장 큰 값)로 자리를 대체하는 것입니다. successor는 왼쪽 서브트리의 모든 값보다 크고 오른쪽 서브트리의 나머지 값보다 작으므로, 그 자리에 놓아도 규칙이 유지됩니다. 그리고 successor는 정의상 왼쪽 자식이 없어서, successor 자신을 원래 자리에서 빼는 일은 다시 쉬운 경우(자식 0개 또는 1개)로 환원됩니다.

"절반씩 줄이는 효과"가 사라진다는 것을 수치로 보면, 균형 트리에서는 비교 한 번마다 후보가 절반이 되어 100만 개 중 하나를 약 20번 만에 찾습니다. 완전히 치우친 트리에서는 비교 한 번에 후보가 하나씩만 줄어 최악 100만 번 비교합니다. 구조는 트리인데 동작은 linked list의 순차 탐색과 같아집니다.

실무에서 이 문제를 직접 겪는 일이 드문 이유는 표준 라이브러리의 트리 자료구조가 모두 자가 균형 트리이기 때문입니다. 다만 순서가 필요 없다면 hash table이 평균 O(1)로 더 빠르므로, "정렬 순서 유지나 범위 검색이 필요한가"가 트리를 선택하는 기준이 됩니다.