왼쪽은 상한을 물려받는다
8의 왼쪽 서브트리는 모두 8보다 작아야 합니다.
BST의 각 노드는 자기 값뿐 아니라 허용 범위를 함께 지킨다
탐색·삽입·삭제는 모두 “이 노드가 들어갈 수 있는 최소·최대 범위”를 좁혀 가는 과정입니다. 대체 노드도 그 범위를 벗어나면 불변식이 깨집니다.
범위가 붙은 BST
8
(-∞, +∞)
3
(-∞, 8)
10
(8, +∞)
1
(-∞, 3)
6
(3, 8)
14
(10, +∞)
오른쪽은 하한을 물려받는다
8의 오른쪽 서브트리는 모두 8보다 커야 합니다.
범위 밖 대체 노드는 금지
값만 가까워도 허용 범위를 벗어나면 중위 순회가 정렬되지 않습니다.
핵심: BST 삭제에서 successor/predecessor를 고르는 이유는 값 대체 후에도 삭제 자리의 범위 계약을 계속 만족시키기 위해서입니다.