programing/DataStructure2 다원 탐색 트리 - AVL트리는 균형 이진 트리의 한 종류 이기 때문에 자료가 많아지면 트리의 높이가 높아짐 -> 다원 탐색 트리 (m-way Search Tree) 1) 각 노드는 0에서 최대 m 개의 서브 트리를 갖음 2) k개의 서브트리를 갖는 노드는 (k-1) 개의 자료를 갖음 (단, k ≤ m) 3) 각 노드 안에서 자료들은 검색 키에 의해 정렬 4) 다음 조건을 항상 만족 Key i ≤ (i번째 서브트리 내의 모든 키 값) ≤ Key (i+1) 5) 모든 서브트리는 m-원 탐색 트리 (B-tree [비 트리]) > m-원 탐색 트리에서 트리 균형을 유지 1) 루트 노드는 leaf 노드이거나, 2에서 m 개의 서브트리를 가짐 2) 루트 노드를 제외한 모든 내부 노드는 아래 개수만큼 서브트리를 가짐 m/2(소수이.. 2015. 6. 4. 해싱 함수 충돌 해결 방법 - 클러스터링 (Clustering) : 자료들이 해시 테이블에 고르게 분포되지 않고 특정 주소들 주위로 뭉치게 되는 현상 - 개방 주소 (Open Addressing) > 조사법 (Probing)이라고도 함 > 주소가 비어있지 않으면 그 다음 주소를 확인하고 안비어 있으면 되풀이 1) 선형 조사법 -> 주소를 1씩 증가 2) 제곱 조사법 -> 주소를 조사 횟수의 제곱만큼씩 증가 3) 이중 해싱 -> 원래 해싱 함수와는 다른 추가적인 해싱 함수 이용 - 체이닝 (Chaining) > 해시 테이블의 구조를 변경하여 각 주소(버킷)에 하나 이상의 검색 키 값이 저장될 수 있도록 함 2015. 6. 4. 이전 1 다음
