트리(이진 탐색 트리) 삽입연산,삭제연산

이진탐색트리는 탐색을 효율적으로 하기 위해 만든 이진 트리 기반의 탐색을 위한 자료구조입니다.

이진탐색트리를 알기 위해 정의를 살펴봅시다.

---

이진 탐색 트리의 정의

• 모든 원소의 키는 유일한 키를 가진다.
• 왼쪽 서브 트리 키들은 루트 키보다 작다.
• 오른쪽 서브 트리 키들은 루트의 키보다 크다.
• 왼쪽과 오른쪽 서브트리도 이진 탐색트리이다.

위에 있는 정의들을 만족시키며 이진 탐색 트리는 완성이 됩니다.

 

아래에 있는 영상은 어떻게 하면 이진탐색트리를 좀더 쉽게 정의를 지키며 구현할 수 있을까 해서 가져온 영상입니다.

https://www.youtube.com/watch?v=9ZZbA2iPjtM

---

이진탐색트리의 삽입연산

 

 이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요하다. 이유는 이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 하기 때문이고 또한 탐색에 실패한 위치가 바로 새로운 노드를 삽입해야하는 위치가 되기 때문이다.

TreeNode * insert_node(TreeNode* node, int key)
{
	if(node==NULL) return new_node(key); //새로운 노드 반환
    if(key>node->key) node->right = insert_node(node->right,key);
    else if(key < node->key) node->left = insert_node(node->left,key);
    
    return node;
}

이진 탐색트리의 삭제 연산

삭제 할때도 역시 삽입 할때처럼 노드를 탐색해야하고 탐색을 하여 노드를 찾았으면 3가지 경우를 고려해야한다.

1. 삭제하려는 노드가 단말노드인 경우
2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브트리 중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두개의 서브트리 모두 가지고 있는 경우

첫번째 와 두번째 경우 삭제할 노드는 삭제하고 서브트리는 삭제할 노드의 부모노드에 붙여주면 된다.

세번째 경우는 왼쪽 서브트리나 오른쪽 서브트리중 아무 노드나 붙여넣으면 이진 탐색트리의 정의에 맞지가 않다.

이진탐색트리는 위에 유튜브에서도 알리다 싶이 배열의 정렬을 토대로 만든 트리이다. 따라서 내가 삭제하고 싶은 노드에 가장 가까운 앞쪽 또는 뒷쪽이 그 자리를 차지하게 된다 그 말은 즉슨 내가 지울려는 노드와 가장 가까운 값의 노드를 그 자리에 갖다 놓으면 된다는 것이다. 가까운 값의 노드는 삭제하려는 노드의 왼쪽 서브트리에서 제일 큰 값 이거나

오른쪽 서브트리에서 제일 작은 값이다. 

우리는 오른쪽 서브트리에서 제일 작은 값을 삭제하는 노드의 대체품으로 넣을 것이다.

 

TreeNode * delete_node(TreeNode *node , int key)
{
	if(root==NULL) return root;
    if(key>root->key) root->right = delete_node(root->right,key);
    else if(key<root->key) root->left = delete_node(root->left,key);
    else{
    		//첫 번째나 두 번째 경우
            if(root->left==NULL) {
			TreeNode *temp = root->right;
            delete(root)
            return temp;
            }
            else if(root->right==NULL){
            TreeNode *temp = root->left;
            delete(root);
            return temp;
            }
            //세 번째 경우
            //오른쪽 서브트리에서 가장 작은 노드를 가져오고
            TreeNode *temp = min_value_node(root->right);
            //작은 노드를 복사하고
            root->key = temp->key;
            //그 작은 노드를 삭제한다.
            root->right = delete_node(root->right,temp->key);
        }
}

TreeNode * min_value_node(TreeNode *node)
{
	TreeNode * current = node;
    while(current->left!=NULL)current = current->left;
    return current;
 }

---

이진 탐색트리의 시간 복잡도

검색/삽입 시간 복잡도 

높이가 h인 경우의 시간복잡도는 o(h) 입니다. 하지만 시간복잡도는 원소의 개수로 표기할 때,

좋은 표기법이므로 원소의 개수가 n이면 h = log₂N (노드의 개수 n = 2^h-1이므로 2^h = n+1 )

따라서 시간 복잡도는 O(log₂N) 이다.

 

삭제 시간 복잡도 

삭제 노드를 탐색 O(H)

대체 노드를 찾기 위한 서브 트리를 탐색 O(H)

참조값 변경 O(1)

총 O(2H+1) = O(H) = O(log2N) 이다.

---

이진 탐색 트리의 통합본

#include <iostream>
using namespace std;


struct TreeNode {
	int key;
	TreeNode*left;
	TreeNode * right;
};
TreeNode * new_node(int key) {
	TreeNode * temp = new TreeNode;
	temp->key = key;
	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* search_node(TreeNode* node, int key) {
	if (node == NULL)return node;
	if (key < node->key) node = search_node(node->left, key);
	else if (key > node->key)node = search_node(node->right, key);

	return node;
}

TreeNode* min_value_node(TreeNode *node)
{
	TreeNode * current = node;
	while (current->left != NULL) {
		current = current->left;
	}
	return current;

}

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

	}
		else if (node->right == NULL)
		{
			TreeNode*temp = node->left;
			delete node;
			return temp;

		}
		else {
			TreeNode *temp = min_value_node(node->right);
			node->key = temp->key;
			node->right = delete_node(node->right, temp->key);
		}
	}

	return node;
}


void inorder(TreeNode *node)
{
	
	if(node) {
		inorder(node->left);
		cout << node->key << " ";
		inorder(node->right);
	}
}
int main() {
	TreeNode *node = NULL;

	node = insert_node(node, 13);
	node = insert_node(node, 8);
	node = insert_node(node, 15);
	node = insert_node(node, 14);
	node = insert_node(node, 19);
	node = insert_node(node, 7);
	node = insert_node(node, 10);
	node = insert_node(node, 9);

	if (search_node(node, 9)) cout << "찾는 노드가 있음 " << endl;
	else cout << "찾는 노드가 없음" << endl;

	node = delete_node(node, 15);


	inorder(node);

}