분야
ppt인덱스 구조
인덱스
-키값 과 그 키값을 가진 레코드 저장된 주소를쌍
으로 체계적 묶음
-밀집인덱스 : 모든 레코드에 대해 키값 주소값 포함
-희소인덱스
이원 탐색 트리
AVL 트리
M-원 탐색 트리
이원 탐색 트리
(binary search tree)
이진 트리로 각 노드는 레코드 키와 레코드 가 저장되어 있는 주소를
지시하고 있는 트리
ex) deer를 찾는다
deer는 5이다
성질- 노드 Ni의 왼편 서브트리(LT(Ni))에 있는 모든 노드
의 키값은 노드 Ni의 키 값보다 적다.
*Ni∈LT(Ni) -> Kj < ki
- 노드 Ni의 오른편 서브트리(Rt(Ni))에 있는 모든 노
드의 어떤 키값보다 적다.
*Ni∈RT(Ni) -> Kj > ki
7
dog
6
cow
9
horse
4
Bear
8
fox
5
deer
이원 탐색 트리 탐색
(binary search tree)
ex)bear를 탐색
bear는 4이다
루트가 Ni인 이원 탐색 트리에서 키값 k인 노드를 탐색하기 위해
탐색 - 1. 만일 트리가 공백이면 노드를 찾지 못하고 끝남.
2. 만일 k = ki 이면 노드 Ni이가 원하는 노드
3. 만일 k < ki 이면 왼쪽 서브트리에서 탐색
4. 만일 k > ki 이면 오른쪽 서브트리에서 탐색
7
dog
6
cow
9
horse
4
Bear
8
fox
5
deer