탐색 알고리즘(2)

 학습개요

1.  균형 탐색 트리로서 흑적 트리와 B-트리를 이용하는 탐색 방법에 대해서 학습한다. 또한 삽입, 삭제, 탐색 연산을 기본적으로 상수 시간에 수행할 수 있는 해싱 기법에 대해서 살펴본다.

학습목표

• 흑적 트리의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

---

• B-트리의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

---

• 해싱의 개념과 해시 함수 및 충돌 해결 방법의 종류와 특징을 이해할 수 있다.

 

• 흑적 트리?
  • 이진 탐색 트리, 균형 탐색 트리
    • 1. 모든 노드는 흑색이거나 적색이다.
    • 2. 루트 노드와 리프 노드는 흑색이다.
      • 모든 리프 노드는 Null  노드이다.
    • 3. 적색 노드의 부모 노드는 항상 흑색이다.
      • 적색 노드가 연달아 나타날 수 없다.
    • 4. 임의의 노드로부터 리프 노드까지의 경로 상에는 동일한 개수의 흑색 노드가 존재한다
    •  
  • 탐색 연산
    • 이진 탐색과 동일
  • 삽입 연산
    • 탐색이 실패한 Null 노드에 적색 노드를 추가, 두 자식 노드를 Null노드로 만듬
    • 적색 노드가 연달아 나타나면 흑적 트리의 성질을 만족하도록 추가적인 연산을 해야함
      • 1. 부모 노드의 형제 노드가 적색인 경우
        • 부모 노드, 부모 노드의 형제 노드, 부모 노드의 부모 노드의 색깔을 모두 변경
      • 2. 부모 노도의 형제 노드가 흑색이고, 현재 노드의 키값이 부모 노드와 부모 노드의 부모 노드의 키값의 사이인 경우인 경우
        • 현재 노드와 부모 노드를 회전시킴 
      • 3. 부모 노도의 형제 노드가 흑색이고, 현재 노드의 키값보다 부모 노드와 부모 노드의 부모 노드의 키값이 큰(또는 작은) 경우
        • 부모 노드와 부모 노드의 부모 노드를 회전시키고 색깔을 변경
  • 탐색 시간
    • 모든 리프 토드의 깊이가 두 배 이상 차이 나지 않으므로 최악의 트리의 높이는 O(logn)
  • 삽입/삭제 시간 -> O(logn) [균형 탐색 트리는 모두 logn]
  • 사실상 이진 탐색 트리
    • 탐색 연산은 이진 탐색 트리와 동일
    • 삽입 연산은 회전, 색깔 변경과 같은 추가 연산이 필요
  • 2-3-4 트리를 이진 탐색 트리로 표현한 것
• B-트리
  • 균형 탐색 트리
    • 1. 루트 노드는 한 개 이상 2t개 미만의 오름차순으로 정렬된 키를 가짐
    • 2.루트 노드가 아닌 모든 노드는 (t-1)개 이상 2t개 미만의 오름차순으로 정렬된 키를 가짐
    • 3.내부 노드는 자신이 가진 키의 개수보다 하나 더 많은 자식 노드를 가짐
    • 4. 한 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 크 키값보다 크다.
    • 5. 모든 리프 노드의 레벨은 동일
  • 탐색 연산 - 이진 탐색 트리와 마찬가지
  • 삽입 연산
    • 루트 노드에서부터 탐색을 수행, 리프 노드에도 존재하지 않으면 해당 노드에 추가
    • 노드 분할
      • 삽입을 위한 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면, 이 노드를  (t-1)개의 키를 갖는 두 개의 노드로 분할 -> 삽입으로 인해 노드의 키의 개수가 2t개가 되는 것을 방지
  • 성능
    • 탐색, 삽입, 삭제 시간 복잡도
      • 트리의 높이 h, 각 노드에서 키의 위치를 찾는 시간 O(t) -> O(th)
        • 트리의 높이 h -> O(log_t(n))
        • 각 노드에서 키관리에 흑적 트리를 이용하면 t -> O(logt), 
          • O(logtlog_t(n)) = O(logn)
  • 내부 탐색과 외부 탐색에 모두 활용
    • 내부 탐색 (t= 2 또는 3) t=2이면 2-3-4 트리
