[자료구조] ch13. 탐색

• *시험 : 교재문제+ 교수님이 올려주신 기출문제

13.1 탐색이란? 

• 탐색: 기본적으로 여러 개의 자료 중 원하는 자료를 찾는 작업- 탐색키와 데이터로 이루어진 여러 개의 항목 중 원하는 탐색키 갖고 있는 항목 찾는 것
  • 사용되는 자료구조 : 배열, 연결리스트, 트리, 그래프 .......
    • 가장 기초적인 방법: 배열 사용하여 자료 저장하고 찾기, but 탐색성능을 향상하고자 한다: 이진트리처럼 보다 진보된 방법으로 자료를 저장하고 찾아야 한다.
  • 탐색의 단위 : 항목(숫자 or 구조체...) - 항목과 항목을 구별시켜주는 탐색키 존재

 

13.2 정렬되지 않은 배열에서의 탐색

• 순차탐색 : 탐색 방법 중 가장 간단하고 직접적인 탐색방법. 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목 찾기
  • 탐색의 대상이 되는 배열 : list[]. 탐색의 범위: low~high까지 함수의 매개변수 - 탐색에 성공하면 그 항목이 발견된 위치 반환, 그렇지 않으면 -1반환.

• 개선된 순차탐색
• 순차탐색에서 비교횟수 줄이는 방법 : 프로그램 13.1에서 리스트 전체를 탐색하기 위한  반복문에서 리스트의 끝을 테스트하는 비교연산이 있고 반복문 안에 키 값의 비교연산 있음 --> 리스트 끝을 테스트하는 비교연산을 줄이기 위해 리스트의 끝에 찾고자 하는 키 값 저장, 반복문의 탈출 조건을 키 값 찾을때까지로 설정하기
• i값이 리스트의 끝에 도달했는지를 매번 비교하지 않아도 된다.

• 순차탐색의 시간복잡도
  • 탐색이 성공하는 경우 : 리스트에 있는 키 위치에 따라 비교횟수 결정, 모든 키가 탐색될 확률 동일하다 가정하면 평균 비교횟수: (1+2+3+...+n)/n=(n+1)/2
  • 따라서 탐색에 성공할 경우 평균 (n+1)/2 비교, 탐색이 실패한 경우 n번 비교 -> 시간복잡도는 O(n)

 

13.3 정렬된 배열에서의 탐색

• 배열이 많은 항목을 가질 때 순차탐색은 매우 비효율

 

• 정렬된 배열에서의 이진 탐색
  • 이진탐색: 배열의 중앙에 있는 값을 조사해서 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄임 -> 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄임

