[알고리즘] 탐색트리(2) - 예제

[문제1] 이진탐색트리를 구현하는 프로그램

- 삽입(i) : 키를 받아 노드생성 및 트리에 삽입

- 삭제(d) : 키를 받아 트리에 존재하면 해당 노드 삭제후 키를 출력, 없다면 X를 출력

- 탐색(s) : 키를 받아 트리에 존재하면 해당 키를 출력, 없다면 X를 출력

- 출력(p) : 현재 트리를 전위순회로 출력

- 종료(q) : 프로그램 종료

입력예시              출력예시

i 3 i 2 i 7 s 4 i 6 p i 5 s 6 q	X  3 2 7 6  6
i 9 i 2 i 15 i 1 i 7 i 11 i 5 i 8 i 3 i 4 p d 2 d 13 p q	9 2 1 7 5 3 4 8 15 11  2 X  9 3 1 7 5 4 8 15 11

#include<stdio.h> #include<stdlib.h> struct node{ int key; struct node *parent; struct node *lChild; struct node *rChild; }; int isExternal(struct node *w) { if ((w->lChild == NULL) && (w->rChild == NULL)) { return 1; } else { return 0; } } int isInternal(struct node *w) { if ((w->lChild != NULL) && (w->rChild != NULL)) { return 1; } else { return 0; } } struct node* sibling(struct node *w) { if (w->parent == NULL) { return; } if (w->parent->lChild == w) { return w->parent->rChild; } else { return w->parent->lChild; } } struct node* inOrderSucc(struct node *w) { w = w->rChild; if (isExternal(w)) { return; } while (isInternal(w->lChild)) { w = w->lChild; } return w; } void reduceExternal(struct node *root, struct node *z) { struct node *w, *zs, *g; w = z->parent; zs = sibling(z); if (w->parent == NULL) { root->lChild = zs->lChild; root->rChild = zs->rChild; root->lChild->parent = zs; root->rChild->parent = zs; zs->parent = NULL; } else { g = w->parent; zs->parent = g; if (w == g->lChild) { g->lChild = zs; } else if (w == g->rChild) { g->rChild = zs; } } free(z); free(w); return zs; } struct node* treeSearch(struct node *w, int k) { if (isExternal(w)) { return w; } if (w->key == k) { return w; } else if (w->key > k) { return treeSearch(w->lChild, k); } else { return treeSearch(w->rChild, k); } } void insertItem(struct node *w, int k) { struct node *lChildNode = (struct node*)malloc(sizeof(struct node)); struct node *rightChildNode = (struct node*)malloc(sizeof(struct node)); struct node *p = treeSearch(w, k); p->key = k; p->lChild = lChildNode; p->rChild = rightChildNode; lChildNode->parent = p; rightChildNode->parent = p; lChildNode->lChild = NULL; lChildNode->rChild = NULL; rightChildNode->lChild = NULL; rightChildNode->rChild = NULL; } int removeElement(struct node *w, int k) { struct node *p = treeSearch(w, k); struct node *z, *y; int e; if (isExternal(p)) return -1; e = p->key; z = p->lChild; if (!isExternal(z)) z = p->rChild; if (isExternal(z)) reduceExternal(p, z); else { y = inOrderSucc(p); z = y->lChild; p->key = y->key; reduceExternal(p,z); } return e; } void printTree(struct node *w) { if (isExternal(w)) { return; } else { printf(" %d", w->key); printTree(w->lChild); printTree(w->rChild); } } void freeTree(struct node *w) { if (isExternal(w)) { return; } else { freeTree(w->lChild); freeTree(w->rChild); free(w); } } void main() { char text; int key, value; struct node *w = (struct node*)malloc(sizeof(struct node)); w->parent = NULL; w->lChild = NULL; w->rChild = NULL; while (1) { scanf("%c", &text); if (text == 'i') { scanf("%d", &key); insertItem(w, key); getchar(); } else if (text == 'd') { scanf("%d", &key); value = removeElement(w, key); if (value == -1) { printf("X\n"); } else { printf("%d\n", value); } getchar(); } else if (text == 's') { scanf("%d", &key); if (treeSearch(w, key)->key != key) { printf("X\n"); } else { printf("%d\n", treeSearch(w, key)->key); } getchar(); } else if (text == 'p') { printTree(w); printf("\n"); } else if (text == 'q') { break; } } freeTree(w); }

