이진 힙, 이진 탐색 트리

완전이진트리

부모의 우선 순위 > 자식의 우선 순위

종류

–최소힙(Minimum Heap) : 키 값이 작을수록 높은 우선순위

–최대힙(Maximum Heap) : 키 값이 클수록 높은 우선순위

 

이진 탐색 트리

왼쪽 서브 트리 <= 루트 노드 <= 오른쪽 서브트리 (중위 순회하면 오름차순으로 정렬)

탐색(찾기)

(1) 비교한 키가 같으면 탐색이 성공

(2) 주어진 키 값이 루트 노드의 키보다 작으면 탐색은 왼쪽 자식으로 다시 시작한다.

(3) 주어진 키 값이 루트 노드의 키보다 크면 탐색은오른쪽 자식으로 다시 시작한다.

//순환적인 탐색 함수
TreeNode  *search(TreeNode  *node,  int  key)
{
      if ( node == NULL )  return NULL;
      if ( key == node->key ) return node;     (1)
      else if ( key < node->key )
            return  search(node->left, key);     (2)
      else
            return  sear ch(node->right, key);  (3)
}

삽입

– 먼저 탐색하다가

– 탐색에 실패한 위치에 새로운 노드를 삽입

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 < t->key ) t = t->left;
	    else t = t->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;
}

 

 

 

 

삭제

1. 삭제하려는 노드가 단말 노드 -> 부모노드를 찾아서 연결 끊기

// 1. 단말노드인 경우
if( (t->left==NULL) && (t->right==NULL) ){ 
   if( p != NULL ){
      // 부모노드의 자식필드를 NULL로 만든다.
      if( p->left == t )  
         p->left = NULL;
      else p->right = NULL;
   }
   else  // 만약 부모노드가 NULL이면 삭제되는 노드가 루트
      *root = NULL;
}

2. 삭제하려는 노드가 자식 하나만 가짐 -> 자식만 부모에 붙여줌 

// 2. 하나의 자식만 가지는 경우
else if((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 // 만약 부모노드가 NULL이면 삭제되는 노드가 루트
      *root = child;
}

3. 삭제하려는 노드가 자식 둘 다 가짐 -> 두 자식 중 가장 비슷한 자식을 삭제할 위치로 가져옴

// 3. 두개의 자식을 가지는 경우
else{
   // 오른쪽 서브트리에서 후계자를 찾는다.
   succ_p = t;
   succ = t->right;
   // 후계자를 찾아서 계속 왼쪽으로 이동한다.
   while(succ->left != NULL){
      succ_p = succ;
      succ = succ->left;
   }
   // 후속자의 부모와 자식을 연결 
   if( succ_p->left == succ )
      succ_p->left = succ->right;
   else 
      succ_p->right = succ->right;
   // 후속자가 가진 키값을 현재 노드에 복사
   t->key = succ->key;
   // 원래의 후속자 삭제
   t = succ;
}

// 삭제 함수
void delete_node(TreeNode **root, int key)
{
TreeNode *p, *child, *succ, *succ_p, *t;
// key를 갖는 노드 t를 탐색, p는 t의 부모노드
p = NULL;
t = *root;

// key를 갖는 노드 t를 탐색한다.
while( t != NULL && t->key != key ){
   p = t;
   t = ( key < t->key ) ? t->left : t->right;
}

// 탐색이 종료된 시점에 t가 NULL이면 트리안에 key가 없음
if( t == NULL ) { 	// 탐색트리에 없는 키
   printf("key is not in the tree");
   return;
}

// 1. 단말노드인 경우
if( (t->left==NULL) && (t->right==NULL) ){ 
   if( p != NULL ){
      // 부모노드의 자식필드를 NULL로 만든다.
      if( p->left == t )	 
         p->left = NULL;
      else p->right = NULL;
   }
   else  // 만약 부모노드가 NULL이면 삭제되는 노드가 루트
      *root = NULL;
}

// 2. 하나의 자식만 가지는 경우
else if((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 // 만약 부모노드가 NULL이면 삭제되는 노드가 루트
      *root = child;
}
// 3. 두개의 자식을 가지는 경우
else{		
   // 오른쪽 서브트리에서 후계자를 찾는다.
   succ_p = t;
   succ = t->right;
   // 후계자를 찾아서 계속 왼쪽으로 이동한다.
   while(succ->left != NULL){
      succ_p = succ;
      succ = succ->left;
   }
   // 후속자의 부모와 자식을 연결 
   if( succ_p->left == succ )
      succ_p->left = succ->right;
   else 
      succ_p->right = succ->right;
   // 후속자가 가진 키값을 현재 노드에 복사
   t->key = succ->key;
   // 원래의 후속자 삭제
   t = succ;
}
free(t);
}

 

최선의 경우 (높이에 비례)

– 균형 트리,  h = log N

최악의 경우

– 경사이진트리, h = N