이진검색 / 해싱해싱/ 균형이진탐색트리(열혈강의 책)

이진검색을 보자..(이거 logn)

미리 정렬된 자료를 대상으로 검색 범위를 반으로 감소시키는 과정을 반복하여 검색 키를 찾는다.

여기서 이진은 검색을 반씩 줄이기 때문이다..

이분검색이라는건...시작위치 + 마지막 위치 / 2 로 소수점은 버리고 정수만을 취한다.

재귀에 의한 구현

int binarySearchRecursive(int value[], int start, int end, int key)

{

int ret = 0;

int middle = 0;

if (start <= end)

{

middle = (start + end) / 2;

if (key == value[middle])

{

ret = middle;

}

else if (key < value[middle])

{

ret = binarySearchRecursive(value, start, middle - 1, key);

}

else

{

ret = binarySearchRecursive(value, middle + 1, end, key);

}

}

return ret;

}

반복에 의한 구현

int binarySearch(int value[], int start, int end, int key)

{

int ret = 0;

int tempStart = 0, tempEnd = 0;

int middle = 0;

tempStart = start;

tempEnd = end;

while (tempStart <= tempEnd)

{

middle = (tempStart + tempEnd) / 2;

if (key == value[middle])

{

ret = middle;

break;

}

else if (key < value[middle])

{

tempEnd = middle - 1;

}

else

{

tempStart = middle + 1;

}

}

return ret;

}

---

해싱은 검색 키에 대한 산술 연산을 이용한 검색 방식이다.

이진검색은 검색 키 갑소가 실제 자료들의 키 값을 하나하나 비교하여 자료를 찾는 비교 검색 방법이었다면

해싱은 검색 키값 만으로 원하는 자료의 위치를 직접 계산할 수 있다는 점이 다르다!

해싱함수에서 쓸 수 있는 방법!

1. 나머지 연산

해싱함수에서 쓸 수 있는 나머지 연산은 테이블의 크기가 소수인 경우 충돌 발생 빈도가 낮아지고 해시 테이블 사용률이 증가하는 특성이 있다.

2. 접기 함수!

1234512345 (10자리)

해시 테이블 크기 999 (3자리)

각각 3자리씩 끊는다 123 / 451 / 234 / 5 

이걸 다 더해봐 그럼 813 나옴..이게 값임..

오오 경계접기도 있다 경계 접기는

분할된 부분들 사이의 이웃한 부분을 거꾸로 뒤집는거임..

123 / 451 / 234 / 5 를.. 321 / 451 / 432 / 5가 되고..다 더하면 1209인데 여기서 1은 버리낟..

문자열일때는 알지? 

각 인덱스 와 문자열 수 곱하는거...근데 재수없으면 오버플로우가 될 수도 있으니까...이게 호너의 방법이란다..

충돌되었을떄 해결법!!

1. 개방 주소법! (그냥 ...옆주소 살펴보고 들어가는거 별로 안좋아)

선형이 있고 제곱이 있고// 이중 해싱도 여기 포함되

2. 체이닝(해시 테이블의 구조를 변경한다)

---

이진검색은 미리 정렬된 자료를 대상으로 배열로 하는건데..이건 원소의 삽입과 삭제할때 모두 이동해야해서 문제다..

이진검색은 O(logn)인데..반면에 이진탐색트리는 트리의 상태에 따라 검색의 시간 복잡도가 다르다는 특성이 있다.

균형트리라면 logn인데..불균형이라면 O(n)이 될 수도 있어...

AVL 균형 이진탐색 트리는..

각 노드의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이의 차이가 1이하인 이진 탐색 트리가 AVL트리이다.

항상 균형 상태가 유지되도록 보장하니까 검색은 logn이다

여기서 균형인수는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값을 말한다.(시발 진짜..1개가 있으면 높이는 1이다..0이 아니라)

균형인수는 -1 0 1 중에 하나가 되야한다..

AVL에서 보통 균형이 꺠지는 경우는 삽입이나 삭제할때 발생된다. 그래서 이때 조정을 해주는거다

시발 LLRR LR RL 아우

LL은 왼쪽에 왼쪽 박았더니 틀어지는거고

RR은 오른쪽에 오른쪽 박았더니 트렁지고

LR은 왼쪽에 오른쪽 박으니 틀어지고

RL은 오른쪽에 왼쪽 박으니 틀어진거다 시발넘아!!!

회전은 LL은 오른회전인데 이게 뭐냐면 가운데 부모가 오른쪽으로 올라가고 해당 노드가 핸들처럼 회전한다고 보면 쉬운듯..

RR은 왼쪽인데 부모가 왼쪽위로 올라가고

시발빌시발비ㅏㄹ

그리고 추가되면 추가된 노드의 부모 노드의 높이와 균형 인수 값을 다시 계산하고 물론 추가된 노드의 모든 선조 노드에 대해 이러한 높이와 균형 인수값의 재계산이 필요해 ㅅㅂ

말단노드부터 루트까지 간다!

시발...ㅠ 근데 이거 자료가 증가하면 트리의 높이가 같이 높아져서 문제가되.. 그리고 상당한 자료가 있는데 자료의 추가나 삭제가 빈번해져봐 그럼 망하는거야

