자료구조 :: 트리(4) 이진탐색트리

# 이진탐색트리

BinarySearchTree.cpp

이진탐색트리(BST)의 정의
(1) 모든 원소의 키는 유일하다.
(2) 왼쪽 서브 트리의 키들은 루트의 키보다 작다.
(3) 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
(4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

탐색 연산
(1) 이진탐색트리가 공백상태이면 탐색실패
(2) 탐색키가 현재 트리의 루트 키값과 같으면 루트 반환
(3) 탐색키값과 루트 키값을 대소비교 하여 작을경우 왼쪽, 큰경우는 오른쪽 서브트리를 반복적으로 탐색

삽입 연산
(1) 전체 트리에서 키값이 없는지 탐색, 탐색이 실패한 곳의 위치가 삽입되어야 할 곳
(2) 탐색이 성공하면 삽입 불가
(3) 만약 탐색이 실패한곳의 부모노드가 NULL이라면 루트로 삽입
(3) 부모노드의 키값과 비교하여 작으면 왼쪽 크면 오른쪽 자식으로 연결

삭제 연산
(1) 삭제하려는 노드가 단말노드인 경우
(2) 삭제하려는 노드가 하나의 서브 트리만 가지고 있는 경우
(4) 삭제하려는 노드가 두개의 서브 트리를 가지고 있는 경우

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

typedefstruct TreeNode 
{ 
int key; 
    TreeNode *left,*right; 
}TreeNode; 

TreeNode* SearchNode(TreeNode *node, int key) 
{ 
while(node!=NULL) 
    { 
if(key == node->key)  
return node; // 검색 성공
elseif(key < node->key) 
            node=node->left; 
else node=node->right; 
    } 
returnNULL; // 검색 실패
} 

int InsertNode(TreeNode **root,int key) // root의 변경이 일어남
{ 
    TreeNode *p=NULL,*t=*root; 
    TreeNode *temp; 

while(t!=NULL) // key값 검사
    { 
        p=t; 
if(key == t->key) 
        { 
// printf("같은 key값이 존재, 삽입실패");
return -1; 
        } 
elseif(key < t->key) 
            t=t->left; 
else
            t=t->right; 
    } 

    temp=(TreeNode*)malloc(sizeof(TreeNode)); 

if(temp) 
    { 
        temp->key=key; 
        temp->left=temp->right=NULL; 
    } 

if(p!=NULL) // p는 데이터를 삽입할 노드의 부모노드
    { 
if(key < p->key) 
            p->left=temp; 
else
            p->right=temp; 
    } 
else
        *root=temp; // 루트에 삽입

return1; 
} 

int DeleteNode(TreeNode **root, int key) 
{ 
    TreeNode *p=NULL,*t=*root; 
    TreeNode *child,*sub_p,*sub; 

while(t!=NULL && t->key!=key) // key를 가진 노드 검색
    { 
        p=t; // key를 가진 노드의 부모노드를 저장
        t=(key < t->key) ? t->left : t->right; 
    } 

if(t==NULL) 
    { 
        printf("key is not in the tree\n"); 
return -1; 
    } 

if(t->left == NULL && t->right == NULL) // 단말노드인 경우
    { 
if(p!=NULL) 
        { 
if(p->left == t) 
                p->left = NULL; 
else
                p->right = NULL; 
        } 
else
            *root = NULL; // 부모노드가 NULL이면 루트
    } 
elseif(t->left == NULL || t->right == NULL) // 하나의 자식을 가지는 경우
    { 
        child = (t->left != NULL) ? t->left : t->right; 
if(p!=NULL) 
        { 
if(p->left == t) // 현재노드의 자식노드를 현재노드 부모와 연결
                p->left = child; 
else
                p->right = child; 
        } 
else
            *root = child; // 부모노드가 NULL이면 루트
    } 
else// 두개의 자식을 가지는 경우
    { 
        sub_p = t; 
        sub = t->right; // 오른쪽에서 서브트리에서 찾는다

while(sub->left != NULL) // 오른쪽 서브트리 중 왼쪽 자식의 맨 끝이 후계자
        { 
            sub_p=sub;  
            sub=sub->left; 
        } 

if(sub_p->left == sub) // 후속자의 부모와 자식을 연결
            sub_p->left = sub->right;  
else
            sub_p->right = sub->right; 

        t->key=sub->key; // 후속자가 가진 키값을 현재 노드에 복사
        t=sub; // 후속자 변경
    } 

    free(t); 

return1; 
} 

void Display(TreeNode *p) 
{ 
if(p!=NULL) 
    { 
        Display(p->left); 
        printf("%d->",p->key); 
        Display(p->right); 
    } 
} 

int main() 
{ 
    TreeNode *root=NULL,*temp=NULL; 
int arr[10],i=0,tmp; 

    srand(time(NULL)); 

    printf("==============\n"); 

for(i=0;i<10;i++) 
        arr[i]=rand()%100+rand()%100; 

for(i=0;i<10;i++) 
    { 
        InsertNode(&root,arr[i]); 
        printf("%d번 삽입 : %d\n",i+1,arr[i]); 
    } 
    printf("==============\n"); 
    printf("루트 노드 key : %d\n",root->key); 
    printf("==============\n"); 
    printf("탐색 데이터 입력 : "); 
    scanf("%d",&tmp); 
    temp=SearchNode(root,tmp); 

if(temp!=NULL) 
        printf("탐색 결과 : %d\n",temp->key); 
else
        printf("key is not in the tree\n"); 

    printf("==============\n"); 
    printf("전체 출력 : "); 
    Display(root); 
    printf("\n==============\n"); 

for(i=0;i<10;i++) 
        DeleteNode(&root,arr[i]); 

return0; 

}