분류 전체보기 (154) 썸네일형 리스트형 해싱 (Hashing) (2) Hasing Open Addressing을 통한 충돌 해결- 모든 키를 해쉬 테이블 자체에 저장한다.- 테이블의 각 칸(slot)에는 1개의 키만 저장한다.- 충돌 해결 기법의 종류Linear probingQuadratic probingDouble hashing Open Addressing의 방법 - Linear Probing- h(k), h(k) + 1, h(k) + 2, ...의 순서로 검사를 진행한다. 만일 원래 저장할 슬롯에 데이터가 존재한다면 계속 뒤로 진행하며 가장 처음에 나오는 빈 슬롯에 데이터를 저장한다.- 테이블의 끝에 도달하면 다시 처음으로 돌아가며 circular하게 저장 공간을 찾게 된다.- Linear Probing의 단점primary cluster : 키에 의해서 채워진 연속된 .. 해싱 (Hashing) (1) Hashing Hash Table- 해쉬 테이블은 dynamic set을 구현하는 효과적인 방법들 중 하나이다.적절한 가정을 한 후에는 평균적인 탐색, 삽입, 삭제 시간에 O(1)만이 소요된다.최악의 경우 시간 복잡도는 대부분의 경우 Θ(n)이 된다.- 해쉬 함수 (hash function) h를 이용해 키 k를 T[h(k)]에 저장하게 된다.h : U -> {0, 1, ..., m - 1} // 이 때 m은 테이블의 크기, U는 가능한 모든 키들의 집합이다.이 과정은 보통 키 k가 h(k)로 해싱되었다라고 말하게 된다. 해쉬 함수의 예- 모든 키들을 자연수라고 가정한다. (어떤 데이터들일지라도 자연수로 해석이 가능하다.)- Ex : 문자열ASCII 코드 : C = 67, L = 76 등- 해쉬 함수의 .. Red Black Tree (2) 보호되어 있는 글입니다. Red Black Tree (1) 보호되어 있는 글입니다. 이진 검색 트리 (3) 보호되어 있는 글입니다. 이진 검색 트리(2) 보호되어 있는 글입니다. 이진 검색 트리 (1) 보호되어 있는 글입니다. 트리와 이진트리 검색 트리 (Search Tree) Tree and BinaryTree 트리 (Tree)- 계층적인 구조를 표현한다.조직도 | 디렉토리와 서브 디렉토리 구조 | 가계도 등- 트리는 노드 (node)들과 이를 연결하는 링크 (link)들로 구성되어 있다.맨 위의 노드는 "루트"라고 부른다.노드를 연결하는 선인 링크는 edge, branch등으로도 불린다.- 부모 - 자식 관계 : 상하로 링크되어 있는 두 노드를 비교했을 때 상대적으로 루트에 가까운 노드는 부모 노드, 아래쪽 노드는 자식 노드라고 불린다.- 루트 노드를 제외한 트리의 모든 노드들은 하나의 부모 노드만을 가지고 있다.- 형제 관계 : 같은 부모노드를 가지고 있는 노드들은 서로 형제(sibling)관계라고 부른다.- 리프 노드 : 아래에 자식 .. 이전 1 ··· 11 12 13 14 15 16 17 ··· 20 다음
