โครงสร้างข้อมูล - โครงสร้างการค้นหาแบบไบนารี
Binary Search Tree (BST) คือต้นไม้ที่โหนดทั้งหมดเป็นไปตามคุณสมบัติที่กล่าวถึงด้านล่าง -
ค่าของคีย์ของแผนผังย่อยด้านซ้ายมีค่าน้อยกว่าค่าของคีย์ของโหนดหลัก (รูท)
ค่าของคีย์ของแผนผังย่อยด้านขวามากกว่าหรือเท่ากับค่าของคีย์ของโหนดหลัก (รูท)
ดังนั้น BST จึงแบ่งต้นไม้ย่อยทั้งหมดออกเป็นสองส่วน แผนผังย่อยด้านซ้ายและแผนผังย่อยด้านขวาและสามารถกำหนดเป็น -
left_subtree (keys) < node (key) ≤ right_subtree (keys)
การเป็นตัวแทน
BST คือชุดของโหนดที่จัดเรียงในลักษณะที่พวกมันรักษาคุณสมบัติ BST แต่ละโหนดมีคีย์และค่าที่เกี่ยวข้อง ขณะค้นหาคีย์ที่ต้องการจะถูกเปรียบเทียบกับคีย์ใน BST และหากพบค่าที่เกี่ยวข้องจะถูกดึงออกมา
ต่อไปนี้เป็นการแสดงภาพของ BST -
เราสังเกตว่าคีย์โหนดรูท (27) มีคีย์ที่มีค่าน้อยกว่าทั้งหมดบนแผนผังย่อยด้านซ้ายและคีย์ที่มีมูลค่าสูงกว่าบนแผนผังย่อยด้านขวา
การทำงานขั้นพื้นฐาน
ต่อไปนี้คือการทำงานพื้นฐานของต้นไม้ -
Search - ค้นหาองค์ประกอบในต้นไม้
Insert - แทรกองค์ประกอบในต้นไม้
Pre-order Traversal - สำรวจต้นไม้ในลักษณะสั่งจองล่วงหน้า
In-order Traversal - เดินลัดเลาะไปตามต้นไม้ตามลำดับ
Post-order Traversal - เดินลัดเลาะไปตามต้นไม้ในลักษณะโพสต์ออร์เดอร์
โหนด
กำหนดโหนดที่มีข้อมูลอ้างอิงโหนดลูกด้านซ้ายและขวา
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
การดำเนินการค้นหา
เมื่อใดก็ตามที่ต้องการค้นหาองค์ประกอบให้เริ่มค้นหาจากโหนดรูท จากนั้นหากข้อมูลน้อยกว่าค่าคีย์ให้ค้นหาองค์ประกอบในทรีย่อยด้านซ้าย มิฉะนั้นให้ค้นหาองค์ประกอบในทรีย่อยด้านขวา ทำตามอัลกอริทึมเดียวกันสำหรับแต่ละโหนด
อัลกอริทึม
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL) {
printf("%d ",current->data);
//go to left tree
if(current->data > data){
current = current->leftChild;
} //else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
}
}
return current;
}
แทรกการทำงาน
เมื่อใดก็ตามที่จะแทรกองค์ประกอบอันดับแรกให้หาตำแหน่งที่เหมาะสม เริ่มค้นหาจากโหนดรูทจากนั้นหากข้อมูลมีค่าน้อยกว่าค่าคีย์ให้ค้นหาตำแหน่งว่างในทรีย่อยด้านซ้ายและแทรกข้อมูล มิฉะนั้นให้ค้นหาตำแหน่งว่างในทรีย่อยด้านขวาและแทรกข้อมูล
อัลกอริทึม
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
} //go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}