알고리즘 스터디

• 종만북 22장 이진 검색 트리 O
• 백준 13325 이진 트리 O
• 백준 2963 무한 이진 트리 탐색 ~
• 종만북 12장 최적화 문제 결정 문제로 바꿔 풀기 복습 ~
• 백준 17179 케이크 자르기 ~
• 백준 2343 기타 레슨 O
• 백준 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야 O
• 백준 1300 K번째 수 O

알고리즘 스터디

백준 13325 이진 트리

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-13325-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC

⚡백준 2963 무한 이진 트리 탐색

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-2963-%EB%AC%B4%ED%95%9C-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-%ED%83%90%EC%83%89

➖

⚡백준 17179 케이크 자르기

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-17179-%EC%BC%80%EC%9D%B4%ED%81%AC-%EC%9E%90%EB%A5%B4%EA%B8%B0

백준 2343 기타 레슨

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-2343-%EA%B8%B0%ED%83%80-%EB%A0%88%EC%8A%A8

백준 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-17951-%ED%9D%A9%EB%82%A0%EB%A6%AC%EB%8A%94-%EC%8B%9C%ED%97%98%EC%A7%80-%EC%86%8D%EC%97%90%EC%84%9C-%EB%82%B4-%ED%8F%89%EC%A0%90%EC%9D%B4-%EB%8A%90%EA%BB%B4%EC%A7%84%EA%B1%B0%EC%95%BC

⚡백준 1300 K번째 수

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-1300-K%EB%B2%88%EC%A7%B8-%EC%88%98

📌참고자료

• 이진 탐색 트리 - 탐색, 삽입, 삭제 연산
  https://yjg-lab.tistory.com/139

탐색 연산

• 주어진 키 값 == 루트 노드의 키 값: 탐색 성공
  주어진 키 값 < 루트 노드의 키 값: 왼쪽 서브트리를 탐색
  주어진 키 값 > 루트 노드의 키 값: 오른쪽 서브트리를 탐색

TreeNode  *search(TreeNode  *node,  int  key)
{
      if ( node == NULL )  return NULL;
      if ( key == node->key ) return node;
      else if ( key < node->key )
            return  search(node->left, key);  
      else
            return  search(node->right, key);
}

삽입 연산

• 이진 트리에 데이터를 삽입하기 위해 먼저 탐색 연산이 필요하다
• 삽입할 데이터 탐색 성공: 트리에 이미 존재하는 데이터. 삽입 불가능
  삽입할 데이터 탐색 실패: 탐색에 실패한 그 위치가 삽입할 위치가 된다

TreeNode * new_node(int item)  {
	TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
	temp->key = item;
	temp->left = temp->right = NULL;
	return temp;
}
TreeNode * insert_node(TreeNode * node, int key){
	//탐색 실패한 경우 삽입할 데이터를 가진 새로운 노드 추가
	if (node == NULL) return new_node(key);
	if (key < node->key)
		node->left = insert_node(node->left, key);
	else if (key > node->key)
		node->right = insert_node(node->right, key);
	//변경된 노드의 포인터 반환 
	return node;
}

삭제 연산

• 삭제할 노드가 단말 노드인 경우:
  단말 노드의 부모 노드를 찾아서 연결을 끊는다
• 삭제할 노드가 하나의 서브트리만 가지고 있는 경우:
  -> 해당 노드를 삭제하고 서브 트리를 부모 노드(삭제된 위치)에 붙여준다
• 삭제할 노드가 두 개의 서브트리를 가지고 있는 경우
  -> 삭제할 노드와 가장 근사한 값을 가진 노드(직후 노드 혹은 직전 노드)를 삭제할 노드 위치로 가져온다

TreeNode * min_value_node(TreeNode * node)
{
	TreeNode * current = node;
	// 최솟값을 가진 노드 = 맨 왼쪽 단말 노드
	while (current->left != NULL)
		current = current->left;
	return current;
}

// key 노드 삭제 후 루트 반환
TreeNode * delete_node(TreeNode * root, int key)  { 
	if (root == NULL) return root;
    	// 키가 루트보다 작으면 왼쪽 서브 트리에 있음
	if (key < root->key) 			
		root->left = delete_node(root->left, key);
    	// 키가 루트보다 크면 오른쪽 서브 트리에 있음
	else if (key > root->key) 		
		root->right = delete_node(root->right, key);
    	// 키가 루트와 같으면 이 노드를 삭제함
	else {				
    		//삭제할 노드가 오른쪽 서브트리만 가지고 있는 경우
            	//혹은 삭제할 노드가 단말 노드인 경우
		if (root->left == NULL) {	
			TreeNode * temp = root->right;
			free(root);
			return temp;
		}
    		//삭제할 노드가 왼쪽 서브트리만 가지고 있는 경우
            	//혹은 삭제할 노드가 단말 노드인 경우
		else if (root->right == NULL) {	
			TreeNode * temp = root->left;
			free(root);
			return temp;
		}
        	// 삭제할 노드가 두 개의 서브트리를 가지고 있는 경우
            	// 삭제할 노드의 우측 서브트리에서의 최솟값 = 삭제할 노드의 직후 노드
		TreeNode * temp = min_value_node(root->right); 		
		root->key = temp->key; 				
		root->right = delete_node(root->right, temp->key); 	
	}
	return root;
}