자료구조 기말고사 정리(이진 탐색 트리)
* 탐색 알고리즘
SearchBST(B, x){
//B는 이진 탐색 트리, x는 탐색 키값
p = B;
if(p==NULL) return null;
if(p->key == x) return p;
if(p->key < x) return searchBST(p->right, x);
else return searchBST(p->left, x);
}
* 삽입 알고리즘
insertBST(B, x) { //B는 이진 탐색 트리, x는 삽입할 키 값
p = B;
while(! p == null){
if(x = p->key) return x;
q <- p; //q는 p의 부모노드를 나타냄
if(x < p->key) p=p->left;
else p=p->right;
}
anode = getNode();
anode->key = x;
anode->right = null;
anode->left = null;
if(B==null) B=newNode;
else if(x < q->key) q->left = newNode;
else q->right = newNode;
return anode;
}
* 삭제 알고리즘
deleteBST(B, x){ // 왼쪽 서브트리에서 최대 노드 값으로 대체시
p = the node to be deleted
parent = the parent node of p;
if(p=null) return false;
if(p->left==null && p->right==null) {
if(parent->left = p) parent->left = null
else parent->right=null
}
if(p->left==null || p->right==null){
if(p->left != null){
if(parent->left == p) parent->left = p->left;
else parent->right = p->left;
} else {
if(parent->left == p) parent->left = p->right;
else parent->right = p->right;
}
}
if(p->left != null && p->right != null){
q = maxNode(p->left); //왼쪽 서브트리에서 최대 키값을 갖는 원소 탐색
p->key = q->key;
deleteBST(p->left, p->key);
}
}
* 순환 삽입 알고리즘
TreeNode insertKey(TreeNode R, char x){
TreeNode *T = R;
if(T == NULL){
TreeNode anode = getNode();
anode->key = x;
return anode;
} else if( compare(x, T->key) < 0){
T->left = insertKey(T->left, x);
return T;
} else if( compare(x, T->key) > 0){
T->right = inserKey(T->right, x);
return T;
} else return T;
}
* 키 값 찾는 알고리즘
TreeNode find(TreeNode R, char x){
TreeNode T = R;
int result;
while(T != null){
if((compareTo(T->key, x) <0){ // x가 T->key 값보다 작으면
T = T->left;
} else if (result == 0){
return T;
} else {
T = T->right;
}
}
return T;
}
* 히프 삽입 알고리즘
insertHeap(Heap, e){
// 순차 표현으로 구성된 최대 히프
// 원소 e를 히프 Heap에 삽입, n은 현재 히프의 크기(원소 수)
if(n=maxSize) heapFull(); //히프가 만원이면 히프 크기를 확장
n <- n+1; // 새로 첨가될 노드 위치
for(i<-n;;)do{
if(i=1) exit; //루트에 삽입
if(e.key <= Heap[i/2].key) exit; //삽입할 노드의 키값과 부모 노드의 키값을 비교
Heap[i] <- Heap[i/2];//부모 노드의 키값을 자식 노드로 이동
i <- [i/2];
}
Heap[i] <- e;
}
* 히프 삭제 알고리즘
deleteHeap(Heap){
//히프로부터 원소삭제, n은 현재 히프 크기(원소 수)
if(n==0) return null;
e <- Heap[1]; //삭제할 원소
x <- Heap[n]; //이동시킬 원소
n <- n-1; // 히프 크기를 하나 감소
i = 1;
j <- 2; //j는 i의 왼쪽 자식 노드
while(j <= n) do{
if( j<n) then if (Heap[j].key < Heap[j+1].key)
then j <- j+1; //j는 값이 큰 자식을 가리킨다.
if(x.key >= Heap[j].key) exit;
Heap[i] <- Heap[j]; //자식을 한 레벨 위로 이동
i <- j;
j <- j*2; //i와 j를 한 레벨 아래로 이동
}
Heap[i] <- x;
return e;
}
* 완전 이진 트리를 히프로 변환하는 알고리즘
makeTreeHeap(H, n){
//H는 히프가 아닌 완전 이진 트리
for(i <- n/2; i>= 1; i--) do{
// 각 내부 노드에 대해 레벨 순서의 역으로
p = i;
for(j=2*p; j<= n; j=2*j) do {
//p의 자손들 탐색
if(j < n) then
if(H[j] < H[j+1]) then j =j+1;
if(H[p] >= H[j]) exit;
H[p] = H[j]; //자식을 부모로
p=j; //부모 노드를 한 레벨 밑으로 이동
}
H[p] = H[i];
}
}