BST (이진탐색 나무)

• 앞서 배운 이진탐색은 사전에 이미 정렬되어 있음을 가정하였다.
  그렇다면 만약 정렬되지 않은 데이터에 대해서는 어떻게 이진탐색을 할 수 있을까? 만약 정렬을 먼저 수행한 뒤 이진탐색을 하면 효율이 높은 이진탐색에 비해 정렬의 효율이 낮아 효과적인 방법이 아니다.
  -> 이것을 극복하기 위한 방법이 BST이다.

• head부터 시작해 오른쪽이나 왼쪽부터 값을 시작해 다음 값이 해당 값보다 작으면 왼쪽 자식이 되고, 크다면 오른쪽 자식이 된다.

• 노드 구조의 설계이다.
• Left / Right 자식의 값의 맨 왼쪽에 있는 주소를 포인터를 이용하여 가리킨다.

• 조건문에서 탐색하고자 하는 값보다 노드값이 큰 경우 오른쪽 노드는 볼 필요가 없기 때문에 왼쪽 노드로 이동한다.
• 반대로 탐색하고자 하는 값보다 노드값이 작은 경우 왼쪽 노드는 볼 필요가 없기 때문에 오른쪽 노드로 이동한다

BST에서의 삽입함수

• 만약 9라는 값을 탐색하고자 하는데 트리에는 9가 존재하지 않는다. 이때 최종적으로 8이라는 말단 노드에 도착해 더이상 노드가 존재하지 않으므로 Null값을 반환한다. 이를 삽입함수를 통하여 8을 가진 노드의 오른쪽에 9를 삽입한다.

• 삽입함수의 설계
• 탐색을 진행하다가 while문에서 더이상 탐색값을 찾이못하고 NULL값을 반환한다면 새로운 공간을 할당하고 탐색값을 노드로 삽입한다.

BST에서의 삭제함수

• 세가지 경우의 삭제 상황이다
• 파란색은 삭제할 값을 가진 대상 노드, 점선이 없어지고 화살표가 새로 이어진다.

BST 성능 분석

---

문자열 탐색

• 주어진 text string에서 pattern string이 나타나는 위치를 결정하는 문제
  

Brute Force(직선적) 알고리즘

• 위치를 옮겨가면서 일치하는 패턴이 있는지 찾는다 = 완전탐색

• 주로 for문을 중첩시켜서 구현한다.

Rabin-Karp 알고리즘

• Pattern String인 1234를 마치 하나의 숫자로 생각해 2543과 비교한다. 이를 통해 문자열 비교 횟수를 줄일 수 있다.

• 영문이라면 26진법으로 간주 (0~25)
• Hash 함수를 통해 해시값을 변형 후 해시값이 일치한다면 이후에 세부 문자열 비교를 진행한다. 일치하지 않다면 다음 위치로 넘어간다.

• 해시값에 대한 계산은 효율적인 호너 방법을 이용한다.

• Text String과 Pattern String에 대해서 길이 m만큼 하나의 문자로 간주하여 호너 방법을 이용해 미리 해시값을 계산해 놓는다.
• 계산한 해시값들을 비교하면서 일치하면 세부 문자열 비교, 일치하지 않으면 새로운 해시값으로 갱신한다.