BST의 구현
기본 골조는 이진트리랑 비슷하지만 BST의 특성을 살려야 함
기본 골조 (일반적인 이진트리)
typedef struct Treenode {
int data; //int형 데이터 담음
struct Treenode* left; //node를 가리키는 포인터 선언
struct Treenode* right;
} TreeNode;
TreeNode* makeTreeNode(int data){
Node* newNode = (Node*)malloc(sizeof(TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
insertBST
BST의 특성 (작은건 왼쪽, 큰건 오른쪽)을 만족하며 노드를 삽입해야 함.
TreeNode* insertBST(TreeNode* root, int data){
if (root == NULL){
return makeTreeNode(data);
}
if (data < root->data){
root->left = insertBst(root->left, data);
}
else if (data > root->data){
root->right = insertBST(root->right, data);
}
return root; //삽입한 트리의 루트 노드를 반환함
}
searchBST
이것도 저번의 find와 마찬가지로 재귀적으로 찾는다
TreeNode* searchBST(TreeNode* root, int target){
if (root == NULL || root->data == target){
return root;
}
else if (target < root->data){
return searchBST(root->left, target);
}
else (target > root->data){
return searchBST(root->right, target);
}
}
deleteBST
BST에서 노드를 지우는 규칙에 따라 노드 삭제
어떤 서브트리의 루트 노드가 지워졌다면
왼쪽 서브트리의 가장 큰 노드를 루트로 올리거나
오른쪽 서브트리의 가장 작은 노드를 루트로 올리거나
TreeNode* deleteBST(TreeNode* root, int target){
if (root == NULL){
return root; //안 지우고 걍 반환
}
else if (target < root->data){
root->left = deleteBST(root->left, target);
}
else if(target > root->data){
root->right = deleteBST(root->right, target);
}
else{ //타겟을 찾음
// 왼쪽 자식이 없음: 오른쪽 자식을 root로
if (root->left == NULL) {
TreeNode* tmp = root->right;
free(root);
return tmp;
}
// 오른쪽 자식이 없음: 왼쪽 자식을 root로
else if (root->right == NULL) {
TreeNode* tmp = root->left;
free(root);
return tmp;
}
// 양쪽 다 자식이 있음: 오른쪽에서 가장 작은 놈으로 대체
TreeNode* tmp = root->right;
while (tmp->left != NULL) {
tmp = tmp->left;
}
root->data = tmp->data;
root->right = deleteBST(root->right, tmp->data);
}
return root;
}
728x90
반응형
'CS > 자료구조' 카테고리의 다른 글
[자료구조](15)[우선순위 큐 & 힙] (0) | 2025.05.14 |
---|---|
[자료구조](14)[이진트리의 구현 3] (0) | 2025.05.09 |
[자료구조](12)[이진트리의 구현 1] (0) | 2025.05.06 |
[자료구조](11)[트리의 순회] (0) | 2025.05.05 |
[자료구조](10)[이진탐색트리] (0) | 2025.04.23 |