โครงสร้างการค้นหาแบบไบนารี (BST) เป็นต้นไม้ชนิดพิเศษซึ่งเป็นไปตามกฎต่อไปนี้ −
-
ค่าโหนดลูกด้านซ้ายจะน้อยกว่าหมายเหตุหลักเสมอ
-
โหนดย่อยที่ถูกต้องมีค่ามากกว่าโหนดหลัก
-
โหนดทั้งหมดจะสร้างแผนผังการค้นหาแบบไบนารีแยกกัน
ตัวอย่างแผนผังการค้นหาแบบไบนารี (BST) −
โครงสร้างการค้นหาแบบไบนารีถูกสร้างขึ้นเพื่อลดความซับซ้อนของการดำเนินการ เช่น การค้นหา ค้นหาค่าต่ำสุดและสูงสุด
ลบ Operation binary search tree (BST)
การดำเนินการลบเป็นการทิ้งโหนดที่ระบุจากทรี ในกรณีที่ลบโหนด มีความเป็นไปได้สามประการ -
-
การลบโหนดลีฟออกจากทรี:การลบที่ง่ายที่สุดคือการลบโหนดลีฟออกจากทรีการค้นหาแบบไบนารี สำหรับการลบโหนดลีฟ เฉพาะลีฟเท่านั้นที่ได้รับผลกระทบ ตัวอย่าง
การลบโหนดลีฟ 7 ให้
-
การลบโหนดด้วยโหนดชายน์:สำหรับการลบนี้ คุณต้องแทนที่โหนดย่อยด้วยโหนดที่จะลบแล้วจึงลบทิ้ง ตัวอย่าง
กำลังลบ 2 ออกจาก BST
-
การลบโหนดที่มีโหนดย่อยสองโหนด:ในที่นี้โหนดที่จะลบมีโหนดย่อยสองโหนด ดังนั้น เราจะใช้ในรูปแบบลำดับของต้นไม้ ที่นี่ เราจะลบองค์ประกอบและเลือกเพื่อนบ้านที่ไม่เรียงลำดับสำหรับตำแหน่งของมัน และสร้างส่วนที่เหลือขึ้นใหม่ ตัวอย่าง
การลบ 5 จาก 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 inordertraversal(struct node *root){
if (root != NULL){
inordertraversal(root->left);
printf("%d ", root->key);
inordertraversal(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
node->right = insert(node->right, key);
return node;
}
struct node * minValueNode(struct node* node){
struct node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node* deleteNode(struct node* root, int key){
if (root == NULL) return root;
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;
}
int main(){
struct node *root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
printf("Inorder traversal of the given tree \n");
inordertraversal(root);
printf("\nDelete 20\n");
root = deleteNode(root, 20);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
printf("\nDelete 30\n");
root = deleteNode(root, 30);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
printf("\nDelete 50\n");
root = deleteNode(root, 50);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
return 0;
} ผลลัพธ์
Inorder traversal of the given tree 20 30 40 50 60 70 80 Delete 20 Inorder traversal of the modified tree 30 40 50 60 70 80 Delete 30 Inorder traversal of the modified tree 40 50 60 70 80 Delete 50 Inorder traversal of the modified tree 40 60 70 80