• 해싱
  • 탐색 키값을 기반으로 데이터의 저장 위치를 직접 계산
    • 상수 시간 내에 데이터를 탐색, 삽입, 삭제 가능
  • 키의 집합 -> 해시 함수 -> 해시 테이블
    • 충돌 ( 키 값은 다른데 같은 값을 가질 경우 발생 )
    • 해시 함수를 잘 만들어서 충돌을 최소화 시켜야하고, 충돌을 어떻게 해결할 지가 중요
  • 해싱의 적합한 적용 : 특정 키값을 갖는 데이터를 찾는 문제
  • 해시 함수 h : U -> {0, 1, ..., M-1}
    • 키 값을 해시 테이블 주소로 변환하는 함수
    • 종류 -> 제산 잔여법, 비닝, 중간 제곱법, 문자열을 위한 함수 등
  • 바람직한 해시 함수는
    • 계산이 용이
    • 각 키값을 테이블의 각 슬로에 균등하게 사상시킬 수 있어야 한다. (충돌 최소화)
  • 해시 함수_제산 잔여법
    • h(K) =KmodM (K: 키값, M: 해시 테이블의 크기)
      • h(123) = 123mod11 = 2
    • M의 선택에 주요
      • M=2^r이면 h(K)는 하위 r비트의 값이 됨
        • 키값의 전체 비트를 주소 계산에 활용하지 못함 
      • M은 2의 멱수와 상당히 차이가 있는 소수로 선택
  • 해시 함수_비닝
    • 키의 집합 U를 단순히 M 등분하여 각 등분을 각 슬로으로 해시
    • 키값의 범위 : 0~999, 해시 테이블 크기 : 10 ->  키값/100 으로 10등분
    • 상위 비트의 분포가 고르지 못하면 몇 개의 슬롯에 집중되는 문제
  • 해시 함수_중간 제곱법
    • h(K) = (K^2/2^m)mod2^r
    • 모든/대부분의 비트가 결과 생성에 기여
      • 상위/하위 자리의 분포에 의해 지배적인 영향을 받지 못함
  • 해시 함수_문자열을 위한 해시 함수(1)
    • M << sum일 때 유용
    • 짧은 문자열에 대해서는 비효과적
    • 뭄ㄴ자열에서 문자의 출현 순서에 무관
  • 충돌 해결 방법
    • 충돌?
      • 서로 다른 키 값x,y에 대하여 h(x)=h(y)인 경우
    • 충돌 해결 방법
      • 개방 해싱 (연쇄법)
        • 테이블의 각 슬롯을 연결 리스트의 헤더로 사용
        • 해시 테이블과 연결 리스트가 주기억장치에 사용될 때 유용
      • 폐쇄 해싱 (개방 주소법)
        • 버킷 해싱 - 오버플로로 보냄 (디스크에 저장된 해시 테이블을 구현하는데 적합)
      • 선형 탐사
        • 탐사 순서
          • 어떤 키 K를 위해서 탐사되는 슬로의 순서열 p(k,i)
          • 탐사 순서의 계산 방법에 따라 성능의 차이가 발생
            • 선형 탐사, 이차 탐사, 이중 해싱
        • 선형 탐사(linear probing)
          • p(K,i) = ( h(K) + i )modM
            • 빈 슬롯을 찾을 때까지 테이블의 바로 다음 슬롯으로 순차적으로 이동
          • 가장 간단한 방법, 하지만 최악의 방법
          • 모든 슬롯이 새로운 데이터를 삽입할 후보가 됨 
          • "1차 클러스터링" 문제 -> 긴 탐사 순서를 만들어 평균 탐색 시간의 증가를 초래
            • 데이터들이 연속된 위치를 점유하여 클러스터를 형성, 이것이 점점 커지는 현상
        • 이차 탐사
          • 탐사 순서의 단계에 대한 이차식을 이용
            • P(K,i ) = (h(K_+ c1*x_i^2 + c2*xi+c3)modM
          • 서로 다른 홈 위치를 갖는 두 키는 서로 다른 탐사 순서를 가짐
          • 모든 슬롯이 탐사 순서에 사용되지 않음
          • 2차 클러스터 문제
            • 서로 다른 두 키의 홈 위치가 동일하면 전체 탐사 순서가 동일
        • 이중 해싱
          • 탐사 순서를 원래의 키 값을 이용하여 계산
            • 1차/2차 클러스터링 문제 해결
          • 서로 다른 두 키의 홈 위치가 동일해도 서로 다른 탐사 순서를 가짐
          • 좋은 이중 해싱을 구현하려면
            • 탐사 순서의 모든 상수가 테이블 크기 M과 서로소가 되어야 함
        • 삭제 연산
          • 두 가지 고려 사항
            • 데이터의 삭제가 차후의 탐색을 방해하지 않아야 한다.
              • 단순히 빈 슬롯을 두면 탐색이 해당 슬롯에서 종료되므로 그 이후의 레코드가 고립된다.
              • 삭제로 인해 해시 테이블의 위치에서 사용할 수 없는 곳을 만들지 않아야 함
            • 비석 tombstone
              • 삭제된 데이터의 위치에 비석이라는 특별한 표시를 하는 방법
                • 탐색 -> 비석을 무시하고 탐색 계속 진행
                • 삽입 -> 비석이 표시된 위치를 빈 위치로 간주, 새 데이터를 삽입하는 방법
              • 비석 개수 증가 -> 평균 탐색 거리 증가 문제

• cf)
  • 균형 탐색 트리(흑적 트리, B-트리)는 경사 트리를 형성하지 않기 때문에 O(logn)이 되지만, 이진 탐색 트리의 최악의 경우에는 경사 트리를 형성하여 O(n)의 시간 복잡도를 갖는다.
  • → 루트 노드는 한 개 이상 2t개 미만의 오름차순으로 정렬된 키를 갖는다.
  • → 모든 리프 노드의 레벨은 동일하다.
  • → 루트 노드가 아닌 모든 노드는 (t-1)개에서 2t개 미만의 오름차순으로 정렬된 키를 갖는다.
  • 개방 해싱(연쇄법)과 폐쇄 해싱(개방 주소법)은 충돌을 해결하기 위한 방법이다. 해시 함수에 해당하는 방법으로는 제산 잔여법, 비닝, 중간 제곱법 등이 있다.

정리하기

• 흑적 트리
  - 이진 탐색 트리로 다음의 성질을 만족하는 균형 탐색 트리
  ① 모든 노드는 흑색이거나 적색이다. 
  ② 루트 노드와 리프 노드는 흑색이다.(→ 모든 리프 노드는 Null 노드이다.) 
  ③ 적색 노드의 부모 노드는 항상 흑색이다.(→ 적색 노드가 연달아 나타나지 않는다.) 
  ④ 임의의 노드로부터 리프 노드까지의 경로 상에는 동일한 개수의 흑색 노드가 존재한다.
  - 탐색 연산 : 이진 탐색 트리의 탐색 방법과 동일
  - 삽입 연산 : 탐색이 실패한 Null 노드에 적색 노드로 추가하고 두 자식 노드를 Null 노드로 만듦 → 이때 적색 노드가 연달아 나타나면 흑적 트리의 성질을 만족하도록 루트 노드쪽으로 올라가면서 노드의 구조와 색깔을 조정하는 추가 연산이 필요
  - 성능 : O(logn)
  - 흑적 트리는 2-3-4 트리를 이진 탐색 트리로 표현한 것 → 2-3-4 트리란 2-노드, 3-노드, 4-노드의 세 가지 종류의 노드로 구성되는 균형 탐색 트리(k-노드는 k-1개의 키와 k개의 자식을 가짐)

---

• B-트리
  - 균형 탐색 트리
  ① 루트 노드는 1 ~ (2t-1)개의 오름차순으로 정렬된 키를 가짐. 
  ② 루트 노드가 아닌 모든 노드는 (t-1) ~ (2t-1)개의 오름차순으로 정렬된 키를 가짐. 
  ③ 내부 노드는 자신이 가진 키의 개수보다 하나 더 많은 자식 노드를 가짐. 
  ④ 한 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 키값보다 크다. 
  ⑤ 모든 리프 노드의 레벨은 동일
  - 탐색 연산 : 이진 탐색 트리와 유사한 방법으로 진행
  - 삽입 연산 : 루트 노드에서부터 탐색을 수행하여 리프 노드에도 존재하지 않으면 해당 노드에 추가 → (노드 분할) 삽입을 위한 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면 이 노드에서 t번째 키는 부모 노도로 이동시키고 나머지는 키들은 (t-1)개의 키를 갖는 2개의 노드로 분할한다.
  - 성능 : O(logn)
  - 내부 탐색과 외부 탐색에 모두 활용

---

• 해싱
  - 배열에서 인덱스가 주어졌을 때 이를 이용하여 원하는 원소를 상수 시간에 찾듯이, 탐색 키값을 이용하여 데이터가 저장된 테이블의 주소를 직접적으로 계산하여 상수 시간 내에 접근할 수 있는 탐색 방법
  - 해시 함수 : 키값을 해시 테이블 주소로 변환하는 함수 → 종류 : 제산 잔여법, 비닝, 중간제곱법, 문자열을 위한 해시 함수 등
  - 충돌 해결 방법 : 
  → 충돌 : 서로 다른 키값 x, y에 대하여 h(x)=h(y)인 경우
  → 개방 해싱(연쇄법) : 동일한 주소로 해시되는 모든 원소를 연결 리스트 형태로 구성하여 관리하는 방법
  → 폐쇄 해싱(개방 주소법): 테이블 내의 다른 슬롯에 충돌된 데이터를 저장·관리하기 위해서 정해진 방법에 따라 테이블의 다른 위치를 탐사하는 방법 → 종류 : 버킷 해싱, 선형 탐사(1차 클러스터링 문제), 이차 탐사(2차 클러스터링 문제), 이중 해싱
  - 데이터 삭제 : 삭제된 위치에 비석을 둠