[자료구조]이진탐색트리-Binary Search Tree

알고리즘 - 이진탐색

이진탐색(Binary Search)은 탐색 기법중 하나입니다.

이 알고리즘을 위해 우리는 이진트리(Binary Tree)를 사용하는데 이진트리는 아시다시피 다음 그림과 같습니다.

이진트리(Binary Tree)는 각 Node에 Sibling의 최대 개수가 2개입니다.

이 Binary Tree에

"좌측 노드에는 부모보다 작은 Value를, 우측 노드에는 부모보다 큰 Value를 갖는다."

라는 규칙을 정하면 이진 탐색 트리로 사용할 수 있습니다.

Binary Search Algorithm의 시간복잡도(Time Complexity)는 O(lg n)으로 탐색중 가장 빠릅니다.

(물론, O(1)의 Hash 탐색을 제외!!)

(Wikipedia 인용)

트리의 구현은 다양한 방법이 있지만 배열(Array)을 사용하는 것이 가장 편리합니다~(아무래도 익숙하니깐)

하지만 여기서는 포인터를 사용해봤습니다, 아무래도 메모리도 동적이구..

실제로 구현만 해놓으면 배열보다는 편리하기 때문입니다.

일단 기본 소스는 다음과 같구 이걸 구조적으로 분석해서 포스팅하겠습니다.

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using namespace std; typedef struct astr { int key; char name[50]; } element; typedef struct anod* Ty_Node_Ptr; //anod에 대한 포인터를 Ty_Node_Ptr로 선언 typedef struct anod { element data; //노드의 데이타 부분 Ty_Node_Ptr leftChild, rightChild; //노드의 좌측, 우측 자식에 대한 포인터 } Ty_Node; Ty_Node_Ptr ROOT = NULL; /*insert_node함수 파라미터에 Ty_Node_Ptr& tr을 넣는 이유*/ /*tr 그 자체의 메모리를 변경해야 하기때문에 참조형식으로 직접참조를 한다.*/ void insert_node(Ty_Node_Ptr& tr, int key, char* name) { bool Child = true; //삽일할 노드의 부모에게 있어서 삽입되는 자식이 왼쪽인지 오른쪽인지 알려주는 임시 변수 Ty_Node* node = (Ty_Node*)malloc(sizeof(Ty_Node)); node -> leftChild = node -> rightChild = NULL; node -> data.key = key; strcpy(node -> data.name, name); //초기화 과정 [지정된 key, name에 대한 노드이므로..] Ty_Node_Ptr p = tr, temp = NULL; //삽입준비. 삽입할 부분을 찾는데 있어 p라는 임시변수가 필요. if (p==NULL) { tr = node; //만약 p = NULL이면 그대로 삽입 후 종료한다. return; } while (p != NULL) { //말단노드에 도착할때까지.. if (strcmp(name, p -> data.name) > 0) { temp = p; //temp에 p의 내용을 복사해 놓는다. 여기서 temp는 항상 p라는 탐색노드의 부모 노드이다. p = p -> rightChild; //p에는 strcmp가 0보다 크닌깐 p의 오른쪽에다가 삽입해준다. Child = true; } else { temp = p; p = p -> leftChild; Child = false; } } if (Child) temp -> rightChild = node; else temp -> leftChild = node; } //중위탐색기법 void in_order(Ty_Node_Ptr ptr) { if (ptr -> leftChild) { in_order(ptr -> leftChild); //ptr의 왼쪽 자식이 있으면 그 자식을 따라간다. } printf("%s %d\n", ptr -> data.name, ptr -> data.key); //왼쪽 자식이 마무리 되었으면 자기자신을 그냥 출력한다. if (ptr -> rightChild) in_order(ptr -> rightChild); //이후 오른쪽 자식을 따라간다 } //파일로부터 읽어준다. void insert_from_file(Ty_Node_Ptr &tr, char* file) { FILE* fp = fopen(file, "rt"); while (!fp){ printf("File Not Exist, Input again : "); scanf("%s",file); getchar(); fp = fopen(file,"rt"); } while (!feof(fp)) { //파일 종료까지.. int key; char name[50]; fscanf(fp, "%d %s\n", &key, name); //각 줄을 모두 읽어드려 트리에 저장한다. insert_node(tr, key, name); } } //name을 가진 노드를 찾는 과정 Ty_Node_Ptr search_node(Ty_Node_Ptr tr, char* name) { if (tr == NULL) return NULL; if (strcmp(tr -> data.name, name) == 0) { printf("%d %s\n",tr -> data.key,name); return tr; //tr이 찾은 노드이다. 그 tr의 포인터를 반환한다. } //if (!((tr-> rightChild) || (tr-> leftChild))) return NULL; //찾지 못했는데 자식노드도 없어[터미널 노드여서] 더 이상 갈 곳이 없을때.. 즉, 찾기 실패한 상황.. if (strcmp(tr -> data.name, name) > 0) return search_node(tr -> leftChild, name); else return search_node(tr -> rightChild, name); } //name을 가진 노드를 tr에서 찾아 삭제하는 함수 bool delete_node(Ty_Node_Ptr tr, char* name) { Ty_Node_Ptr parent = tr; bool Child = true; while (tr) { if (strcmp(tr -> data.name, name) < 0) { //찾아야 하는 것이 더 크다. 즉, 오른쪽 노드로 간다. parent = tr; //부모 노드는 항상 설정해 주어야 한다. tr = tr -> rightChild; Child = true; //삭제할 노드가 그 노드 본래의 부모의 오른쪽 자식 노드임을 알려줌의 임시변수. } else if (strcmp(tr -> data.name, name) == 0) { //찾아야 하는것과 같다. 즉, 현재 노드를 deletion해준다. if (tr -> leftChild && tr -> rightChild) { //삭제할 노드에게 자식노드가 모두 딸려있는 경우 Ty_Node_Ptr temp = tr -> rightChild; //temp는 후계자노드 Ty_Node_Ptr tmp_parent = NULL; //tmp_parent는 후계자노드의 부모노드 while (temp -> leftChild) { //후계자를 찾아서 계속 왼쪽으로 이동 tmp_parent = temp; //leftChild로 내려가기 전에 temp값을 tmp_parent값에 넣어준다. [안그러면 후계자노드의 부모노드를 알수가 없다] temp = temp -> leftChild; //후계자노드에는 tmp_parent의 왼쪽자식 값을 넣어준다. 즉, 이렇게해서 왼쪽노드의 자식이 NULL을 가질때까지 반복 } tr -> data = temp -> data; tmp_parent -> leftChild = NULL; free(temp); } else if (tr -> leftChild) { //왼쪽 자식만 있는 경우 -> 그대로 올려줌. if (Child) //만약 삭제할 노드가 삭제할 노드의 부모노드의 오른쪽 자식노드이라면.. parent -> rightChild = tr -> leftChild; else parent -> leftChild = tr -> leftChild; if (parent == tr) ROOT = tr -> leftChild; free(tr); } else if (tr -> rightChild) { //오른쪽 자식만 있는 경우. if (Child) parent -> rightChild = tr -> rightChild; else parent -> leftChild = tr -> rightChild; if (parent == tr) ROOT = tr -> rightChild; free(tr); } else { //자식이 없는 경우 [그냥 부모 노드의 포인터를 지워주고 free하면 된다.] if (Child)parent -> rightChild = NULL; else parent -> leftChild = NULL; free(tr); } return true; } else { parent = tr; tr = tr -> leftChild; Child = false; } } return false; //삭제가 성공한것! } //name을 가진 노드의 level을 찾는다. int get_level(Ty_Node_Ptr tr, char* name, int level) { if (strcmp(tr ->data.name, name) == 0) return level; //찾았으면 성공! if (!(tr -> rightChild) && !(tr -> leftChild)) return -1; //찾지 못함! if (strcmp(tr -> data.name, name) < 0) return get_level(tr -> rightChild, name, level + 1); else return get_level(tr -> leftChild, name, level + 1); } //자식 노드를 찾는다. bool get_sibling(Ty_Node_Ptr tr, char* name) { Ty_Node_Ptr temp = search_node(tr, name); //찾아서 그 노드의 포인터를 불러온다. if (temp) { if (temp -> leftChild) printf("왼쪽 자식 노드 : %s %d\n", temp -> leftChild -> data.name, temp -> leftChild -> data.key); if (temp -> rightChild) printf("오른쪽 자식 노드 : %s %d\n", temp -> rightChild -> data.name, temp -> rightChild -> data.key); if (!(temp -> leftChild) && !(temp -> rightChild)) puts("자식 노드가 없습니다.\n"); puts(""); return true; } return false; //찾지 못한 경우 } //노드의 가장 큰 높이[level]을 반환 int get_height(Ty_Node_Ptr tr) { //static int tt = 0; if (tr) return 1 + max(get_height(tr -> leftChild), get_height(tr -> rightChild)); else return 0; } int main() { char filename[100], ch, name[50], key; puts("Enter the name of the file. ex - sdata.txt"); scanf("%s", filename); //파일 이름 입력 insert_from_file(ROOT, filename); //파일에서 각 줄을 입력받아 각각의 노드를 생성함. while (true) { printf("명령을 입력하세요 [i, p, d, s, v, b, h, e] : "); //각각의 입력마다 fflush로 전부 스택을 초기화 한다. fflush(stdin); //scanf의 특성상 %c를 받으면 enter키의 ASCII도 함께 입력되서 반례가 발생한다. scanf("%c", &ch); switch (ch) { case 'i' : scanf("%s%d", name, &key); insert_node(ROOT, key, name); printf("Successful insertion..\n\n"); break; case 'p' : printf("In-order traversal starting..\n\n"); in_order(ROOT); break; case 'd' : scanf("%s", name); if (delete_node(ROOT, name)) puts("Deleting success..\n\n"); else printf("Failed to delete..\n\n"); break; case 's' : scanf("%s", name); if(!search_node(ROOT, name)) printf("%s can not be found..\n\n", name); break; case 'v' : int v; scanf("%s", name); v = get_level(ROOT, name, 1); if (v == -1) printf("%s can not be found..\n\n", name); else printf("The height of %s = %d\n\n", name, v); break; case 'b' : scanf("%s", name); if (!get_sibling(ROOT, name)) printf("%s can not be found..\n\n", name); break; case 'h' : printf("height = %d\n\n", get_height(ROOT)); break; case 'e' : exit(0); } fflush(stdin); } return 0; }