이진 트리 삽입 Binary Tree Insertion

이진 트리 삽입을 위해서는 먼저 탐색을 수행하는 것이 필요하다.

같은 key값을 같는 노드가 없음과 동시에, 탐색에 실패한 그 위치가 새로운 노드를

삽입하는 위치가 되기 때문이다.

 

 

 

 

아래는 자연어 버전의 이진 탐색 트리 삽입 알고리즘이다.

insert_node(T,z)

1.트리 T에서 z에 대한 탐색을 먼저 수행한다.
2.탐색이 실패하면 탐색이 끝난 지점에 노드 z를 삽입한다.

key 탐색이 성공하면 이미 key가 트리 안에 존재하는 것이고, 탐색 키가 중복되는 것이므로

삽입이 불가능하다. 하지만 key가 트리 안에 없다면 어디선가 탐색이 실패로 끝날 것이다. 그 위치가

key가 있어야 할 곳이 된다.

 

 

 

 

 

 

매개 변수 root는 이진 탐색 트리의 루트 노드를 가리킨다.

삽입 함수에서는 루트 노드 포인터가 변경되어야 하므로 루트 포인터의 포인터가 전달되었다.

key는 삽입할 탐색 키 값을 의미한다. <- 이거 자주 헷갈림!!!!

 

<c언어로 구현한 코드>

void insert_node(TreeNode **root, int key)
{
	TreeNode *p, *t; //p는 부모 노드, t는 현재 노드
    TreeNode *n; //n은 새로운 노드
    
    t=*root;
    p=NULL;
    
    //탐색을 먼저 수행
    while(t!=NULL){
    	if(key==t->key) return; //이미 존재
        p=t;
        if(key<p->key) t=p->left;
        else t=p->right;
   }
   //key가 트리 안에 없으므로 삽입 가능
   //트리 노드 구성
   n=(TreeNode*)malloc(sizeof(TreeNode));
   if(n==NULL)return;
   //데이터 복사
   n->key=key;
   n->left=n->right=NULL;
   //부모 노드와 연결
   if(p!=NULL)
   	if(key<p->key)
    	p->left=n;
    else p->right=n;
   else *root=n;
}