-
심볼 테이블키
심볼 테이블
키-벨류 쌍(key-value pair) 추상화
키: 검색에 사용하는 필드
밸류 : 관련(부속, 위성) 데이터(satellite data)
연산
검색: 주어진 키에 대하여 검색한 후, 해당 밸류를 반환
삽입: 키와 함께 밸류를 삽입
- 만일 키가 이미 존재하면, 밸류를 업데이트삭제: 특정 키를 검색하여 해당 키-밸류 쌍을 삭제
선형자료구조를 이용한 심볼 테이블 구현과 검색
정렬되지 않은 연결 리스트(unordered linked list)
삽입/검색이 앞의 정의와 비슷하다.
삽입/검색의 시간복잡도 : O(n)
예)
정렬 상태를 유지하는 배열(ordered arrays)
검색: 이분검색(binary search)
이분검색의 시간복잡도: O(lg n)이다.
-> 빠른 것 같지만, 검색 전에 정렬을 해야 하기 때문에 정렬시간도 고려 해야 한다.
삽입 : 이분검색하여 삽입 위치를 결정한 후, 뒤쪽 데이터를 한 칸씩 뒤로 이동한 후 해당 위치에 삽입, O(n)시간 소요
효율적인 심볼 테이블?
이진검색트리 : 평균적으로 O(lg n), 최악의 경우는 O(n)
균형 잡힌 이진검색트리 : 언제나 O(lg n)해싱 : 심지어 O(1)
-> 해싱이 제일 좋지만, 검색에만 사용할 수 있는 녀석이라서, 트리 같이 다른 기능을 추가할 수 있는 녀석도
쓴다.
Hashing
해싱(Hashing)
키를 사용하여 데이터가 저장된 테이블의 인덱스를 알아내는 기법
해시 테이블은 키에 따라 즉시 검색 위치가 결정 -> 상수시간 검색
-> 언제나 시간이 일정하다.
해시코드(hash code) + 압축함수(compression function)
해시 함수(hash function)
키 값을 입력으로 받아 해시 테이블 상의 주소(index)를 리턴하는 함수
좋은 해시 함수의 조건
최대한 랜덤하게 키들을 테이블에 퍼지게 저장해야 함
해시코드(hash code)
보통 문자열이다.
예)
입력합수 or 모듈라 행식
해시코드에 테이블의 인덱스를 매핑시키는 함수
Division 방법: 해시코드 x에 대하여
- 더 정확한 방법 : h2(x) = (x & 0x7fffffff) % m, “bitwise-and”
해시값(hash value)
불가피하게 충돌이 발생한다: 해시 테이블의 인덱스가 켭쳤을 때
해결 방법: 체이닝(chaining) 혹은 개방 주소 방법(open addressing)
개방 주소 방법
추가공간을 허용하지 않고, 주어진 테이블 공간에서 해결
새로운 키가 충돌하면, 다음 빈 슬롯을 찾아 저장
선형조사(linear probing) : hi(x) = (h(x) + i) % m
이차원 조사(quadratic probing) : hi(x) = (h(x) + i^2) % m
더블 해싱(double hashing) : hi(x) = (h(x) + i*d(x)) % m-> 더블 해싱의 성능이 가장 뛰어남
-> 원소를 삭제할 때는 반드시 원래는 원소가 있던 자리였음을 표시해 주어야 함
해시 테이블 크기의 동적 재조정
- 적재율이 높아지면 효율이 급격히 떨어진다. -> 적재율이 0.5 이하여야 한다.
- 적재율이 1을 넘으면 , "Table Overflow"
- 적재율에 대한 임계값을 설정한 후, 그 값을 넘으면 해시 테이블의 크기를 두 배로 키우고 모든 원소를 재해싱(rehashing) 해야 함
- Rehashing: 원래 적재되었던 Key와 value들을 새로운 테이블에 넣는 것이다.
이진검색트리(BST)
이진트리 : 트리의 모양(위상 topology)
이진검색트리: 노드의 키의 성질이진검색트리(binary search tree)
tree: 모든 node들이 연결된 계층구조(hierarchy) 부모와 자식관계
이진트리(binary tree) : 모든 노드가 2개의 서브 트리(공집합 가능)를 가지는 트리
-> 2개이하의 노드를 갖는 것이다.
이진트리의 노드
- 키(key) : 검색 필드
- 밸류(value) : 키의 동반 데이터
- 왼쪽 서브트리에 대한 참조(left)
- 오른쪽 서브트리에 대한 참조(right)잎노드(leaf) : 자식노드가 모두 null인 노드(=terminal node)
이진검색트리
- 왼쪽 서브트리의 키들은 해당 노드의 키보다 작고
- 오른쪽 서브트리의 키들은 해당 노드의 키보다 크다.
-> 단 중복이 있으면 안된다.
이진검색트리에서의 검색
재귀 알고리즘
- 방문노드가 null이면, null을 반환
- 검색 키가 방문 노드의 키보다 작으면, 왼쪽 서브트리에 대하여 재귀적으로 검색
- 검색 키가 방문 노드의 키보다 크면, 오른쪽 서브트리에 대하여 재귀적으로 검색
- 두 값이 동일하면 해당 노드(의 밸류)를 반환
예)
첫번쨰 노란색:
키에 행당하는 검색 결과가 없다, 검색 실패
마지막 노란색:
자료형이 다를 수 있기 때문에, node를 반환한다
이진검색트리에서의 삽입
재귀 알고리즘
- 방문노드가 null이면, 새로운 노드를 만들어 반환
- 검색 키가 방문 노드의 키보다 작으면, 왼쪽 서브트리에 재귀적으로 삽입
- 검색 키가 방문 노드의 키보다 크면, 오른쪽 서브트리에 재귀적으로 삽입
- 두 값이 동일하면, 밸류를 수정
예)
(S E A R C H X M P L)(key) 을 이진검색트리에 삽입하기
X는 깊이가 1, P는 깊이가 5이다.
X는 비교 2회, P는 비교 6회한다.
-> 깊이에 따라서 시간 복잡도가 결정된다.
최악검색시간 == 트리의 높이
최악: O(n)
평균(lg n)
왜 이진트리를 쓰는가?
- 최소, 최대
- 직전/직후 원소
- 데이터를 정렬 상태 추출 가능하다.
->pre-order, in-order, post-order, level-wise(구현이 어렵다)
이진검색트리의 성질
이진검색트리는 효율적으로 동적검색을 실행
키를 빨리 추가·삭제할 수 있을 뿐만 아니라, 평균검색시간을 낮게 유지함
트리의 높이(height)가 검색시간을 좌우함
n개의 다른 키로 이루어진 이진검색트리에서의 평균검색시간은 A(n) 비스무리 1.38lg n
-> O(lg n)이다.
균형 잡힌 검색트리 알고리즘
균형을 유지하면서 마디를 추가하고 삭제하는 트리 알고리즘
- 이진트리 : AVL 트리, 레드블랙 트리
- 다진트리 : 2-3(-4) 트리, B-트리
(다진트리: 여러개의 노드가 붙일 수 있다.)
(B-트리: 외부트리하고 한다, 데이타 베이스에서 들을 수 있다.)
레드블랙 트리
래드블랙 트리(RBT : red-black tree)
- 색깔(color) 필드를 가짐 -> 색깔은 해당 노드의 부모와의 링크의 색깔
- 모든 레드 링크는 왼쪽(으로 기울어진, left-leaning) 링크이어야 함
- 임의의 경로에서 레드 링크는 연속으로 연결되지 않아야 함
- 일종의 균형 잡힌 트리
왼쪽 회전(left rotation: LR)
-> 오른쪽 레드 링크를 왼쪽으로 회전
오른쪽 회전(right rotation : RR)
-> 왼쪽 레드 링크를오른쪽으로 회전
색깔 반전(color flip : CF)
-> 모두 레드인 자식을 블랙으로 바꾸고 자신의 색깔을 레드로
- 오른쪽 자식이 레드이고, 왼쪽 자식이 블랙 : 왼쪽 회전
- 왼쪽 자식과 왼쪽 자식의 자식이 모두 레드 : 오른쪽 회전
- 두 자식이 모두 레드 : 색깔 반전