1. 이진 탐색 트리
1.1. 이진 탐색 트리 (Binary Search Tree)
•
개념
◦
트리에서 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진트리
◦
특정 데이터를 검색하고, 노드를 삽입/삭제하는 응용 문제에 가장 효과적인 이진 트리
◦
탐색에 최적화된 이진 트리
◦
키: 이진 트리 노드의 데이터 (노드를 특정할 수 있는 값)
•
구성(제한사항)
◦
왼쪽 자식 노드 < 부모 노드
◦
오른쪽 자식 노드 > 부모 노드
•
예시
이진탐색트리 이진탐색트리가 아님
루트를 어떻게 설정하냐에 따라 다양한 BS 트리가 생겨날 수 있음
1.2. BS 트리 순회
•
BS 트리를 위한 노드 정의
struct Knode {
struct KNode *left; // 왼쪽 자식을 위한 포인터
char key[10]; // 키값을 위한 문자 배열
int info; // 데이터 필드
struct Knode *right; // 오른쪽 자식을 위한 포인터
}
C
복사
•
BS 트리의 중위 순회
void Inorder(struct KNode *rootptr) {
if(rootptr != null) {
Inorder(rootptr->left);
printf("%d", rootptr->info);
Inorder(rootptr->right);
}
}
C
복사
1.3. BS 트리의 노드 탐색
struct KNode *Search(char k[], struct KNode *r){
if(r==null)
return(null);
else
if(strcmp(k, r->key) == 0) // strcmp - key값 비교
return(r);
else if(strcmp(k, r->key) < 0) // k < r->key => 왼쪽으로 이동
return(Search(k, r->left));
else
return(Search(k, k->right)); // k > r->key => 오른쪽으로 이동
}
C
복사
1.4. BS 트리의 노드 삽입
struct KNode *Insert(struct KNode *newptr struct KNode *r){
if(r==null)
return(newptr);
else
if(strcmp(newptr->key, r->key) == 0) // strcmp - key값 비교
DUPLICATE_ENTRY();
else
if(strcmp(newptr->key, r->key) < 0)
r->left = Insert(newptr, r->left);
else
r->right = Insert(newptr, r->right);
return(r);
}
C
복사
•
예시
1.5. BS 트리의 노드 삭제
•
자식을 하나만 갖는 노드를 삭제하는 경우
◦
삭제한 노드를 가르키던 포인터가 그 노드의 null이 아닌 서브트리의 루트를 가리키게 함
◦
자식노드를 삭제한 노드의 부모 노드를 바라보게함
•
두개의 자식을 갖는 노드를 삭제하는 경우
◦
둘 중 특정 방향의 서브트리에서 노드를 올리는 방법으로 진행
2. Splay 트리
2.1. 이진 탐색 트리의 단점
•
트리의 구조와 특정 노드에 접근할 확률에 영향을 받음
•
어떤 노드의 탐색/삽입/삭제를 위한 접근 정보를 예측할 수 없는 상황에서는 최적의 BS 트리 구조 결정 어려움
•
휴리스틱 알고리즘을 이용하여 구축한 BS 트리의 성능이 최적에 가까움
◦
휴리스틱 알고리즘: 경험적 알고리즘
2.2. 이진 탐색 트리의 성능
•
좋은 성능의 BS 트리를 구축하는 방법 (휴리스틱)
◦
자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓음
◦
트리가 균형이 되도록 유지
▪
각 노드에 대해 왼쪽과 오른쪽 서브트리가 가능한 한 같은 수의 노드를 갖게함
2.3. Splay 트리
•
자주 탐색하는 키를 가진 노드를 루트에 가깝에 위치하도록 구성한 BS 트리
•
Splay 연산
◦
최근에 접근한 노드 x를 (곧 사용할 것으로 예상하여) 루트에 위치시켜 트리를 재구성하는 연산
•
Splay 트리
◦
가장 최근에 사용한 노드 x가 트리의 루트에 올때까지 Splay 연산을 반복하여 적용하여 생성된 이진트리
2.4. Splay 트리의 연산
•
노드 x: 최근에 접근한 노드
•
노드 p: x의 부모 노드
•
노드 g: x의 조부모(부모의 부모) 노드
•
Zig (단일 회전)
◦
p가 트리의 루트면 p와 x의 간선 연결을 회전시킨다.
•
Zig-Zag (두개의 단일 회전)
◦
p가 루트가 아니고, x와 p가 동일하게 왼쪽 자식들 또는 오른쪽 자식들이면, p와 조부모 g와의 간선 연결을 회전시키고, 그 다음 x와 p의 간선연결을 회전시킨다.
◦
예시 1
◦
예시 2
3. AVL 트리
3.1. 정의
•
정의
◦
노드 의 왼쪽 서브트리 높이와 의 오른쪽 서브트리 높이가 최대 1만큼 차이가 난다는 조건을 만족하는 트리
•
특징
◦
제한 조건을 완하여 트리가 완전한 균형이 아닌 것을 허용
◦
무너진 균형의 정도는 작아야함
◦
평균 탐색 길이도 완전 균형 트리의 탐색 길이와 크게 차이 나지 않아야 함
◦
거의 완전한 균형 트리의 한 형태로, 높이가 균형잡힌 높이 균형 트리 (height balanced tree)
◦
직접 탐색 성능이 매우 좋음
3.2. 조건
•
노드 Vi의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이가 최대 1만큼 차이 남
3.3. 예시
•
예시
4. BB 트리
4.1. 정의
•
Bounded-Balanced Tree
◦
거의 완전히 (대략) 균형 잡힌 트리의 다른 종류로 무게가 균형 잡힌 트리
•
각 노드의 양쪽 서브트리의 무게가 균형을 유지하는 트리
•
트리의 높이
◦
노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값으로 루트로부터 잎까지 가장 긴 경로 길이
•
트리의 무게
◦
트리에 속한 잎 노드의 개수
4.2. 균형 트리
•
AVL 또는 BB 트리에 대하여 각각 무게 또는 크기(높이) 제한 조건을 만족시키는데 드는 비용 > 트리를 완전히 균형잡히게 유지하는 비용 및 노력
•
삽입이나 삭제 후 트리를 완전히 균형 잡히게 유지하기 위해서는 O(n)의 노드를 옮겨야 함
•
반면 AVL 또는 BB 트리는 O(log2N)개의 노드만 옮기면 됨