레코드 record
-개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위
(예) 사람의 레코드 주민번호, 이름, 집주소, 집 전화번호, 직장 전화번호,
필드 field
-레코드에서 각각의 정보를 나타내는 부분
(예) 위 사람의 레코드에서 각각의 정보를 나타내는 부분
검색키 search key 또는 키 key
- 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드
-키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있음
검색 트리 search tree
-각 노드는 규칙에 맞도록 하나씩의 키를 갖고 있음
-키를 통해 해당 레코드가 저장된 위치를 알 수 있음
검색 트리 종류
①자식 노드 수
-K진 검색 트리: 자식이 최대 k개
-이진 검색 트리(2개)/ 다진 검색 트리(세개 이상)
②저장되는 장소
-내부 검색 트리: 검색트리가 메인 메모리 내에 존재
-외부 검색 트리: 검색트리가 외부(디스크)에 존재
③검색키가 포함하는 필드 수
-일차원 검색트리: 키를 구성하는 필드가 1개
:이진 검색트리, 다진 검색 트리, B트리, AVL트리, 레드 블랙 트리
-다차원 검색트리: 키를 구성하는 필드가 두개 이상
:KD-트리, KDB-트리, R-트리
1) 이진 검색 트리
-각 노드는 서로 다른 키 값을 하나씩 갖는다.
-최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식을 갖는다
-임의늬 노드의 키 값은 자신의 왼쪽 자식 노드의 키 값보다 크고, 오른쪽 자식의 키 값보다 작다
case1: r이 리프 노드인 경우 - 그냥 삭제
case 2 : r의 자식 노드가 하나인 경우 - 바로 붙이기
case 3 : r의 자식 노드가 2개인 경우 - r의 직후 원소 s를 찾아서 r 자리에 놓고 나머지는 그냥 붙이기
2) 2-3 트리
-완전 균형 크리
-구조
•왼쪽 자식의 키는 부모의 왼쪽 키보다 작음
•오름쪽 자식의 키는 부모의 오른쪽 키보다 큼
•가운데 자식의 키는 부모의 왼쪽, 오른쪽 키 사이에 있음
•내부 노드는 물론 리프 노드도 3-node가 될 수 있음
•완전한 균형을 이루기 때문에 root에서 leaf에 이르는 모든 경로의 길이가 동일함
-특징
①언제 tree의 높이가 증가하는 가?
•삽입 위치의 리프 노드로부터 루트 노드까지의 경로가 모두 3-node로 가득찬 경우
•이진 탐색트리의 높이는 leaf 아래쪽으로 1 증가하는 반면, 2-3트리는 root위쪽으로 1만큼 자람
②언제 트리의 높이가 감소하는가?
• 삭제 위치의 리프 노드로부터 루트 노드까지의 경로가 모두 2-node인 경우
③ 탐색 효율: O(log2N)~O(log3N)
• 모든 노드가 3노드일때 가장 높이가 낮음
• 이경우 레벨 h까지의 데이터 수 N= 2(1+3+32+…+3 h-1 ) = 3h
• 따라서 h = log3N
3) 레드블렉트리
- Red와 black의 색상을 이용해 트리의 균형을 유지
- 이진검색트리의 모든 노드에 블랙 또는 레드의 색을 칠하되 다음의 레드블랙특성을 만족해야 한다
① 루트는 블랙이다
② 모든 리프는 블랙이다
③ 노드가 레드이면 그 노드의 자식은 반드시 블랙이다
④ 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다
-삭제
①이진 검색 트리와 동일한 방법 + 색상 맞추기
②삭제노드의 자식이 2개인 경우 - 자기보다 하나 작은 값으로 대체
③삭제노드가 자식이 없거나 한개만 가진 경우-삭제노드가 레드면 문제없고 블랙이라도 유일 자식이 레드면 문제 없음
-자세한 내용은 문풀에서 다루겠음
4) B-트리
-검색 트리가 방대하여 디스크에 있는 경우 (외부 검색 트리)
-디스크의 접근 단위는 블록(페이지)
-디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다
-트리의 높이를 최소화하는 것이 유리 Ø외부 다진 검색 트리
-검색트리가 외부 디스크에 있음 § 한 노드에 최대 k개까지 키가 크기 순으로 저장
: 키가 k개 있는 경우 k+1개의 자식을 가짐
특징
- 루트를 제외한 모든 노드는 ~ k 개의 키를가진다.
- 모든 리프 노드는 같은 깊이를 가진다.
-오버플로우가 일어나면 가운데 key를 기준으로 분할하고 가운데가 승진한다. 만약 마지막꺼면 마지막 꺼를 위에 올리고 하나 내리기
'알고리즘' 카테고리의 다른 글
| 쉽게 배우는 알고리즘-09동적프로그래밍(~돌놓기) (1) | 2023.10.23 |
|---|---|
| 쉽게 배우는 알고리즘-08집합의 처리 (0) | 2023.10.23 |
| 쉽게 배우는 알고리즘-05선택 알고리즘 (0) | 2023.10.23 |
| 쉽게 배우는 알고리즘-04정렬 (1) | 2023.10.23 |
| 쉽게 배우는 알고리즘-03점화식과 알고리즘 복잡도 분석 (1) | 2023.10.23 |