이진 검색 트리(BST) 다음 규칙을 따르는 특별한 유형의 트리입니다 -
- 왼쪽 자식 노드의 값은 항상 부모 노트보다 작습니다.
- 오른쪽 자식 노드는 부모 노드보다 더 큰 값을 가집니다.
- 모든 노드는 개별적으로 이진 검색 트리를 형성합니다.
이진 검색 트리(BST)의 예 -
검색, 최소값 및 최대값 찾기와 같은 작업의 복잡성을 줄이기 위해 이진 검색 트리가 생성됩니다.
BST에서 검색 작업
이진 검색 트리에서 검색 수행,
트리에서 키를 찾아야 합니다. 이를 위해 키를 트리의 루트 노드와 비교합니다.
키가 루트 노드와 같으면 키를 찾습니다.
키 값이 루트 노드보다 크면 오른쪽 하위 트리를 가져와서 키를 검색합니다.
키 값이 루트 노드보다 작으면 왼쪽 하위 트리를 가져와서 키를 검색합니다.
예시
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
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);
}
struct node* insert(struct node* node, int 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;
}
int main(){
struct node *root = NULL;
root = insert(root, 23);
insert(root, 15);
insert(root, 12);
insert(root, 17);
insert(root, 32);
insert(root, 29);
insert(root, 45);
printf("The tree is :\n");
traversetree(root);
printf("\nSearching for 12 in this tree ");
if(search(root , 12))
printf("\nelement found");
else
printf("\nelement not found");
return 0;
} 출력
The tree is : 12 15 17 23 29 32 45 Searching for 12 in this tree element found
BST에서 삽입 작업
BST에서 삽입 작업은 삽입을 위해 트리의 리프 노드에서 발생하며 노드와 루트 노드의 비교를 시작하고 노드의 올바른 위치를 찾은 다음 배치합니다. 다음 예를 보면 더 명확해집니다.
이 BST에 12를 삽입합니다.
12를 루트 노드 12> 5와 비교하고 오른쪽 하위 트리에 속합니다.
12를 오른쪽 자식 노드 12> 8과 비교하면 오른쪽 자식 노드의 오른쪽에 속합니다.
오른쪽 하위 트리 12>10의 오른쪽 하위 하위 항목과 12를 비교합니다. 위치는 이 노드의 오른쪽입니다.
새로 형성된 나무는 다음과 같습니다.
예시
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
struct node* insert(struct node* node, int 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;
}
int main(){
struct node *root = NULL;
root = insert(root, 23);
insert(root, 15);
insert(root, 12);
insert(root, 17);
insert(root, 32);
insert(root, 29);
printf("The tree is :\n");
traversetree(root);
printf("\nInseting 45 to the tree\n");
insert(root, 45);
printf("Tree after insertion is :\n");
traversetree(root);
return 0;
} 출력
The tree is : 12 15 17 23 29 32 Inserting 45 to the tree Tree after insertion is : 12 15 17 23 29 32 45