이진검색트리(Binary Search Tree)

<이진검색트리(Binary Search Tree)>
- 이진 트리는 노드에 저장된 데이터의 크기와 무관히 데이터가 노드에 위치되었다
  - 그러나 이진트리의 응용에서는 이진트리를 사용하여 데이터를 트리 내에 저장하고
    검색, 삭제하는 연산이 많이 사용
 
- 이진 검색 트리
  - 데이터의 크기에 따라 트리 내부에 저장되는 위치가 결정되고 검색이나 삭제 시에도 데이터의 크기에
    따라서 검색의 경로가 결정되는 구조
  - 이진 검색트리에서 데이터를 크기에 따라 저장될 위치를 결정하기 위한 조건이 먼저 지정되어야 한다

- 조건
  1. 루트 노드의 데이터값은 왼쪽 부트리의 모든 노드보다 크거나 같다
  2. 로트 노드의 데이터값은 오른쪽 부트리의 모든 노드의 데이터 값보다 작다
  3. 모든 부트리에서 위의 두 조건을 만족한다 


<하나의 노드를 표현하기 위한 구조체 구조>
struct list{
  strunct list*left;
  int data;
  struct list*right; //자신과 구조체 자신과 같은 주소체를 저장, 이름은 right(이름은 관련 없다, a라고 써도된다)
};
- 구조체 구성원의 순서는 상관없다
- 논리적 구조이므로 위치도 상관없다



<Binary Search Tree의 구현>
struct list{
  struct list*left; //리스트(구조체)의 주소를 가리키는 left
  int data;
  struct list*right; //리스트(구조체)의 주소를 가리키는 right
};
struct list*p, x; //리스트(구조체)의 주소를 가리키는 p, x는 구조체형 변수(즉, x는 구조체 자신을 가리킨다)
p=(struct list*)malloc(sizeof(struct list)); //p는 구조체 리스트의 주소를 가리키고 list구조체의 사이즈만큼 동적메모리 할당

p->data=50; //p의 주소값 필드에 50을 넣어라
x.data=30; //x라는 변수에 데이터 요소에 30을 대입

p=&x; //p에다가 x의 주소값을 넣어라
p->data=40; //p의 주소값 필드에 40을 넣어라