• 비교가 이루어질때마다 범위가 급격히 줄어듦(찾고자 하는 항목이 속해있지 않은 부분은 전혀 고려할 필요 x
• 이진탐색 적용하려면 탐색 전 배열이 반드시 정렬되어 있어야 함-> 주로 고정된 데이터에 대한 탐색에 적합

 

• 이진탐색: 탐색을 반복할 때마다 탐색범위를 반으로 줄임 -> 이러한 탐색범위가 더 이상 줄일 수 없는 1이 될 때까지의 탐색횟수 = k라 놨을 때, 표의 마지막 행에서 n/2^k=1이므로

• 정렬된 배열에서의 색인 순차 탐색
  • 색인순차탐색 : 인덱스라 불리는 테이블 사용하여 탐색의 효율 높이는 방법.
    • 인덱스 테이블은 주 자료 리스트에서 일정간격으로 발췌한 자료 갖고 있음. 인덱스 테이블에 m개의 항목 있고, 주 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 주 자료 리스트의 각 n/m번쩨 데이터 갖고있음
      • 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 한다.

인덱스 테이블에서 index[i] <= key < index[i+1]을 만족하는 항목을 찾는다.

• 인덱스 테이블에서 위의 조건을 만족하는 항목으로부터 주 자료 리스트에서 순차탐색 수행
  • 주 자료 리스트에서의 탐색시간을 상당히 줄일 수 o -> 빠른 시간 안에 원하는 항목 발견할 수 있게 해 줌 -> 파일처리, 데이터베이스 등 응용분야에서 많이 사용
• 색인순차탐색 알고리즘의 탐색성능 : 인덱스 테이블의 크기에 좌우. 인덱스 테이블의 크기 줄이면 주 자료 리스트에서의 탐색시간 증가, 테이블 크기 크게하면 인덱스 테이블의 탐색시간 증가. 
  • 인덱스 테이블의 크기: m, 주자료 리스트의 크기: n --> 색인 순차 탐색 복잡도 = O(m+n/m)
    • 색인 순차 탐색에서 데이터 수 증가해서 1차 인덱스 테이블 크기  매우 커지면 2차 인덱스 테이블 사용, 2차 인덱스 테이블은 1차 인덱스 테이블의 인덱스 가리키도록 함 -> 탐색: 2차 인덱스 테이블 탐색 ->  1차 인덱스 -> 주 자료 리스트의 탐색으로 이어진다.
• 보간탐색 : 탐색키가 존재할 위치 예측하여 탐색
  • 이진탐색과 유사하나 리스트를 반이 아닌 불균등하게 분할하여 탐색
  • 탐색위치 결정 : 찾고자 하는 키값과 현재의 low, high위치 값 고려하여 다음과 같이 탐색위치 결정

k=찾고자 하는 키 값. low와 high: 탐색할 범위의 최소, 최대 인덱스 값. 탐색위치를 결정할 때 찾고자 하는 키 값이 있는 곳에 근접하게 되도록 가중치 둠

 

13.4 이진탐색트리

 

• 이진트리와 이진탐색트리는 근본적으로 같은 원리에 의한 탐색구조

<차이점>

이진탐색	이진탐색트리
자료들이 배열에 저장 -> 삽입삭제가 상당히 힘듦(앞뒤의 원소들을 이동시켜야 함	비교적 빠른 시간 안에 삽입과 삭제 끝마칠 수 O

따라서 삽입삭제가 심하지 않은 정적인 자료를 대상으로 이루지는 경우-> 이진탐색 괜찮음 BUT 삽입삭제가 빈번하다면 반드시 이진 탐색 트리를 사용해야함

• 트리가 균형트리일때 복잡도 :

but 이진탐색트리에서의 삽입, 삭제연사은 균형트리 보장 x, 균형트리 아닐때 시간복잡도 : O(n)

>>따라서 균형 유지하는 게 매우중요.  --> 스스로 균형 트리 만드는 탐색트리들을 살펴보자!

 

13.5 AVL트리

• 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이차가 1 이하인 이진탐색트리. 트리가 비균형 상태가 되면 스스로 노드를 재배치하여 균형상태로 만듦 --> 균형트리 항상 보장되어 탐색시간+삽입과 삭제 연산 모두 

  

• 균형인수 = (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이) , 모든 노드의 균형인수가 +-1 이하이면 AVL트리
  • AVL트리의 탐색연산: 일반적인 이진탐색트리와 동일 ->

    

• AVL트리의 삽입연산: 일반적인 이진탐색트리에서 균형상태 깨지는 것-삽입, 삭제연산 시
  • 삽입연산 : 삽입되는 위치에서 루트까지의  경로에 있는 조상노드들의 균형 인수에 영향 ->  새로운 노드의 삽입 후 불균형 상태로 변한 가장 가까운 조상 노드(균형인수가 +-2가 된)들의 서브트리에 대해 다시 균형을 잡아야 한다. --> 새로운 노드부터 균형인수가 +-2가 된 가장 가까운 조상노드까지 회전시키기!

• 균형이 깨지는 4가지 경우

13.6 2-3 트리

• 차수가 2 또는 3인 노드를 갖는 트리. 삽입삭제 알고리즘이 AVL 트리보다 간단
  • 하나의 노드가 2-3개의 자식노드 가짐.
    • 차수가 2인 노드 : 2-노드
      • 일반 이진탐색트리처럼 하나의 데이터 k1, 2개의 자식노드 가짐
    • 차수가 3인 노드 : 3-노드
      • 2개의 데이터 k1, k2와 3개의 자식노드 가짐, 왼쪽 서브트리에 있는 데이터들은 모두 k1보다 작은 값. 중간 서브트리에 있는 값들은 모두 k1보다 크고 k2보다 작음, 오른쪽 데이터들은 모두 k2보다 크다.

• 2-3트리의 삽입연산
  • 2개의 데이터값 저장 가능 -> 2-3트리에 데이터 추가시 노드에 추가할 수 있을때까지 데이터는 추가, 더 이상 저장할 장소가 없는 경우 노드 분리

• 노드가 분리되는 상황
  1. 단말노드를 분리하는 경우

 2. 비단말노드를 분리하는 경우

• 중간값을 다시 부모 노드로 올려보내고 작은 값과 큰 값을 별개의 노드로 분리. 만약 다시 부모 노드에 추가노드를 받을 만한 공간이 없다면 이러한 분리과정이 부모노드에 대하여 되풀이된다.

 

 3. 루트노드를 분리하는 경우

• 이전과정과 비슷, 하지만 루트노드를 분리학[ 되면 새로운 노드가 하나 생기게 되므로 트리의 높이가 하나 증가한다.
  • 새로 만들어지는 노드는 이 트리의 새로운 루트 노드가 된다.(오직 이 경우만 트리의 높이가 증가)

 

13.7 2-3-4 트리

• 하나의 노드가 4개의 자식까지 가질 수 있도록 2-3트리 확장한 것
  • 4-노드 : 4개의 자식을 가질 수 있는 노드, 3개의 데이터를 가질 수 O. 

• 삽입연산 : 2-노드, 3-노드면 간단하게 삽입만 하면 됨, BUT 삽입해야 할 노드가 4-노드이면 '후진분할'이 일어난다.
  • 후진분할 연산 방지 위해 : 삽입 노드 찾는 순회(루트->단말)시 4노드 만나면 미리 분할 수행
    • 2-3트리는 삽입 또는 삭제를 위한 순회(루트-> 단말)와 분할과 합병으로 인한 순회(단말-> 루트) 가 필요
    • --> 2-3-4 트리의 장점 : 삽입을 위해 루트에서 단말 노드로 내려가는 동안 4-노드를 만나면 무조건 분할 -> 단말노드에 도달하게 되면 단말노드의 부모노드는 4-노드가 아니라는 것이 보장 -> 후진이동 막기!