홍시홍의 프로그래밍

사용하는 곳, 데이터 베이스나 파일시스템에서 데이터를 저장, 관리 할 때 사용한다 특징 1. n차 b트리라면 자식 트리들은 최소한 n/2개의 노드를 가져야한다 2. 왼쪽에는 자신보다 작은 서브 트리, 오른쪽에는 자신보다 큰 서브트리를 가진다 탐색 하향식으로 탐색할 수 있도록 한다 삽입 하향식으로 자기 자리를 찾고 b트리의 조건을 만족하지 못할 경우, 분해하여 b트리의 조건을 만족 시킬 수 있도록 한다 삭제 리프 노드일 경우는 그냥 삭제 아닐 경우는 삭제 후 부모노드, 형제 노드를 이용하여 b트리 유지한다. 시간 복잡도 높이가 h라고 햇을때 logh

구간 트리란 구간의 합을 구하기 위한 트리 시간 복잡도 O(logn) 트리 만들기 구간 별 합을 저장할 수 있도록 한다. 트리는 완전 이진 트리로 구성되어 있다 자식은 왼쪽 자식은 *2, 오른쪽 자식은 *2+1이다 위 점을 활용하여 각 구간의 합을 부모에 저장한다 트리 갱신 해당 Index를 포함하는 구간을 현 Index의 값과의 차이를 합하여 갱신한다 특징 1. 배열로 구성 - 배열의 크기는 보통 N*4 - 2^k로 N을 넘을수 있는 최소 수 구간 트리의 updata 그 수를 포함한 모든 노드들을 업데이트 시켜준다 구간 트리의 탐색 탐색은 4가지 경우가 발생한다 1. 탐색 구간이 겹치지 않는 경우 - 종료 2. 탐색 구간이 정확히 일치하는 경우 - 탐색 완료 3. 탐색 구간이 내부에 포함되는 경우 - ..

이진 탐색 트리란 노드의 왼쪽에는 현 노드보다 작은 값, 오른쪽에는 큰 값이 저장되어 있는 자료 구조 이진 탐색 트리 조건 1. 왼쪽에는 작은 값 2. 오른쪽에는 큰 값 3. 공집합도 포함 삽입 위의 과정으로 위치를 찾아 삽입 삭제 1. 단말 노드일 경우 - 노드 삽입 2. 하나의 자식이 있는 경우, 본인 노드 지우고 자식을 자신의 자리에 3. 노드가 2개 있는 경우 - 오른쪽 서브 트리 중 가장 작은 값을 삽입 시간 복잡도 평균 O(logn) 최악의 경우 한쪽으로 치우친 트리일 경우 O(n)

해싱이란 해시 테이블을 이용한 탐색 기법 이론적으로 O(1)에 탐색가능 해시 함수 : 인덱스를 해시 주소로 바꿔주는 함수 해시 함수 조건 - 충돌이 적어야 한다 - 해시 주소가 고르게 분포되어야한다 - 계산이 빨라야 한다. 제산 함수 일 경우 소수로 나눈다 폴딩 이동 폴딩, 경계 폴딩 탐색키가 문자열일 경우 호너의 방법 사용 해싱은 충돌을 잘 처리해야 한다 충돌이 일어날 경우, 선형 조사법과 체이닝으로 해결 충돌 해결법 2가지 1. 오픈 어드레싱 2. 체이닝 오픈 어드레싱 종류 3가지 1. 선형 조사법 - h(k)+1 ,,,, +2 ,,,,+3 으로 2. 이중 조사법 - 제곱을 더함 h(k) +1^2,2^2,3^2식으로 3. 이중 해싱법 - 해시 2개 사용 - 첫번째 해시 kmod H 두번째 해시 P -..