-----------------------------------------------
<이진검색트리의 순회 알고리즘>
int key; //main 함수 메뉴로 6개의 연산 실행
do{
  printf("Input(file-1) Input(keyboard)-2 Display-3 Search-4
          Delete-5 End-6\n");
  print("\n Select a key -->");  scanf("%d", &key);
  if(key==1){
  ...
  root=insert(root, data);
  }
  ....
  if(key==3){  //키보드에서 삽입할 데이터값을 입력받는다
    prnt(root, 1);
  }
  ....
  }while(key<6);

-----------------------------------------------
<이진검색트리의 구현(Original version : 저장데이터 - 문자열 데이터)
#include "stdio.h"
#include "string.h"
#define YES 1
#define NO 0
#define LIST struct list
  struct list{
    struct list *left
    char *name;
    char *tel;
     struct list *right;
};


<이진검색트리의 구현(Simple version : 저장데이터 - 정수)
#include "stdio.h"
#include "string.h"
  struct list{
    struct list *left;
    int data;
    struct list *right;
};

-----------------------------------------------
<이진검색트리의 입력 예제>

void main( ) 
{
struct list *root, *insert( ), *srch( ), *delet( ), *temp;
int key, data, sdata;
void prnt( ),inp( );
FILE *fp;
root= NULL;
do{   // 메뉴방식의 함수 호출
   printf("Input(file)-1 Input(keyboard)-2 Display-3 Search-4    
             Delete-5 End-6 \n");
   printf("\n Select a key --->");
   scanf("%d", &key);

if(key == 1) { //파일로부터의 입력수행은 1번만 진행한다
  printf("\n---input---\n");
  fp= fopen("binary.dat","r");
  if(fp != NULL) 
    while(fscanf(fp,"%d",&data) != EOF) {
      printf(“data=%d\n", data);
      root= insert(root, data);
    }
  else
    printf("fopen error\n");
 }

 if(key == 2) {     // 키보드에서 삽입할 데이터값을 입력받는다
    scanf("%d",&data);
    root= insert(root, data);
 }
 if(key == 3) {  // 순회(전순회, 중순회, 후순회 중 하나를 구현)
    printf("\n---display ---\n");
    printf("\nlevel   data\n");
    prnt(root, 1);  
 }
 if(key == 4) { // 검색
    printf("\n---search ---\n");
    printf(" data---> ");
    scanf("%d",&sdata); //사용자가 찾고자 하는 데이터를 받는다
    temp= srch(root, sdata); //srch라는 검색 알고리즘을 호출해서 &sdata와 비교해서 변수 temp에 넣는다
 }

 if(key == 5) {  // 삭제
     printf("\n---delete---\n");
     printf(" data---> ");
     scanf("%d",&sdata);
     root= delet(root, sdata); //delete라는 삭제 함수를 호출(삭제할 데이터가 말단인지 아닌지에 대해서 추가적으로 결정해야한다)
 }
 if(key == 6) {  // 프로그램 종료
    printf("\n---end---\n");
 }
}while(key < 6);
}
- 재귀적으로 트리를 순회하면서 입력위치를 결정
- 1번에서의 file 입력은 한 번만 수행되어야 한다

-----------------------------------------------
<메인함수로부터 이진검색트리의 삽입연산을 진행하는 과정>
void main( ) 
{
int key, data, sdata;
void prnt( ),inp( );
FILE *fp;
root= NULL; //존재하는 트리가 없다
do{   // 메뉴방식의 함수 호출
   printf("Input(file)-1 Input(keyboard)-2 Display-3 Search-4    
             Delete-5 End-6 \n");
   printf("\n Select a key --->");        scanf("%d", &key);
. . . . . . . . . . . . . . 
   if(key == 2) {     // 키보드에서 삽입할 데이터값을 입력받음
       scanf("%d",&data); //입력된 값이 data에 저장되고
       root= insert(root, data); //return값이 root노드의 값을 update하게 된다 
    }

struct list  *insert(struct list *rp, int data) //insert함수는 재귀함수로 구성되어있는 삽입 연산을 담당한다 
{
struct list *create_node( );
if(rp == NULL) {                      //트리가 비어있는 상태
   rp= create_node( );              //하나의 노드를 할당받아 
   rp->data= data;      rp->left= NULL;       rp->right= NULL;
}
else if( data == rp->data ) { //이미 데이터가 존재할 때(노드 포인터가 가리키는 데이터가 존재할 때) 
     printf(“Existing data %d\n”,data);
}
else if(data < rp->data )       //왼쪽 부트리로 이동
     rp->left= insert(rp->left, data); 
else                         //오른쪽 부트리로 이동
     rp->right= insert(rp->right, data);
return(rp);
}
-----------------------------------------------
struct list  *insert(struct list *rp, int data)
{
struct list *create_node( );
. . .
   rp= create_node( );   
   rp->data= data; //rootNode의(100번지의)데이터필드에 삽입할 데이터값(12)를 집어넣어라
   rp->left= NULL;       
   rp->right= NULL;
}

함수 호출 -> struct list *create_node( )
{
 char *malloc( );
  return((struct list *)malloc(sizeof(struct list )));
}
-----------------------------------------------
<최초 data 11 삽입 경우, rp(rootNode의 주소)는 900> -(호출)1번째, (돌아감)5번째

void main()
Null root Null data
root=insert(root, data)

struct list *insert(struct list*rp, int data)
A : if(rp==NULL){
  rp=create_node(); rp->data=data;
  rp->left=NULL;     rp->right=NULL;
B :
C :
D :
E : return(rp) //return을 하면, insert함수의 지역변수는 없어지지만 create_node()에 의해 노드구조는 남게된다

<최초의 루트노드를 생성 이후에 두 번째 data를 입력하는 경우> -(호출)2번째, (돌아감)4번째
struct list  *insert(struct list *rp, int data) //rp=900, data=5일 때
{
struct list *create_node();
if(rp == NULL) {                      //트리가 비어있는 상태
   rp= create_node();              //하나의 노드를 할당받아 
   rp->data= data;      rp->left= NULL;       rp->right= NULL;
}
else if( data == rp->data ) { //데이터가 존재 (5 != 900->data(즉, 11))
     printf(“Existing data %d\n”,data);
}
else if(data < rp->data )      //왼쪽 이동(5 < 900->data(즉, 11)) ->만족, 재귀함수를 부른다
     rp->left= insert(rp->left, data);
else                         //오른쪽 부트리로 이동
     rp->right= insert(rp->right, data); //rp에 return된 주소값 100으로 치환된다
return(rp);
}

왼쪽 이동에서 만족하여 재귀함수(insert)를 부를 때 -(호출)3번째
insert(*rp, data ) //rp=NULL이고, data=5
A: A:if(rp == NULL) {    //rp가 NULL이므로 새로 생긴 주소(100)에 왼쪽부트리는 NULL, 오른쪽 부트리 NULL 
    rp= create_node();    rp->data= data;      
    rp->left= NULL;          rp->right= NULL;

B:
C:
D:
E: return(rp) //재귀함수가 종료되고 돌아가면서, return한 주소값 100이 rp의 left에 치환된다

<data 9를 삽입하는 경우>
insert(*rp, data ) - (호출)1번, (돌아감)4번 //rp=900, data=9
A
B
C: if(data<rp->data) //9 < 900->data(11) 만족
    rp->left= insert(rp->left,data) //900번지의 rp에 리턴된 rp=100을 왼쪽에 치환
D
E: return(rp)


insert(*rp, data  ) - (호출)2번, (돌아감)3번 //rp=100, data=9
A
B
C   //9 < 100->data(5) 불만족
D: if(data>rp->data)
    rp->right= insert(rp->right,data) //rp=NULL, data=5 -> rp의 100번지의 오른쪽에 300을 치환
E: return(rp) //rp=100이 리턴

insert(*rp, data ) - (호출)3번 //rp=NULL, data=9
A:if(rp == NULL) {    //만족
   rp= create_node();  //rp=300    
   rp->data= data;     //data=9
   rp->left= NULL;       
   rp->right= NULL;
B
C
D
E: return(rp) //rp=300이 리턴