บทความ: การจัดการข้อมูลแบบไดนามิคใน C++ ผ่าน Binary Search Tree
ยุคปัจจุบันนี้ หนึ่งในสกิลที่ไม่สามารถมองข้ามได้เลยสำหรับการเป็นนักพัฒนาซอฟต์แวร์คือ การมีความสามารถในการจัดการข้อมูล (Data Management skills) ในบทความนี้ เราจะมาสำรวจเทคนิคการจัดการข้อมูลแบบไดนามิคในภาษา C++ ผ่านโครงสร้างข้อมูลที่เรียกว่า Binary Search Tree (BST) โดยจะการพร้อมด้วยตัวอย่างโค้ดสำหรับการ insert, insert at front, find และ delete พร้อมทั้งประเมินข้อดีข้อเสียเพื่อให้ผู้อ่านได้เข้าใจอย่างลึกซึ้ง
Binary Search Tree (BST) เป็นโครงสร้างข้อมูลที่เป็นรูปแบบพิเศษของ Binary Tree โดยมีลักษณะเฉพาะตัวคือภายในแต่ละโหนด (node) จะประกอบด้วยค่าข้อมูล (data) พร้อมด้วยการเชื่อมโยงไปยังโหนดย่อย (sub-node) สองโหนด คือ left child และ right child โดยมีข้อกำหนดว่าค่าข้อมูลใน left child ต้องมีค่าน้อยกว่าโหนดปัจจุบัน และค่าข้อมูลใน right child ต้องมีค่ามากกว่าโหนดปัจจุบัน
ข้อดีของ BST ก็คือความสามารถในการค้นหา, แทรก, และลบข้อมูลด้วยความเร็วเฉลี่ยในทางทฤษฎีคือ O(log n) ซึ่งเกิดจากการทำซ้ำของการแบ่งข้อมูลลงครึ่งเรื่อยๆ จนกระทั่งพบข้อมูลหรือจนกว่าการแทรกหรือลบสมบูรณ์ ส่วนข้อเสียก็คือหากการเพิ่มข้อมูลไม่สมดุล (เช่น การเพิ่มข้อมูลที่เรียงลำดับไปเรื่อย ๆ) BST จะมีลักษณะเหมือน linked-list ธรรมดาทำให้ประสิทธิภาพการทำงานลดลงเป็น O(n)
ต่อไปนี้คือตัวอย่างการใช้งาน BST ในการจัดการข้อมูลหลักๆ:
1. Insert:
ในการแทรกข้อมูลใหม่ จะต้องทำการเดินทางผ่านต้นไม้โดยเริ่มจากราก (root) และเปรียบเทียบค่าข้อมูลเพื่อจะไปทางซ้ายหรือขวาจนถึงตำแหน่งที่เหมาะสมที่จะแทรกโหนดใหม่
struct Node {
int key;
Node *left, *right;
};
Node* insert(Node* node, int key) {
if (node == nullptr) return new Node(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
2. Insert At Front:
Insert at front เป็นการแทรกข้อมูลที่ตำแหน่งแรกของเส้นทางการค้นหาโดยไม่คำนึงถึงลำดับใน BST ซึ่งนับเป็นการใช้งานที่ไม่เหมาะสมกับ BST เนื่องจากสามารถทำให้โครงสร้างของต้นไม้เสียหายได้
3. Find:
การค้นหามีหลักการเดียวกันกับการแทรก คือเริ่มจากราก และเคลื่อนไปตามลำดับตามกฎของ BST
Node* find(Node* root, int key) {
if (root == nullptr || root->key == key) return root;
if (key < root->key)
return find(root->left, key);
else
return find(root->right, key);
}
4. Delete:
การลบโหนดใน BST นั้นมีความซับซ้อนกว่าการแทรกหรือค้นหา เนื่องจากรักษาลักษณะพิเศษของ BST โดยพวกเราต้องหาโหนดที่จะลบ แล้วปรับโครงสร้างของต้นไม้ เพื่อให้ยังคงเป็น BST เช่นการหารากทดแทน (inorder successor)
Node* deleteNode(Node* root, int key) {
// Base Case: If the tree is empty
if (root == nullptr) return root;
// Otherwise, recur down the tree
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// Node with only one child or no child
if (root->left == nullptr) {
Node *temp = root->right;
delete root;
return temp;
}
else if (root->right == nullptr) {
Node *temp = root->left;
delete root;
return temp;
}
// Node with two children: Get the inorder successor
Node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
Node * minValueNode(Node* node) {
Node* current = node;
// Loop down to find the leftmost leaf
while (current && current->left != nullptr)
current = current->left;
return current;
}
BST นับเป็นเครื่องมือที่ทรงพลังในการจัดการข้อมูลที่เปลี่ยนแปลงได้อย่างไดนามิค แล้วจะเห็นได้ว่าถ้าจำเป็นต้องจัดการข้อมูลจำนวนมาก BST สามารถช่วยในการปรับปรุงการทำงานในหลาย ๆ ด้าน เช่น ในเรื่องของการซื้อขายหลักทรัพย์ การควบคุมฐานข้อมูล หรือการเข้าถึงข้อมูลที่เรียงลำดับ อย่างไรก็ตาม เพื่อเพิ่มประสิทธิภาพ เราควรพิจารณาการใช้งานเพิ่มเติมเช่นการสร้าง Self-balanced BST เช่น AVL tree หรือ Red-Black tree ที่สามารถช่วยให้ต้นไม้มีความสมดุลและการทำงานเป็น O(log n) อย่างสม่ำเสมอ
เพื่อประสบการณ์การเรียนรู้ที่ดียิ่งขึ้นและมีโครงสร้างที่มั่นคงในการพัฒนาโปรแกรม ศึกษากับ EPT เรามุ่งมั่นที่จะอุทิศความรู้และทักษะในการเขียนโปรแกรมอย่างมืออาชีพให้กับคุณ ลงทะเบียนเรียนกับเราวันนี้เพื่อทำความเข้าใจเกี่ยวกับการจัดการข้อมูลและ BST บนพื้นฐานของการจัดการข้อมูลที่เป็นระบบและรองรับการขยายตัวได้อย่างไร้ขีดจำกัด!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM