7장 탐색 (2)- 방통대, 알고리즘

학습개요

탐색 알고리즘에 대한 지난 강의에 이어서 이번 시간에는 균형 탐색 트리로서 레드-블랙 트리와 B-트리를 이용하는 탐색 방법에 대해서 학습한다. 또한 삽입, 삭제, 탐색 연산을 기본적으로 상수 시간에 수행할 수 있는 해싱 기법에 대해서 살펴본다.

학습목표

• 레드-블랙 트리의 개념, 동작 그리고 성능과 특징을 이해하고 설명할 수 있다.
• B-트리의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
• 해싱의 개념, 그리고 해시 함수 및 충돌 해결 방법의 종류와 특징을 이해하고 설명할 수 있다.

주요용어

• 레드-블랙 트리(red-black tree)
• - 2-3-4 트리를 이진 탐색 트리 형태로 구현한 것으로서, 검정 노드와 빨강 노드로 구성된 균형 탐색 트리
• B-트리
• - 각 노드에 최대 2t개 미만의 키와 키의 개수보다 하나 더 많은 자식을 가질 수 있는 균형 탐색 트리
• 노드 분할(node split)
• - B-트리에서 삽입을 위한 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면 이 노드를 (t-1)개의 키를 갖는 두 개의 노드와 t번째의 1개의 키로 구성된 하나의 노드로 분할하고, t번째 키를 부모 노드로 이동시키는 연산
• 해시 테이블(hash table)
• - 각 위치마다 주소가 부여된 저장공간으로, 보통 배열 형태로 표현
• 해싱(hashing)
• - 탐색 키값을 기반으로 데이터의 저장위치를 직접 계산함으로써 기본적으로 상수 시간 내에 데이터를 저장, 삭제, 탐색하는 방법
• 해시 함수(hash function)- 제산 잔여법, 중간 제곱법 등 매우 다양한 함수가 존재
• - 주어진 키값을 해시 테이블의 주소를 변환하는 함수
• 충돌(collision)- 충돌 해결 방법으로는 개방 해싱과 폐쇄 해싱(버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱)이 있음
• - 서로 다른 키값이 같은 해시 테이블 주소로 사상되는 현상

정리하기

• 레드-블랙 트리① 모든 노드는 검정이거나 빨강③ 빨강 노드의 부모 노드는 항상 검정 → 빨강 노드가 연달아 나타나지 않음⦁ 탐색 연산 → 이진 탐색 트리의 탐색 방법과 동일- 이때 빨강 노드가 연달아 나타나면 레드-블랙 트리의 성질을 만족하도록 루트 노드쪽으로 올라가면서 노드의 구조와 색깔을 조정하는 추가 연산이 필요 → 이를 위해 3가지 경우로 구분하여 규칙이 적용됨⦁ 레드-블랙 트리는 2-3-4 트리를 이진 탐색 트리로 표현한 것
• ⦁ 성능 → O(logn)
• ⦁ 삽입 연산 → 탐색이 실패한 NULL 노드에 빨강 노드로 추가하고 두 자식 노드를 NULL 노드로 만듦
• ④ 임의의 노드로부터 리프 노드까지의 경로상에는 동일한 개수의 검정 노드가 존재
• ② 루트 노드와 리프 노드는 검정(단, 모든 리프 노드는 NULL 노드)
• ⦁ 이진 탐색 트리로서 다음의 성질을 추가로 만족하는 균형 탐색 트리
• B-트리① 루트 노드는 1 ~ (2t-1)개의 오름차순으로 정렬된 키를 가짐③ 내부 노드는 자신이 가진 키의 개수보다 하나 더 많은 자식 노드를 가짐⑤ 모든 리프 노드의 레벨은 동일⦁ 삽입 연산 → 루트 노드에서부터 탐색을 수행하여 리프 노드에도 존재하지 않으면 해당 노드에 추가⦁ 성능 → O(logn)
• ⦁ 내부 탐색과 외부 탐색에 모두 활용
• - 노드 분할 → 삽입을 위한 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면 이 노드에서 t번째 키는 부모 노도로 이동시키고 나머지는 키들은 (t-1)개의 키를 갖는 2개의 노드로 분할
• ⦁ 탐색 연산 → 이진 탐색 트리와 유사한 방법으로 진행
• ④ 각 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 키값보다 큼
• ② 루트 노드가 아닌 모든 노드는 (t-1) ~ (2t-1)개의 오름차순으로 정렬된 키를 가짐
• ⦁ 균형 탐색 트리
• 해시 테이블⦁ 해시 함수 → 키값을 해시 테이블 주소로 변환하는 함수⦁ 충돌 → 서로 다른 키값 x, y에 대하여 h(x)=h(y)인 경우⦁ 개방 해싱(“연쇄법”) → 충돌된 데이터를 해시 테이블 밖의 별도의 장소에 저장 → 동일한 주소로 해시되는 모든 원소를 연결 리스트 형태로 구성하여 관리하는 방법- 종류 → 버킷 해싱, 선형 탐사(→ 1차 클러스터링 문제), 이차 탐사(→ 2차 클러스터링 문제), 이중 해싱- 탐색 → 탐색하는 동안 비석을 만나면 탐색을 계속 진행
• - 삽입 → 비석이 표시된 위치를 빈 위치로 간주하여 새 데이터를 삽입
• ⦁ 데이터 삭제 → 삭제된 위치에 ‘비석’이라는 특별한 표시를 함
• ⦁ 폐쇄 해싱(“개방 주소법”) → 테이블 내의 다른 슬롯에 충돌된 데이터를 저장·관리하기 위해 정해진 방법에 따라 테이블의 다른 위치를 탐사하는 방법
• ⦁ 충돌 해결 방법 → 개방 해싱, 폐쇄 해싱
• - 종류 → 제산 잔여법, 비닝, 중간 제곱법, 문자열을 위한 해시 함수(비닝, 단순 합, 가중 합) 등 매우 다양
• ⦁ 해싱 → 탐색 키값을 이용하여 데이터가 저장된 테이블의 주소를 직접적으로 계산하여 상수 시간 내에 접근할 수 있는 탐색 방법

