[Algorithm] 이진 탐색 트리

이진 탐색 트리: Binary Search Tree

- 각 노드는 유일한 키를 가지고 있음 (distinct keys)

- 왼쪽 서브 트리에 있는 키들은 모두 루트 노드의 키보다 작음

- 오른쪽 서브 트리에 있는 키들은 모두 루트 노드의 키보다 큼

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

BST

• 4, 5는 루트노드인 6보다 작음
• 7은 루트노드인 6보다 큼
• 71은 누트노드인 23보다 큼
• 50은 루트노드인 71보다 작음 (왼쪽에 위치해있기 때문)
• 6은 루트노드인 15보다 작고, 23은 큼

---

BST:: SEARCH(V):

if this == null
	return null
else if this key == search value
	return this
else if this key < search value
	search right
else
	search left

- 예시는 [참고]에 있는 동영상 참고할 것

---

BST:: INSERT(V):

if insertion point is found
	create new vertex
else if value to be inserted < this key
	go left
else
	go right

- 예시는 [참고]에 있는 동영상 참고할 것

---

BST:: REMOVE(V):

search for v

if v is a leaf
	delete leaf v
else if v has 1 child
	bypass v
else
	replace v with successor

- 예시는 [참고]에 있는 동영상 참고할 것

- bypass v: 자식 노드가 1개 밖에 없다면 루트 노드를 삭제하고 그 밑에 있는 자식 노드를 replace 해줌

- replace v with successor: 루트노드보다 더 크면서 그 중에서 제일 작은 수 (왼쪽 끝에 있을 것임) 

---

출처

1. 주니온TV 아무거나연구소 - 6. 이진 탐색 트리 https://www.youtube.com/watch?v=-gSu9s7WeKo&list=PLHqxB9kMLLaNIvuYT6NgXsIt782lS3xiD&index=6