[알고리즘 과제] 이진 탐색 트리의 구성, 노드의 삽입과 삭제

1. 이진 탐색 알고리즘(의사 코드)

① 데이터 집합의 중앙값을 선택(이진 탐색 트리에서는 Root 선택)
② 중앙값(Root)과 찾고자 하는 목표값과 비교
③ 목표값이 중앙값(Root)보다 작으면 왼쪽, 크면 오른쪽의 이진 탐색을 수행.
④ 찾고자 하는 데이터가 발견될 때까지 ①~③ 반복

 

2. 이진 탐색 트리 구성 과정

30, 50, 20, 35, 15, 60, 55, 70, 25

 

① 30: Root 노드가 없으므로 30 삽입.

② 50: 30보다 크므로 오른쪽 탐색. 왼쪽에 50 삽입(하위 노드가 없으므로).

③ 20: 30보다 작으므로 왼쪽 탐색. 왼쪽에 20 삽입.

④ 35: 30보다 크므로 오른쪽 탐색. 50보다 작으므로 왼쪽 탐색. 왼쪽에 35 삽입.

⑤ 15: 30보다 작으므로 왼쪽 탐색. 20보다 작으므로 왼쪽 탐색. 왼쪽에 15 삽입.

⑥ 60: 30보다 크므로 오른쪽 탐색. 50보다 크므로 오른쪽 탐색. 오른쪽에 60 삽입.

⑦ 55: 30보다 크므로 오른쪽 탐색. 50보다 크므로 오른쪽 탐색.
      60보다 작으므로 왼쪽 탐색. 왼쪽에 55 삽입.

⑧ 70: 30보다 크므로 오른쪽 탐색. 50보다 크므로 오른쪽 탐색.

      60보다 크므로 오른쪽 탐색. 오른쪽에 70 삽입.

⑨ 25: 30보다 작으므로 왼쪽 탐색. 20보다 크므로 오른쪽 탐색. 오른쪽에 25 삽입.

 

3. 노드 삽입(Insert) 과정

ㄱ. 삽입할 노드: 32

① 32: 30보다 크므로 오른쪽 탐색   ② 32: 50보다 작으로 왼쪽 탐색   ③ 32: 35보다 작으므로 왼쪽 탐색   ④ 하위 노드가 없으므로 32 삽입

 

ㄴ. 삽입할 노드: 19

① 19: 30보다 작으므로 왼쪽 탐색   ② 19: 20보다 작으로 왼쪽 탐색   ③ 19: 15보다 크므로 오른쪽 탐색   ④ 하위 노드가 없으므로 19 삽입

 

 

3. 노드 삭제(Delete) 과정

ㄱ. 삭제할 노드: 60

	① 60: 30보다 크므로 오른쪽 탐색   ② 60: 50보다 크으로 오른쪽 탐색   ③ 60 삭제
	④ 삭제된 노드 60의 오른쪽 서브 트리 내에서 최소값인 70을 기존 60의 자리로 이동

 

ㄴ. 삭제할 노드: 50

	① 50: 30보다 크므로 오른쪽 탐색   ② 50 삭제
	③ 삭제된 노드 50의 오른쪽 서브 트리 내에서 최소값인 55를 기존 50의 자리로 이동

 

ㄷ. 삭제할 노드: 30

	① 30 삭제
	② 삭제된 노드 30의 오른쪽 서브 트리 내에서 최소값인 35를 기존 30의 자리로 이동