[c++] 이진 탐색 트리의 삽입 및 삭제 알고리즘
이진 탐색 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식은 현재 노드보다 작은 값을, 오른쪽 자식은 현재 노드보다 큰 값을 가지고 있는 트리 구조입니다. 이진 탐색 트리에는 값의 삽입과 삭제가 빈번하게 일어나는데, 이를 위해 효율적인 알고리즘이 필요합니다.
이진 탐색 트리의 삽입 알고리즘
이진 탐색 트리에 새로운 값을 삽입하는 알고리즘은 다음과 같습니다.
// 새로운 값을 삽입하는 함수
Node* insert(Node* root, int value) {
if (root == nullptr) {
return new Node(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}
위의 알고리즘은 새로운 값을 삽입할 자리를 찾을 때까지 재귀적으로 트리를 탐색하며, 적절한 위치를 찾으면 새로운 값을 갖는 노드를 생성하여 연결합니다.
이진 탐색 트리의 삭제 알고리즘
이진 탐색 트리에서 값을 삭제하는 알고리즘은 다음과 같습니다.
// 값을 삭제하는 함수
Node* remove(Node* root, int value) {
if (root == nullptr) {
return root;
}
if (value < root->data) {
root->left = remove(root->left, value);
} else if (value > root->data) {
root->right = remove(root->right, value);
} else {
if (root->left == nullptr) {
Node* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
Node* temp = root->left;
delete root;
return temp;
}
Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = remove(root->right, temp->data);
}
return root;
}
위의 알고리즘은 삭제할 값이 존재하는 경우에는 해당 값을 포함하는 노드를 찾은 후, 그 노드를 삭제하고 적절한 자식 노드와 연결하여 트리를 재구성합니다.
결론
이진 탐색 트리의 삽입과 삭제 알고리즘은 해당 값을 탐색하고, 트리의 구조를 유지하며 값을 삽입하거나 삭제하는 데 있어서 효율적으로 동작합니다.
이진 탐색 트리는 자식 노드가 최대 두 개인 트리이며, 이를 활용하여 값의 삽입과 삭제를 빠르게 처리할 수 있습니다.
이진 탐색 트리의 삽입 및 삭제 알고리즘을 이해하면, 트리의 동적인 구조를 효율적으로 관리할 수 있습니다.
이진 탐색 트리(Binary Search Tree) - 위키피디아