---

1. 레드-블랙 트리

이진 탐색 트리, 균형 탐색 트리이다 성질4가지가 존재한다

성질

• 모든 노드는 검정이거나, 빨강이다. 루트 노드와 리프 노드는 검정이다.
• 루트 노드와 리프 노드는 검정이다.
  • 모든 리프 노드는 null 노드이다
• 빨강 노드의 부모 노드는 항상 검정이다.
  • 빨강 노드가 연달아 나타낼 수 없음
• 임의의 노드로부터 리프 노드까지의 경로상에는 동일한 개수의 검정 노드가 존재한다.

탐색연산 - 이진탐색트리의 방법과 동

삽입 연산 - 원소 15

탐색에 실패한 null 노드에 빨강 노드를 추가하고 추가한 노드의 두 자식 노드를 null 로 만듦

이번엔 45 라는 원소를 삽입해보자

먼저 탐색

집어넣은 이후 자식노드 null로 만듦

성질 3번째 위배

• 빨강 노드의 부모 노드는 항상 검정이다.
  • 빨강 노드가 연달아 나타낼 수 없음

루트 노드쪽으로 올라가면서 노드의 구조와 색깔을 조정해서 성질을 만족시켜야 함

빨강 노드가 연달아 나타나는 경우의 규칙

• 부모 노드의 형제 노드가 빨강인 경우
  • 부모 노드, 부모 노드의 형제 노드, 부모 노드의 부모 노드의 색깔을 모두 변경(오타아님 조상맞음, 조부모라고 하겠음)
• 부모 노드의 형제가 검정이고, 현재 노드의 키값이 부모 노드와 조부모 노드의 키값이 사이인 경우
  • 현재 노드와 부모 노드를 회전시킴
• 부모 노드의 형제 노드가 검정이고, 현재 노드의 키값보다 부모노드와 조부모 노드의 키값이 큰(또는 작은)경우
  • 부모 노드와 조부모 노드를 회전시키고 색깔을 변경

경우1 부터 보자

45를 삽입한 직후의 상태이다

부모노드 50, 부모노드의 형제노드가 30, 조부모 노드의 40의 색깔을 변경한다

하지만 이렇게 색을 변경함으로서

경우2를 위배했다

• 부모 노드의 형제가 검정이고, 현재 노드의 키값이 부모 노드와 조부모 노드의 키값이 사이인 경우
  • 현재 노드와 부모 노드를 회전시킴

부모 노드의 60 형제 노드 10이 검정, 현재 노드의 키값 40이 부모 노드 60와 조부모 노드의 20의 키값 사이인 경우

→ 현재 노드 40과 부모 노드 60을 회전 시킴(우회전)

• 부모 노드의 형제 노드가 검정이고, 현재 노드의 키값보다 부모노드와 조부모 노드의 키값이 큰(또는 작은)경우
  • 부모 노드와 조부모 노드를 회전시키고 색깔을 변경

규칙 3 위배

부모 노드 60의 형제 노드 10이 검정, 현재 노드의 키값 60보다 부모 노드 40와 조부모 노드의 20의 키값이 작은 경우

