0x05.탐색 알고리즘(3):이진 탐색트리

3. 이진 탐색트리

이진트리는 다음의 성질중 하나를 반드시 만족한다.

ⓐ 자식을 갖지 않음

ⓑ 왼쪽 자식 하나만 가짐

ⓒ 오른쪽 자식 하나만 가짐

ⓓ 왼쪽과 오른쪽 자식 모두를 가짐

 

이진 탐색 트리의 개념은 왼쪽과 오른쪽으로 나뉜다. 왼쪽에 있는 자식과 그 자식의 자식들이 가지고 있는 데이터들은 정점의 데이터(그림의 15)보다 값이 작고, 오른쪽에 있는 자식과 그 자식의 자식들이 가지고 있는 값들은 정점보다 크다.

말로 표현하려면 여러운데, 왼쪽의 그림으로 보면 조금 쉬울 수 있다.

루트의 왼쪽 자식의 값은 루트 값인 15보다 작은 12이며, 오른쪽은 더 큰 값인 19이다. 또한 12(왼쪽 서브트리)의 자손들의 값은 9, 13, 14로 루트 값인 15보다 작다. 

정점(루트)의 입장에서보면 왼쪽 서브트리의 값들은 모두 자기가 가진 값보다 작고, 오른쪽 서브트리의 값들은 모두 크다는 점을 알 수 있다.

이진 탐색 트리의 기본 설정은 다음과 같다.

typedef int keytype;

typedef char othertype;

typedef structnode tree;

struct node{

   keytype key;

   othertype otherinfo;

   tree *left, *right;

};

tree root;

위에서의 root는 이진 탐색트리의 루트의 포인터 값으로 탐색의 출발점이 된다. 정점의 왼쪽 또는 오른쪽 자식이 없으면 left 또는 right의 값으로 NULL이 들어간다.

① 탐색 알고리즘

탐색은 예상되듯이 아주 간단하다. root부터 출발하는데, target값보다 데이터 값이 작으면 왼쪽으로, 크면 오른쪽으로 이동하면 된다. 물론 root의 데이터 값과 일치하면 탐색이 끝난다. 만약 자식이 없어서 NULL값을 만나게 되면 탐색은 실패로 끝난다.

tree *search(keytype target, tree *p){

   if(p==NULL){

       tree=NULL;

       return tree;

   }

   else if(target==p>key)

       tree=p;

   else if(arget<p->key)

       return search(target,p->left);

   else

       return search(target,p->right);

}

② 삽입 알고리즘

새 데이터는 다음과 같이 삽입한다.

void insert(keytype x, othertype y, tree *p){

   if(p==NULL){

       p=(tree*)malloc(sizeof(tree));

       p->key=x;

       p->otherinfo=y;

       p->left=NULL;

       p->right=NULL;

   }

   else if(x==p->key)

       exit(1);

   else if(x<p->key)

       insert(x,y,p->left);

   else

       insert(x,y,p->right);

}

p는 새 데이터를 넣어야 할 서브트리이다. insert 함수를 통해 데이터를 삽입할 장소를 찾는데, NULL 값을 만나면 서브트리가 없다는 뜻이므로 삽입하려는 데이터로 트리를 구성하고, 이미 삽입하려는 값이 존재하는 경우에는 비정상 종료를 시킨다. 그 외의 경우는, 재귀를 통해 결국 언젠가는 NULL 값을 만나 데이터 트리가 구성된다.

③ 삭제 알고리즘

void delete(keytype x, tree *p){

   tree r, tmp;

   if(*p=NULL)

       exit(1);

   else if(x!=p->key){                 //키 값과 다른경우

       if(x<p->key)

           delete(x,p->left);

       else

           delete(x,p->right);

   }

   else{                                  //키 값과 일치할 경우

       if(p->left==NULL){

           tmp=*p;

           *p=p->right;

          dispose(tmp);

       }

       else{

           r=extractmax(p->left);

           r->left=p->left;

           r->right=p->right;

           p=r;

       }

   }

}

tree *extractmax(tree *q){

   if(q->right=NULL){

       *q=q->left;

       return q;

   }

   else

       return extractmax(q->right);

}