[자료구조] Chap11 검색(탐색)

Chap11 검색(탐색)

선형 검색

• 앞에서부터 하나씩 찾아봄

 

이진 검색

• 절반씩 잘라서 중간값을 탐색해나가는 방법

 

해시 탐색

• 해시테이블(크기 = 버킷*슬롯)
  • 버킷 : 해시될 키 값의 범위. 해시함수에 들어갔다 나온 값이 같으면(동의어) 같은 버킷에 저장됨
  • 슬롯 : 같은 버킷에 저장될 수 있는 키 값 개수
  • 충돌 : 동의어가 나타나서 다른 값이 같은 버킷에 저장되는 경우
  • 오버플로우 : 충돌로 저장하려는 값의 슬롯이 이미 꽉 찬 경우 오버플로우가 일어남
  • 식별자밀도=적재밀도 : 같은 말. 테이블 크기에 비해 저장된 데이터 수 비율을 의미.(키값=식별자=데이터)
• 해시 함수 : 계산이 편해야 하고 충돌을 최소화할 수록 좋음. 
  • mid-square : 식별자를 제곱해서 가운데 부분 값을 사용함
  • division : 나머지 연산자를 이용해 식별자를 M(테이블의 buket범위)로 나눈 나머지 값을 사용함. 이 때 M이 소수인 것이 좋다
  • digit analysis : 키값의 자리수들을 분석해 가장 분포가 고른(충돌이 적은) 자리수를 사용함
  • folding접지법 : 키 값의 각 자리수들을 접거나 이동시켜 조작함
    • 이동 접지법(수를 일정 단위로 끊어 같은 위치로 이동시켜 다 더함), 경계 접지법(수를 일정 단위로 끊어 일부 수를 뒤집음)
• 오버플로우 해결법
  1. 개방 주소법 : 오버플로우가 일어나면 현재 해시테이블 영역 내에서 빈 공간을 찾아 저장함. 빈 공간을 어떻게?
     • 선형조사법 : 해당 버킷의 다음 버킷의 빈 공간에 저장함 - 단점 : 충졸이 한 버킷에 집중하는 경향이 있고 검색 시 오래걸림
     • 2차조사법 : 1의 제곱, 2의제곱, 3의 제곱 순으로 건너뛰며 찾아 새로운 빈 공간에 저장함
  2. 재해싱 : 다른 해시 함수를 사용함
  3. chaining : 테이블을 확장함. 저장공간을 늘림. 연결리스트 활용(연결된 각 연결리스트에 동의어를 저장). 무한정.

 

이진 탐색 트리 BST Binary Search Tree

• 중복값 없음. 왼쪽 부속트리의 모든 값들은 루트보다 작고, 오른쪽은 루트보다 큼.
• 탐색, 삽입, 삭제 시간이 트리의 깊이h에 비례함 O(h)
• 단점 : 최악의 경우 skewed트리가 됨 O(n) -> 완전 이진 트리로 바꿔서 없앨 수 있음 -> 평균,최악 O(logn)

 

균형 이진 트리 Balanced Binary Tree (AVL트리, 높이 균형 이진 트리)

• 평균,최악 O(logn)
• 어느 노드에서 봐도 두 자식 부속트리의 높이 차가 1이하이다.(0이거나 1이다)
• 균형인자 BF(T) : 두 자식 부속트리의 높이 차를 표현. 왼쪽-오른쪽. AVL트리의 모든 노드는 -1, 0, 1이다.
• 균형 트리 만들기
  • 노드를 삽입하거나 삭제했을 때 BF가 +-2가 되어 균형이 깨지는 지점을 찾아 LL, LR, RR, RL회전을 해 맞춘다. (회전은 LL의 경우 왼쪽-왼쪽자식에게 새 노드가 삽입됨의 의미다. LL과 RR은 그대로 회전하고, LR과 RL은 아래 노드를 위로 올리고 위에 있던 깨진 노드를 회전하는 것 같은 느낌 . . . 구분을 . .. -> 그러지 말고 RL은 새 노드가 삽입된 부속 트리의 루트노드를 R회전 한번 시켜서 한단계 위로 올리고, 올린 노드와 깨진 노드가 인접하게 된 부분을 L회전시켜서 균형 맞추는 거라고 하자! 이게 맞는 듯~~)
• 이진트리였을 때보다 완전이진트리에 더 가까운 모양이 됨. 윗부분일수록 노드가 채워져 있음. 
• 삽입 시마다 균형을 맞춰주는 번거로움이 있음

 

B-트리(m-Way 탐색트리의 개선)

• 주로 보조기억장치에 저장된 데이터의 탐색에 이용됨. O(log_m n)

• m-Way 탐색 트리
  • 각 노드에 최대 m개의 자식노드가 있음.
  • 각 노드에 m개의 자식을 가리키는 값과 m-1개의 키값(데이터)이 있음
  • 한 노드 안의 데이터(키값)들은 오름차순 정렬되어있으며 자식을 가리키는 값과 키값이 번갈아 저장되어있음
  • 각 자식노드들은 부모노드에서 그 자식노드를 가리키는 값의 양 옆 키값의 사이값들을 자신의 키값으로 갖는다.. 
  • 각 노드가 모두 m-Way탐색트리이다.
  • 이진 탐색트리 = 이원(2-Way) 탐색트리
  • m값이 클수록 같은 값들을 저장해도 트리의 높이가 낮다. 성능↑
• B-트리 : 다음 조건을 만족하는 m-Way 탐색트리
  • 각 노드는 최대 m개, 최소 m/2개의 종속트리를 가짐. 루트노드는 최소 2개.
  • ★모든 리프노드는 같은 레벨에 위치할 것
  • 노드에 있는 키 값 개수는 최소 m/2 - 1개, 최대 m-1개.