이전 시간에 트리에 대해 공부했습니다. (참고 : 자료구조 트리)
이번 시간에는 이진 탐색 트리에 대해 공부해보겠습니다.
♪ 이진 탐색 트리(Binary Search Tree) : 노드기반(Node-Based) 이진 트리 자료구조입니다.
♪ 특징(Properties) :
☞ 좌측 하위 트리(Left Subtree)의 노드들은 상위 노드보다 작거나 같은 값입니다.
☞ 우측 하위 트리(Right Subtree)의 노드들은 상위 노드보다 큰 값입니다.
☞ 좌측 및 우측 하위트리 역시 이진 탐색 트리입니다. (하위트리의 하위트리들도 모두 위 특징에 해당합니다)
♪ 탐색(Search) :
☞ 탐색의 시작은 루트 노드(Root Node)에서 시작합니다. 만약 탐색하려는 값이 루트 노드의 값이라면 루트 노드의 값을 반환합니다.
☞ 만약 탐색하려는 값이 루트 노드의 값보다 작다면 좌측 하위 트리로 이동해서 탐색을 반복합니다.
☞ 만약 탐색하려는 값이 루트 노드의 값보다 크다면 우측 하위 트리로 이동해서 탐색을 반복합니다.
# 탐색 - 소스코드(C/C++)
struct node* search(struct node* root, int key) // 키 값 : 탐색하려는 값
{
if (root == NULL || root->key == key) // 루트 노드가 없거나 루트 노드의 값이 키 값인 경우
return root; // 루트 노드 반환
if (root->key < key) // 키 값이 루트 노드의 값보다 크다면
return search(root->right, key); // 우측 하위 트리 탐색
// 키 값이 더 작다면
return search(root->left, key); // 좌측 하위 트리 탐색
}
♪ 삽입(Insertion) : 새로운 노드는 항상 잎(Leaf) 노드에서 발생합니다.
☞ 루트 노드에서 탐색을 시작합니다. 만약 루트 노드가 없다면 노드를 삽입합니다.
☞ 잎(Leaf) 노드를 만날 때 까지 탐색을 시작합니다.
☞ 잎(Leaf) 노드를 만났다면 새로운 노드를 삽입합니다.(새 노드 값이 작다면 좌측, 크다면 우측)
# 삽입 - 소스코드(C/C++)
struct node *newNode(int item) // 새로운 노드 생성 함수
{
struct node *temp = (struct node *)malloc(sizeof(struct node)); // 새로운 노드를 동적할당
temp->key = item; // 키 값을 설정
temp->left = temp->right = NULL; // 좌측 및 우측 노드 null로 초기화
return temp;
}
struct node* insert(struct node* node, int key) // 삽입 함수; node는 root노드, key는 삽입하려는 값
{
if (node == NULL) return newNode(key); // 루트 노드가 없다면 바로 삽입
if (key < node->key) // 새 노드가 루트노드 값보다 작다면
node->left = insert(node->left, key); // 좌측 서브트리로 이동해서 반복
else if (key > node->key) // 새 노드가 루트노드 값보다 크다면
node->right = insert(node->right, key); // 우측 서브트리로 이동해서 반복
return node;
}
♪ 삭제(Delete) : 설명은 소스코드 주석으로 대체합니다.
# 삭제 - 소스코드(C/C++)
struct node * minValueNode(struct node* node) // 가장 작은 노드 반환 함수
{
struct node* current = node; // 루트 노드 복사
while (current->left != NULL) // 좌측 서브트리가 없을 때 까지 반복
current = current->left;
return current;
}
struct node* deleteNode(struct node* root, int key) // 삭제 함수
{
if (root == NULL) return root; // 루트 노드 null이라면 루트 노드 반환
if (key < root->key) // 삭제하려는 노드의 값이 루트노드의 값보다 작다면
root->left = deleteNode(root->left, key); // 좌측 서브트리로 이동해서 반복
else if (key > root->key) // 크다면
root->right = deleteNode(root->right, key); // 우측 서브트리로 이동해서 반복
else // 삭제하려는 노드가 루트 노드
{
if (root->left == NULL) // 좌측 서브트리가 없는 경우
{
struct node *temp = root->right; // 우측 서브트리 복사
free(root); // 루트 노드 삭제
return temp; // 우측 서브트리 반환
}
else if (root->right == NULL) // 우측 서브트리가 없는 경우
{
struct node *temp = root->left; // 좌측 서브트리 복사
free(root); // 루트 노드 삭제
return temp; // 좌측 서브트리 반환
}
// 좌, 우측 서브트리 모두 있을 경우
struct node* temp = minValueNode(root->right); // 우측 서브트리 중 가장 작은 값 복사
root->key = temp->key; // 복사 한 값을 루트 노드에 복사
root->right = deleteNode(root->right, temp->key); // 루트의 우측 서브트리 이동해서 반복
}
return root;
}
정보가 유익하셨다면 아래 공감버튼 눌러주시면 감사하겠습니다.
질문사항은 댓글로 달아주시면 성의껏 답변해드리겠습니다.
