[자료구조] 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리 (Binary Search Tree)

• 특정 키 값에 해당하는 노드를 빠르게 찾는 것이 주된 기능
• 효율적인 자료 검색이 목적

 

조건

1. 모든 노드는 유일한 키를 가짐(중복x)
2. 왼쪽 서브트리 노드들 키 값 < 루트 노드 키 값
3. 오른쪽 서브트리 노드들 키 값 > 루트 노드 키 값
4. 왼쪽, 오른쪽 서브트리 = 이진 탐색 트리

=> 왼쪽 서브트리 키 < 루트 노드 키 < 오른쪽 서브트리 키 => 중위 순회(InOrder) 방식으로 나열하면 키 값 크기대로 나열됨

​

1. 검색 연산

1. 입력 값 < 현재 노드 값 : 왼쪽 서브트리로 이동
2. 입력 값 > 현재 노드 값 : 오른쪽 서브트리로 이동
3. 입력 값 = 현재 노드 값 : 검색 완료!

​

2. 삽입 연산

1. 입력 값 < 현재 노드 값 : 왼쪽 서브트리로 이동
2. 입력 값 > 현재 노드 값 : 오른쪽 서브트리로 이동
3. 현재 노드가 단말 노드인 경우 => 비교 후 왼쪽 혹은 오른쪽 자식 노드로 삽입!

​

3. 삭제 연산

1) 삭제 노드의 자식 노드가 0개인 경우 (단말 노드인 경우)

• 부모 노드와의 연결만 끊어버리면 됨

​

2) 삭제 노드의 자식 노드가 1개인 경우

• 삭제 노드의 자식 노드를 삭제 노드의 부모 노드와 연결 시킨다.
• ex) 22(자식) - 24(삭제) - 21(부모) => 22 - 21

​

3) 삭제 노드의 자식 노드가 2개인 경우

• 대체 노드 : 왼쪽 서브트리 최대값 vs 오른쪽 서브트리 최소값

​

[CASE 1] 대체 노드 : 왼쪽 서브트리 최대값

• 왼쪽 서브트리 중 최대값이므로 오른쪽 자식 노드가 없음!
• 대체 노드의 왼쪽 자식 노드를 대체 노드의 부모 노드와 링크 시킴
• 대체 노드는 삭제 노드 위치로 이동

​

[CASE 2] 대체 노드 : 오른쪽 서브트리 최소값

• 오른쪽 서브트리 중 최소값이므로 왼쪽 자식 노드가 없음!
• 대체 노드의 오른쪽 자식 노드를 대체 노드의 부모 노드와 링크 시킴
• 대체 노드는 삭제 노드 위치로 이동