🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.
1. 이진트리 (Binary Tree)
모든 node의 자식이 둘 이하인 트리(tree) -> left, right 
2. 이진트리 (Binary Tree : BT) 의 종류
1.포화 이진트리 (Full BT)
- 모든 non-terminal node (leaf 제외)가 두 개의 자식을 갖는다.
- 모든 leaf의 level이 같다.
2. 완전 이진트리 (Complete BT)
- 높이 h인 BT에서 level h-1 까지는 Full BT
- 마지막 level h 에는 좌->우로 빈틈 없이 leaf가 채워진다.
💡참고
3. 완전 이진 트리 (CBT) 의 구현
4. 이진 트리의 순회 (Traversal)
: 재귀적 방문( stack이 사용됨)
5. 이진 탐색 트리 (Binary Search Tree : BST)
- 선형검색 (Linear Search) : O(N)
- 이진검색 (Binary Search) : O(lg N)
- 검색 (Search)
// Search (Root, key)
Search(Node *p, key)
{ if(p == NULL) return Not Found
if(key == p->Data) return Found
if(key < p->Data){
return search(p->Left, key); // 재귀
}else {
return search(p->Right, key);
}
}
// 시간 : O(lg N)- 삽입 (Insert)
if(Root == NULL) Root = p
else Insert(Root,p) // 현재 방문중인 노드 -> x != NULL
Insert(Node *x, Node *p)
{
if(p->Data == x->Data) return; // 이미 있다.
if(p->Data < x->Data){ // 왼쪽 삽입 예정
if(x->Left == NULL) x->Left = p;
else Insert(x->Left, p);
}else { // 오른쪽 삽입 예정
if(x->Right == NULL) x->Right = p;
else Insert(x->Right, p);
}
}
// 시간 O(lg N)- 삭제 (Delete)
6. 균형잡힌 이진 탐색 트리 : AVL Tree (Adelson - Velskii & Landis, 1962)
모든 Node의 좌우 Subtree의 높이 차가 1 이내일 때 균형 이진 탐색 트리 (Balanced BST)로서 검색, 삽입 삭제가 모두 O(lg N)에 가능 (= 최악의 경우가 없음)
- 균형인수 (Balanced factor = 좌우 높이 차) = (왼쪽 subtree 높이) - (오른쪽 subtree 높이) (-1 <= 균형인수 <= 1) -> 균형
- 초기 AVL은 삽입 / 삭제 후 균형이 깨질 수 있다.
-> 4가지 rotation (회전)으로 rebalancing (재균형) 한다. (LL, LR, RL, RR)
- Algoritms for 4 Rotations
Node X, A, B, T1, T2, T3, T4
