-Direct-access tables: 배열의 인덱스로 바로 접근하는 방식
장점: 배열의 인덱스에 O(1)으로 바로 접근/ 단점: 공간을 많이 낭비
-Resolving collisions by chaining: : 각 인덱스에 할당된 것이 값이 아니라 키와 값을 가진 LinkedList(연결리스트)로 추가적인 공간을 활용하는 것
-Choosing hash functions
1. Division method: 간단하고 빠름, 해시테이블 크기가 결정되야 함
2. Multiplication method:
-Resolving collisions by open addressing: 충돌 발생시, 인접한 다른 비어있는 해시 버킷을 찾아 삽입하는 방법/테이블에 1개의 해시와 1개의 값이 매칭
INSERT & SEARCH : 빈 공간을 찾을 때까지 계속 탐색하는 방법
1. Linear probing: primary clusting문제, 어떤 키에 데이터가 여러번 들어가면 그 근처의 slot들이 다 채워짐
2. Double hashing: 주로 m을 2의 제곱수로 고르고 h2()는 홀수만 생성하도록
-> α < 1인 해시 테이블에서 없는 slot을 탐색하는 예상 횟수는 최대 1/(1-α)이다.
(수학적 증명을 거쳐 밝혀진 사실)
만약 테이블이 절반 정도 채워졌으면, 예상 탐색 횟수는 1/(1-0.5) = 2
만약 테이블이 90%정도 채워졌으면, 예상 탐색 횟수는 1/(1-0.9) = 10
-Universal hashing:다수의 해시 함수를 만들고 이 해시함수의 집합에서 무작위로 해시함수를 선택해 해시값을 만드는 기법
-Constructing a set of universal hash functions
-Perfect hashing: 서로 다른 모든 식별자들을 서로 다른 버킷으로 대응시키는 해쉬
-Binary-search-tree sort
: Average node depth = O(lgn)
-Convex functions:
-Jensen’s inequality
-Exponential height recurrence
Balanced search trees(균형이진탐색트리)
-Red-black trees
1. 모든 노드는 빨간색 혹은 검은색이다
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL:자료를 갖지 않고 트리의끝을 나타냄)
4. 빨간색 노드의 자식은 검은색이다. (빨간색 노드가 연속으로 나올 수 없다)
5. 모든 리프 노드에서 Black Depth는 같다.(리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.)=> bh >= h/2
한 트리의 총 노드의 수는 n은 subtree의 노드의 수(2^bh-1)보다는 크거나 같다, bh>=h/2. 따라서
-Rotations(회전): O(1)시간에 수행/ 키의 순서를 유지
-Insertion(삽입): O(lgn) with O(1) rotations
Case 1. 부모 노드가 레드인데, 부모님의 형제가 레드일 때 - 색상 변환
Case 2. 부모 노드가 레드인데, 부모님의 형제가 없거나 블랙일 때 – 회전
