이진 탐색 트리: 순서 규칙이 탐색 경로를 줄이는 원리
이진 탐색 트리는 각 노드의 왼쪽 부분트리에 더 작은 키, 오른쪽 부분트리에 더 큰 키가 놓이도록 유지한다. 비교 한 번으로 어느 쪽에 답이 있을지 결정할 수 있다. 중복 키를 허용한다면 어느 쪽에 넣을지 또는 개수를 저장할지 추가 규칙이 필요하다.
중위 순회하면 키의 정렬 순서를 얻을 수 있다.
정렬 조건은 부분트리 전체에 적용된다
루트가 8이고 왼쪽 자식이 3이라면 3의 오른쪽에 놓인 노드도 8보다 작아야 한다. 부모와 자식 사이만 비교해 모두 맞는다고 전체 트리가 올바른 것은 아니다. 각 경로에서 얻은 상한과 하한을 유지해야 한다.
8을 루트로 두고 3, 10, 6을 넣으면 6은 8보다 작아 왼쪽, 3보다 커 오른쪽으로 간다. 검색도 같은 비교 경로를 따른다. 아래는 중복이 없는 트리의 검색 예다.
def search(root, target_key):
current_node = root
while current_node is not None:
if target_key == current_node.key:
return current_node
if target_key < current_node.key:
current_node = current_node.left
else:
current_node = current_node.right
return None
한 층마다 한 노드를 보므로 시간은 높이 h에 대해 O(h)다. 균형이 좋으면 h=O(log n)이지만 1,2,3,4처럼 정렬된 값을 그대로 넣으면 한쪽으로 긴 사슬이 되어 h=O(n)이다. 이진이라는 이름 자체가 로그 성능을 보장하지 않는다.
삭제는 세 경우로 나뉜다
자식이 없으면 부모 연결을 비우고, 자식이 하나면 그 자식을 대신 연결한다. 자식이 둘이면 오른쪽 부분트리의 최솟값인 중위 후계자나 왼쪽 최댓값을 이용한다. 후계자 키를 옮긴 뒤 그 원래 노드를 삭제하면 순서가 유지된다.
루트 8의 오른쪽 부분트리에 10과 그 왼쪽 9가 있다면 후계자는 9다. 9로 루트 키를 바꾸고 기존 9를 제거할 수 있다. 노드에 키 외의 값이 있으면 항목 전체를 일관되게 옮겨야 하며, 외부 노드 참조가 있는 구현에서는 구조 변경의 계약도 고려해야 한다.
왼쪽→현재→오른쪽의 중위 순회는 키를 정렬 순서로 출력한다. 범위 질의는 경계 밖 부분트리를 건너뛸 수 있어 정확 조회만 하는 해시 테이블과 다른 기능을 제공한다.
AVL이나 레드 블랙 트리는 추가 균형 규칙으로 높이를 제어한다. 일반 이진 탐색 트리를 사용할 때는 입력 순서, 트리 높이, 삭제 후 구조를 점검해야 한다. 순서 불변식이 정확성을 보장하고 높이 관리가 성능을 보장한다는 두 역할을 분리해 보는 것이 좋다.
키 비교는 일관된 순서를 정의해야 한다. 예를 들어 사용자 정의 비교가 A<B, B<C이면서 C<A라고 답하면 트리의 방향 선택에 논리적 모순이 생긴다. 데이터의 정렬 기준은 저장 뒤에도 유지되어야 한다.