[ch 11-2] 이진 탐색 트리

[주제]

- 이진 탐색 트리의 개념

[정의]

- 이진 탐색 트리에는 데이터를 저장하는 규칙이 있음. 그 규칙은 특정 데이터의 위치를 찾는데 사용됨

- 이진 트리 + 데이터의 저장 규칙 = 이진 탐색 트리

[중요]

- 이진 탐색 트리의 노드에 저장된 키(Key)는 유일

- 루트 노드의 키는 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크며,

  오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작음

- 왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

- 왼쪽/오른쪽 서브 트리도 이진 탐색 트리

- 삽입 과정과 탐색 과정은 동일하게 진행

※ 키는 정수 값으로 설정했다는 가정

■ 그림(이진 탐색 트리)

■ 그림(이진 탐색 트리의 데이터 삽입 과정)

- 비교대상이 없을 때까지 내려감

- 비교대상이 없는 때 해당 위치가 저장되는 위치로 결정됨

■ 그림(이진 탐색 트리의 데이터 삭제 과정)

- 삭제 시 상황의 종류

상황 1) 삭제할 노드가 단말 노드인 경우

상황 2) 삭제할 노드가 하나의 자식 노드를(하나의 서브 트리를) 갖는 경우

상황 3) 삭제할 노드가 두 개의 자식 ㅗㄴ드를(두 개의 서브 트리를) 갖는 경우

- 위 그림은 '상황 3'의 경우이며, 삭제할 값을 기준으로 가장 가까운 값이 교체될 후보 값이 됨

- 정수 숫자의 경우 '-1 or +1' 차이나는 값이 가장 가까운 값

- 왼쪽 서브 트리의 가장 큰 값과 오른쪽 서브 트리의 가장 작은 값을 탐색

- 차이가 동일할 경우 최종 결정은 정하기 나름

- 교체된 후보 값은 모든 자식 노드들도 같이 이동됨