→ 부모 노드 40과 조부모 노드 20을 회전 시키고 색깔 변경

솔직히 이해가 잘 안갈꺼다 필자도 쉽지않았다, 회전이 뭔지 몰랐을 수도 있고 등등 아래링크를 추천드린다 설명 Goat 입니다.

학교 기출문제를 보니 특징을 위주로 시험을 내시더라구요 삽입/삭제는 안다루는것 같습니다(실제로 강의도 삭제는 안다룸)

https://youtu.be/2MdsebfJOyM?si=2YElPNkWy7aO-ABf

어떤 두 리프 노드의 레벨 차이가 2배를 넘지 않는 균형 탐색 트리

특징 탐색, 삽입, 삭제 연산의 시간 복잡도 O(logn)

• 최악의 경우 트리높이 O(logn)
• 사실상 이진 탐색 트리
  • 탐색 연산은 이진 탐색 트리와 동일
  • 삽입 연산은 회전과 색깔 변경과 같은 추가 연산이 필요

2. B-트리

t는 자연수인 상수

• 루트 노드는 1개 이상 2t개 미만의 오름차순으로 정렬된 키를 가짐
• 루트 노드가 아닌 모든 노드는 (t-1)개 이상 2t개 미만의 오름차순으로 정렬된 키를 가짐
• 내부 노드는 자신이 가진 키의 개수보다 하나 더 많은 자식 노드를 가짐
• 각 노드의 한 키의 왼쪽 서브 트리에 있는 모든 키값은 그 키값 보다 작음
• 각 노드의 한 키의 오른쪽서브 트리에 있는 모든 키값은 그 키값 보다 큼
• 모든 리프노드의 레벨은 동일

t = 3인 B-트리

16탐색

루트 노드에서부터 탐색을 수행하여 리프 노드에도 존재하지 않으면 해당 노드에 추가

노드 분할

• 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면, 이 노드를 (t-1)개의 키를 갖는 2개의 노드와 1개의 키를 갖는 노드로 분할
  • 삽입으로 인해 노드의 키의 개수가 2t개가 되는 것 방지

2-3-4 트리 연장선이네요

탐색, 삽입, 삭제 연산의 시간 복잡도 → O(logn)

• 트리의 높이 h, 각 노드에서 키의 위치를 찾는 시간 O(t) → O(th)
  • 각 노드 → 키의 개수 : (t-1) ~ (2t-1) 개, 자식 노드의 개수 : t~2t개
  • 모든 리프 노드의 레벨은 동일
  • 성능 → O(logn)
  • 내부 탐색과 외부 탐색에 모두 활용

3. 해시테이블

키값을 기반으로 데이터의 저장 위치를 직접 계산함으로써 상수시간 내에 데이터를 저장, 삭제, 탐색할 수 있는 방법

오른쪽의 표가 해시테이블로서

• 각위치마다 주소가 부여되어있는 저장 공간
• 배열 형태

각 위치는 슬롯이라고 부름

해키의 키의 집합은 엄청키고 해시테이블이 작다면 위의 사진처럼 키가 같은 테이블의 주소를 참조하고 있는걸 볼 수 있다

이러한 ‘충돌문제’해결을 뒤에서 배운다

해싱이 적합한 형태의 응용 문제는?

1. 동일한 키값을 가진 여러개의 데이터가 존재하는 응용
2. 어떤 범위에 속하는 키값을 가진 모든 데이터를 탐색하는 문제
3. 최대 또는 최소의 키값을 가진 데이터를 찾는 문제
4. 키값의 순서대로 데이터를 방문하는 형태의 문제
5. 특정 키값 k를 갖는 데이터를 찾는 문제

해시함수란?

• 키값을 해시 테이블의 주소로 변환하는 함수
• 종류
  • 제산 잔여법, 비닝, 중간 제곱법

바람직한 해시함수는 계산이 용이하고 적은 충돌이 발생해야한다, 즉 각 키를 테이블의 각 슬롯에 균등하게 사상시킬 수 있어야한다.

제산 잔여법

(k는 키값 m은 해시 테이블 크기)

h(k) = K mod M

h(123) = 123 mod 11 = 2

(M)해시테이블의 선택에 주의 해야함

M=2 h(k)는 키 값의 하위 r 비트의 값이 됨

→ 키 값의 전체 비트가 주소 계산에 활용되지 못함

비닝

U를 단순하게 M 등분하여 각 등분을 각 슬롯으로 해시

키값의 볌위 U : 0~999

해시테이블의 크기 M : 10

U/M = 100

상위 비트가 고르게 분포하지 못하면 몇개의 슬롯에 집중되는 문제가 발현

중간제곱법

h(k) = (k^2) mod 2^r