균형유지를 계속 해야하는데 으어..

---

야 다원 탐색 트리다 이건 균형이진탐색트리의 높이문제와 높은 균형유지비용 문제를 해결한다.

B tree다

특징은..

B - Tree 규칙.2

1. Root 노도는 적어도 2개 이상의 자식을 가져야 한다.

2. Root 노드를 제외한 모든 노드는 적어도 floor(M/2) [<= 내림] 개의 자료를 가지고 있어야 한다.

( 위 그림에서는 노드들이 모두 적어도 2개 이상의 자료를 가지고 있다

3. 외부 노드(leaf node) 로 가는 경로의 길이는 모두 같다

4. 입력자료는 중복될 수 없다.( list 등을 같이 쓰면 중복을 허용 할 수도 있다 )

1. 각 노드는 0에서 최대 m개의 서브트리를 가진다.

2. k개의 서브트리를 가지는 노드는 (k - 1)개의 자료를 가진다 k <= m

3. 각 노드 안에서 자료들은 검색 키에 의해 정렬된다.

keyi <= (i번째 서브트리 내의 모든 키 값) < key( i + 1)

서브트리 key k1 서브트리 key k2 서브트리..

M 차 => 한 노드에 자료가 가장 많이 들어간 수의 차수를 말한다

루트 노드는 단말 노드이거나, 2에서  m개의 서브트리를 가진다

루트 노드를 제외한 모든 내부노드는 아래 개수만큼 서브트리를 가진다.

m / 2 <= 서브트리의 개수 <= m    루트노드를 제외한 모든 노드는 적어도 (차수M/2)(소수점엔 내림적용)개의 자료를 가지고 있어야 한다.

단말노드는 아래 개수만큼 자료를 가진다

m/2 - 1 <= 자료의 개수 <= m - 1    루트노드를 제외한 모든 노드는 적어도 (차수M/2)(소수점엔 내림적용)개의 자료를 가지고 있어야 한다.

모든 단말 노드는 같은 레벨이다. 즉, 트리는 완전한 균형 상태에 있도록 한다.

b- 트리에서 새로운 자료를 추가하는 연산에 대해 알아보도록 하자.

1. 저장위치찾기, 2. 자료 저장과 (필요하다면) 노드분할

현재 비교하는 자료의 키 값보다 더 작으면 서브트리로 내려가서 탐색을 계속한다. 이러한 탐색의 특성으로 결국 새로운 자료의 저장은 말단 노드에서만 가능하다..

노드 분할은 말이야..

먼저 분할전에 새로운 키 값을 노드에 추가해..m = 5일때 최대는 4인데 일단 저장해봐..그럼 5개가 저장되지?

여기서 노드의 중간값을 기준으로 기존노드를 2개로 분할하고 중간값을 가지는 자료는 부모 노드로 올려보낸다..

근데 만약에..기존 노드가 루트노드라면..더 이상 올려보낼 부모노드가 없잖냐...이렇게 올려보낼수없을때는..새로운 루트노드를 만들어서 추가한다.

결국 중간값은 새로운 루트 노드로 되고..그리고 그 노드는 루트 노드의 첫 번째 위치에 저장하게 된다. 그 저장된 중간값의 왼쪽 서브트리는 앞서 분할된 왼쪽이 되고

오른쪽 서브는 분할된 오른쪽이 된다. 

근데 만약에 분할에 의해 부모노드로 올라갔는데 거기도 꽉차서 또 분할해야하면..?똑같이하면됨..또 중간값을 찾아서 부모로 올라감..

삭제도 볼까? 삭제도

1. 저장위치 찾기 2. 자료삭제와 3. 필요한 경우 균형유지로 되어있다.

자료의 제거는 트리의 균형을 유지하기 위해서 모두 말단 노드에서만 발생하도록 한다.

만약 제거하려는 자료가 발견된 위치가 말단 노드이면 단순히 해당 자료만 삭제하면 끝임..

근데 말단이 아니라 내부라면..삭제하려는 자료를 대체할 자료를 말단노드에서 찾아야한다..

이제 균형유지인데..균형 유지를 위해서는 위에 있는 서브트리의 개수와 자료의 개수를 지켜줘야한다.(최소 최대기준)

m = 5인 경우에는 루트 노드가 아닌 가 ㄱ노드는 최소한 2개의 자료를 저장해야한다. 

균형유지는 1. 왼쪽에서 빌리기 2) 오른쪽에서 빌리기 3) 병합 이 단계다.

자료개수 부족이 발생한 상황에 적합한 연산을 수행하면된다. !!

자료의 위치와 대소관계를 잘 확인하면 되는데..

어쨌든 빌려주려면 빌려주려는 노드도 조건이 있는데 최소한 3개의 자료를 가지는 노드여야 한다는것..(이건 단말노드에만 해당된다)

중간노드가 1개이고 뿌리를 내려도 상관없다는것..(아 쉬발 이게 아니네..균형이 안맞느다고하네...이것도..)

만약에 왼쪽 오른쪽 둘다 여유가 없으면 병합들어간다.