[문제2] AVL트리를 구현하는 프로그램

- 삽입(i) : 키를 받아 노드생성 및 트리에 삽입

- 삭제(d) : 키를 받아 트리에 존재하면 해당 노드 삭제후 키를 출력, 없다면 X를 출력

- 탐색(s) : 키를 받아 트리에 존재하면 해당 키를 출력, 없다면 X를 출력

- 출력(p) : 현재 트리를 전위순회로 출력

- 종료(q) : 프로그램 종료

입력예시       출력예시

i 9 i 31 i 66 i 30 i 1 s 30 i 24 p s 47 i 61 d 30 i 13 q

30  30 9 1 24 31 66 X  30

#include<stdio.h> #include<stdlib.h> struct node { int key; int height; struct node *lChild; struct node *rChild; struct node *parent; }; struct node *root; int isExternal(struct node *w) { if ((w->lChild == NULL) && (w->rChild == NULL)) { return 1; } else { return 0; } } int isInternal(struct node *w) { if ((w->lChild != NULL) && (w->rChild != NULL)) { return 1; } else { return 0; } } struct node* sibling(struct node *w) { if (w->parent == NULL) { return; } if (w->parent->lChild == w) { return w->parent->rChild; } else { return w->parent->lChild; } } struct node* inOrderSucc(struct node *w) { w = w->rChild; if (isExternal(w)) { return; } while (isInternal(w->lChild)) { w = w->lChild; } return w; } void expandExternal(struct node *w) { struct node *leftnode = (struct node*)malloc(sizeof(struct node)); struct node *rightnode = (struct node*)malloc(sizeof(struct node)); leftnode->lChild = NULL; leftnode->rChild = NULL; leftnode->height = 0; leftnode->parent = w; rightnode->lChild = NULL; rightnode->rChild = NULL; rightnode->height = 0; rightnode->parent = w; w->lChild = leftnode; w->rChild = rightnode; w->height = 1; return; } struct node *reduceExternal(struct node *z) { struct node *p, *zs, *g; p = z->parent; zs = sibling(z); if (p->parent == NULL) { root = zs; zs->parent = NULL; } else { g = p->parent; zs->parent = g; if (p == g->lChild) g->lChild = zs; else if (p == g->rChild) g->rChild = zs; } free(z); free(p); return zs; } struct node* treeSearch(struct node *w, int k) { if (isExternal(w)) return w; if (w->key == k) return w; else if (w->key > k) return treeSearch(w->lChild, k); else return treeSearch(w->rChild, k); } int updateHeight(struct node *w) { int height; if (w->lChild->height > w->rChild->height) { height = w->lChild->height + 1; } else { height = w->rChild->height + 1; } if (height != w->height) { w->height = height; return 1; } else { return 0; } } int isBalanced(struct node *w) { if ((-1 <= (w->lChild->height - w->rChild->height)) && ((w->lChild->height - w->rChild->height) <= 1)) { return 1; } else { return 0; } } struct node* restructure(struct node *x, struct node *y, struct node *z) { struct node *a, *b, *c; struct node *T0, *T1, *T2, *T3; if ((z->key < y->key) && (y->key < x->key)) { a = z; b = y; c = x; T0 = a->lChild; T1 = b->lChild; T2 = c->lChild; T3 = c->rChild; } else if ((x->key < y->key) && (y->key < z->key)) { a = x; b = y; c = z; T0 = a->lChild; T1 = a->rChild; T2 = b->rChild; T3 = c->rChild; } else if ((z->key < x->key) && (x->key < y->key)) { a = z; b = x; c = y; T0 = a->lChild; T1 = b->lChild; T2 = b->rChild; T3 = c->rChild; } else { a = y; b = x; c = z; T0 = a->lChild; T1 = b->lChild; T2 = b->rChild; T3 = c->rChild; } if (z->parent == NULL) { root = b; b->parent = NULL; } else if (z->parent->lChild == z) { z->parent->lChild = b; b->parent = z->parent; } else if (z->parent->rChild == z) { z->parent->rChild = b; b->parent = z->parent; } a->lChild = T0; T0->parent = a; a->rChild = T1; T1->parent = a; updateHeight(a); c->lChild = T2; T2->parent = c; c->rChild = T3; T3->parent = c; updateHeight(c); b->lChild = a; a->parent = b; b->rChild = c; c->parent = b; updateHeight(b); return b; } void searchAndFixAfterInsertion(struct node *w) { struct node *x, *y, *z; w->lChild->height = 0; w->rChild->height = 0; w->height = 1; if (w->parent == NULL) { return NULL; } z = w->parent; while (updateHeight(z) && isBalanced(z)) { if (z->parent == NULL) { return; } z = z->parent; } if (isBalanced(z)) { return; } if (z->lChild->height > z->rChild->height) { y = z->lChild; } else { y = z->rChild; } if (y->lChild->height > y->rChild->height) { x = y->lChild; } else { x = y->rChild; } restructure(x, y, z); return; } void insertItem(struct node *w, int k) { struct node *p = treeSearch(w, k); if (isInternal(p)) { return; } else { p->key = k; expandExternal(p); searchAndFixAfterInsertion(p); } } void searchAndFixAfterRemoval(struct node *w) { struct node *x, *y, *z, *b; if (w == NULL) { return; } z = w; while (updateHeight(z) && isBalanced(z)) { if (z->parent == NULL) { return; } z = z->parent; } if (isBalanced(z)) { return; } if (z->lChild->height > z->rChild->height) { y = z->lChild; } else { y = z->rChild; } if (y->lChild->height > y->rChild->height) { x = y->lChild; } else if (y->lChild->height < y->rChild->height) { x = y->rChild; } else { if (z->lChild == y) { x = y->lChild; } else if (z->rChild == y) { x = y->rChild; } } b = restructure(x, y, z); searchAndFixAfterRemoval(b->parent); } int removeElement(struct node *w, int k) { struct node *p = treeSearch(w, k); struct node *z, *zs, *y; int e; if (isExternal(p)) { return -1; } e = p->key; z = p->lChild; if (!isExternal(z)) { z = p->rChild; } if (isExternal(z)) { zs = reduceExternal(z); } else { y = inOrderSucc(p); z = y->lChild; p->key = y->key; zs = reduceExternal(z); } searchAndFixAfterRemoval(zs->parent); return e; } void printTree(struct node *w) { if (isExternal(w)) { return; } else { printf(" %d", w->key); printTree(w->lChild); printTree(w->rChild); } } void freeTree(struct node *w) { if (isExternal(w)) { return; } else { freeTree(w->lChild); freeTree(w->rChild); free(w); } } void main() { char text; int key, value; root = (struct node*)malloc(sizeof(struct node)); root->parent = NULL; root->lChild = NULL; root->rChild = NULL; while (1) { scanf("%c", &text); if (text == 'i') { scanf("%d", &key); insertItem(root, key); getchar(); } else if (text == 'd') { scanf("%d", &key); value = removeElement(root, key); if (value == key) { printf("%d\n", value); } else { printf("X\n"); } getchar(); } else if (text == 's') { scanf("%d", &key); if (treeSearch(root, key)->key != key) { printf("X\n"); } else { printf("%d\n", treeSearch(root, key)->key); } getchar(); } else if (text == 'p') { printTree(root); printf("\n"); } else if (text == 'q') { break; } } freeTree(root); }