Chap 08. 탐색

탐색 : 데이터를 찾는 방법

탐색이 효율적이기 위해서는 효율적인 '저장방법'을 고려해야한다.

대표적으로 '이진 트리'가 효율적이다.

---

이진 탐색 - 탐색 대상을 반으로 줄여나가면서 탐색
             - '찾는 대상의 위치에 따라 탐색의 효율에 차이가 발생'한다.


이진 탐색의 단점을 보완한 탐색이 보간탐색.

보간 탐색 - 대상에 비례하여 탐색의 위치를 결정

'이진 탐색'보다 '보간 탐색'이 더 효율적이다.

---

<보간 탐색>

내가 찾고자 하는 데이터의 값에따라 탐색위치를 정해준다.

low  : 배열의 시작 인덱스
high : 배열의 마지막 인덱스
s    : 찾고자하는 값의 배열 인덱스

배열의 값들이 정렬되어 있다면,

---

<이진 탐색 트리>

이진 트리에 저장된 데이터의 수가 10억개라면,
거치는 노드의 수는 30을 넘지 않는다.

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

데이터의 저장 규칙 : 작으면 왼쪽, 크면 오른쪽으로 데이터를 삽입한다.

---

[데이터 삽입]

- 새로운 데이터가 비교대상보다 값이 '크면' 오른쪽 '작으면' 왼쪽으로 이동한다.
- 비교대상이 없을 때까지 내려간다. 비교대상이 없다면 그 위치에 저장한다.

---

[데이터 삭제]

- 이진 탐색 트리에서 데이터를 삭제하고나서도 이진 탐색 트리를 유지해야한다.

삭제 대상이 '단말 노드'

삭제 대상이 '자식 노드'가 1개

삭제 대상이 '자식 노드'가 2개