m : 키값을 제곱한 결과에서 사용하지 않을 하위 비트의 크기

r: 해시 주소로 취할 비트의 크기

• 키 값 → 3자리 십진수
• 해시 테이블의 크기 16 (r=4)
• m = 7

충돌

서로 다른 키값 x, y에 대하여 h(x) = h(y) 인 경우

충돌 해결 방법

• 개방 해싱(”연쇄법”)
  • 충돌된 데이터를 테이블 밖의 별도의 장소에 저장/관리 → 연결리스트 사용
• 폐쇄 해싱 (”개방 주소법”)
  • 해시 테이블 내의 다른 슬롯에 충돌된 데이터를 저장/관리
  • 종류 → 버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱

개방 해싱

해시 테이블의 각 슬롯을 연결 리스트의 헤더로 사용

h(k) = K mod 10으로 할당한다 (일의 자리수만 보겟다는 소리)

위의 사진 처럼 9530이 들어온경우 기존 0번자리인 1000과 충돌이 발생하게 된다

이럴 경우 연결리스트를 해더로 사용하여 해결 할 수 있다

이런 방식을 연쇄법 개방해싱이라고 하며, 해시 테이블과 연결리스트가 주기억장치 내에서 유지될 때 적합하다.

버킷 해싱

해시 테이블 슬롯을 버킷으로 묶어 버킷 단위로 해싱

버킷 1에 차례대로 1121, 351, 1501 이 들어가다 671이 들어갈 자리가 없다 이럴경우 맨 아래 오버플로 버킷으로 내려가게 된다

디스크에 저장된 해시 테이블 구현에 적합하다 (버킷 크기 = 디스크 크기, 오버플로는 작게 유지)

선형 탐사

• 어떤 키 k에 대해서 탐사되는 슬롯의 순서열
  • p(K, i) → p(K, 0) = h(k), p(k, 1), p(k, 2), p(k, 3)…
• 탐사 순서의 계산 방법에 따라 성능의 차이가 발생
  • 선형 탐사, 이차 탐사, 이중 해싱
• 홈 위치가 사용 중이면 빈 슬롯을 찾을 때까지 테이블의 다음 슬롯으로 순차적으로 이동

별거 없이 쭉 탐색하며 빈자리에 들어감

0은 이미 자리가 있는상황이라 슬롯별 저장이 될수가없어 0

3/10의 경우는 1. 바로 1번슬롯 갈 경우, 2. 0번슬롯에 밀려 저장될경우, 9번슬롯 (9878)에 저장될경우

쭉 진행하다 보면 다음과 같은 문제들이 발생

• 모든 슬롯이 새로운 데이터가 삽입할 후보가 됨
• 1차 클러스터링 문제 → 긴 탐사 순서르 만들어 평균 탐새 시간의 증가를 초래
  • 데이터들이 연속될 위치를 점유하여 클러스터를 형서하고 이것이 점점 커지는 현상

이런 문제를 해결하고자 ‘이차탐사’가 등장

이차탐사

탐사 순서의 계산에 이차식을 이용

p(K + i^2) mod 10 으로 동작한다

파란색 박스의, 3을 제곱하면 9 초기에 키값이 7이였음으로 9 + 7 = 16

16에 mod 10을 해서 6번방에 들어가는 모습이다.

이럴 경우 모든 슬롯이 탐사 순서에 사용 되지 않음

3, 4, 8, 9는 사용이 되지않음 0, 1, 2, 5, 6만 탐사함

동일한 홈 위치를 갖는 두키는 동일한 탐사순서를 가짐으로 클러스터링이 여전히 발생

이 문제를 해결하고자 이중 해싱이 나옴

이중해싱

간단하게 해시함수를 하나 더씀

이를 통해

• 1차/2차 클러스터링 문제 해결
• 서로 다른 두 키의 홈 위치가 동일해도 서로 다른 탐사 순서를 가짐

삭제 연산

두가지 고려 사항

• 데이터의 삭제가 차후의 탐색을 방해하지 말아야 함
  • 단순히 빈 슬롯으로 두면 탐색이 해당 슬롯에서 종료되므로 그 이후의 데이터는 고립됨
• 삭제로 생긴 빈 슬롯은 나중에 삽입 과정에서 사용되어야 함

비석

• 삭제된 데이터의 위치에 ‘비석’ 이라는 특별한 표시를 하는 방법
  • 탐색 → 탐색하는 동안 비석을 만나면 탐색을 계속 진행
  • 삽입 → 비석이 표시된 위치를 빈 위치로 간주하여 새 데이터를 삽입
• 비석의 개수가 증가할 수록 평균 탐색 거리가 증가