쉅게 배우는 알고리즘 2 쉅게 배우는 알고리즘 - 해시테이블 6장 해시 테이블 원소끼리 비교해 자리를 찾는 것이 아니라 자신의 값이 자신의 자리를 바로 결정한다. 1. 해시 테이블 - 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조 - 해시값은 해시 함수에 의해 계산 - 적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율로서 성능에 중요한 영향을 끼침. 2. 해시 함수 다음의 두 가지 성질을 만족해야 함 a. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. b. 계산이 간단해야 한다. 2.1 나누기 방법 - 테이블의 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 하는 방법 - h(x) = x mod m : m은 해시 테이블의 크기 - m은 2의 멱수(2^p) 에 가깝지 않은 소수를 택하는 것이 좋다. 2의 멱수라면 입력 원소.. 2019. 8. 22. 쉅게 배우는 알고리즘 - 검색트리 1. 이진 검색 트리 1.1 특성 a. 이진검색트리의 각 노드는 키값을 하나씩 갖는다. 각 노드의 키값은 모두 달라야 한다. b. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다. c. 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식 노드의 키값보다 작다. 1.2 검색 루트 노드에서부터 검색을 시작한다. 루트 노드의 값과 x를 비교해 x가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽 서브트리로 가서 x를 찾는다. x를 가진 노드가 있으면 해당 노드를 리턴하고, 없으면 NIL을 리턴한다. 1.3 삽입 실패하는 검색을 수행하여 리프 노드로 간 후 그 리프 노드의 자식으로 x를 매단다. 이진검색트리의 모양은 원소들이 어떤 순서로 삽입되었는지에 따라 달.. 2019. 8. 16. 이전 1 다음