[자료구조] 9. B-트리, 해쉬 테이블

1. B-트리

 

- B-트리란?

- 원소삽입 

 

 

- B-트리란?

다음을 모두 만족하면 m차 B-트리

a. 모든 리프노드의 깊이가 동일
b. 노드 당 자식 수는 [m/2] ~ m개 (leaf 노드 제외)     // [m/2] : 올림함수
c. 자식 노드의 수는 데이터 수보다 +1 (leaf노드 제외)  // 즉, m차 B-트리에서 노드 내 데이터 최대 수는 m-1개
d. 단일 노드 내에서 데이터는 정렬됨
e. 트리 관점에서도 데이터는 정렬됨

 

 

 

 

 

- 원소 삽입

 

데이터 수 제한을 넘어서지 않는 경우에서 삽입

⁘ 탐색과 유사한 방법으로 새 데이터를 삽입할 적절한 리프 노드 선정

⁘ 해당 리프 노드에 데이터가 추가될 여유가 있으면 그대로 삽입

 

데이터 수 제한을 초과하는 경우에서 삽입

⁘ 리프 노드에 데이터 삽입될 여유가 없으면, 가운데 데이터를 튕겨내는 과정을 반복

⁘ 튕겨나가는 데이터의 좌우 값이 분리됨 주의

 

 

 

 

2. 해쉬 테이블 (Hash Table)

 

이진탐색트리의 성능(O(n))을 개선한 AVL 트리와 레드-블랙 트리, B-트리의 탐색/삭제/삽입 연산의 시간 복잡도는 모두 O(log N)

 

 

- 해쉬 테이블이란?

- 해쉬테이블 예시

- 해쉬테이블 충돌 해결 

Chaining - Open Addressing

Linear Probing

Quaadratic Probing

Double Hashig

 

 

 

- 해쉬테이블이란?

데이터 값과 Hash 함수에 의해 삽입 위치가 결정되는 자료구조

충돌의 경우를 무시한다면, 삽입/삭제/검색에 O(1)만 소요

 

 

- 해쉬테이블 예시

mod 연산을 이용한 해쉬 함수의 구성

해쉬테이블의 크기가 m일 때, h(x) = x (mod m)으로 정의

 

적재율

해쉬 테이블의 크기가 m이고 저장된 데이터의 수가 n일 경우, 적재율 = n/m

 

 

 

- 해쉬테이블 충돌 해결; Chaining

삽입하고자 하는 위치에 이미 데이터가 존재할 경우,

Linked List 등을 이용하여 동일한 위치에 데이터를 연달아 삽입함으로써 충돌 문제를 해결 가능

 

⁘ Open Addressing

목적: 하나의 index에 하나의 data 저장하기 위해

비어있는 곳을 찾아 데이터 삽입

 

 

- 해쉬테이블 충돌 해결; Linear Probing

Open Addressing 중 하나, 선형적으로 빈칸을 탐색하는 방식

삽입하려는 곳이 비어있지 않은 경우, 다음 빈칸을 찾아 그곳에 데이터를 대신 삽입

 

(문제 1) -> 데이터 지운 흔적 남기기

(문제 2) -> 특정 구간에 데이터가 몰리는 문제 발생 (효율성)

 

 

 

- 해쉬테이블 충돌 해결; Quadratic Probing

기존에는 1칸 뒤 탐색 - 4칸(2^2) 뒤 탐색 - 9칸(3^3) 뒤 탐색

 

(문제) 그러나 h(x) 해시함수의 값이 같은 다른 데이터를 계속 삽입하면 충돌이 계속 일어남

 

 

 

- 해쉬테이블 충돌 해결; Double Hashig

일차적으로 h(x)를 이용하여 데이터를 삽입할 위치 결정

충돌 발생 시 추가 함수 f(x)를 이용, 건너뛸 칸 수를 결정한 후 빈칸을 찾을 때까지 건너뛰기 반복

h(x) = x (mod 13)

f(x) = x(mod 7) + 2

서로 다른 수 a와 b에 대하여 h(a) = h(b)이더라도, f(a)와 f(b)는 다를 수 있음

 

 

 

 

 

 

참고

파이썬과 함께하는 자료구조의 이해 - 예스24