การจัดการข้อมูลเป็นหัวใจสำคัญทางด้านคอมพิวเตอร์วิทยาการ ไม่ว่าจะเป็นการเก็บรักษา การค้นหา หรือการปรับปรุงข้อมูล สำหรับโปรแกรมเมอร์ที่ใช้ภาษา C++ หนึ่งในโครงสร้างข้อมูลที่มีความสำคัญและทรงพลังคือ Tree โดยเฉพาะการใช้งาน Binary Tree และ Binary Search Tree (BST) ที่ช่วยให้การจัดการข้อมูลเป็นไปได้สะดวกและรวดเร็วยิ่งขึ้น เรามาเริ่มกันที่ข้อมูลพื้นฐานและวิธีการใช้งานพร้อมตัวอย่างโค้ดเป็นประจำการครับ
ก่อนที่เราจะไปดูโค้ดการทำงานของ Tree ใน C++ ลองทบทวนกันสักนิดว่า Tree คือโครงสร้างข้อมูลแบบหนึ่งที่ประกอบไปด้วย node ที่เชื่อมต่อกันเป็นลักษณะแบบไม่เชิงเส้น (non-linear) โดยแต่ละ node จะมีตัวชี้ (pointer) ไปยัง node ที่เป็นลูก (children) และมีเพียงหนึ่ง node เท่านั้นที่จะเป็น root node
เรามาเริ่มกับการ insertion ของข้อมูลเข้าสู่ BST กันครับ:
struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : value(x), left(NULL), right(NULL) {}
};
TreeNode* insert(TreeNode* root, int value) {
if (root == NULL) {
return new TreeNode(value);
}
if (value < root->value) {
root->left = insert(root->left, value);
} else if (value > root->value) {
root->right = insert(root->right, value);
}
return root;
}
จากโค้ดดังกล่าวเราสร้างฟังก์ชันที่ชื่อว่า `insert` เพื่อนำเข้าข้อมูลใหม่เข้าไปใน tree ของเรา ข้อมูลใหม่จะถูกเพิ่มเข้าไปในตำแหน่งที่เหมาะสมเพื่อรักษาคุณสมบัติของ BST คือ ข้อมูลทุกตัวทางซ้ายจะต้องน้อยกว่า root และข้อมูลทุกตัวทางขวาจะต้องมากกว่า root
ต่อไปเป็นการค้นหาโดยใช้ฟังก์ชัน `find`:
TreeNode* find(TreeNode* root, int value) {
if (root == NULL || root->value == value) {
return root;
}
if (value < root->value) {
return find(root->left, value);
}
return find(root->right, value);
}
การค้นหาบน BST นั้นมีประสิทธิภาพสูง เพราะเราสามารถข้ามกึ่งหนึ่งของ tree ไปตามเงื่อนไขได้ทันที ทำให้เวลาการค้นหาเป็นเวลาโดยเฉลี่ย O(log n)
เมื่อเราสามารถเพิ่มและค้นหาข้อมูลได้แล้ว การลบข้อมูลก็คือการเรียงโครงสร้าง node ใหม่เพื่อรักษาคุณสมบัติของ BST ต่อไปคือตัวอย่างโค้ดของฟังก์ชัน `delete`จาก BST:
TreeNode* deleteNode(TreeNode* root, int value) {
if (root == NULL) return root;
if (value < root->value) {
// go left
root->left = deleteNode(root->left, value);
} else if (value > root->value) {
// go right
root->right = deleteNode(root->right, value);
} else {
// node with only one child or no child
if (root->left == NULL) {
TreeNode *temp = root->right;
delete root;
return temp;
} else if (root->right == NULL) {
TreeNode *temp = root->left;
delete root;
return temp;
}
// node with two children: Get the inorder successor
TreeNode* temp = minValueNode(root->right);
root->value = temp->value;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->value);
}
return root;
}
การลบข้อมูลจำเป็นต้องไล่ตาม node ที่ต้องการลบ แล้วปรับโครงสร้าง tree เพื่อไม่ให้สูญเสียคุณสมบัติของ BST ซึ่งอาจจะทำให้เกิดกระบวนการค้นหาที่ไม่ได้เป็น O(log n) เสมอไปในกรณีที่ต้องการลบ node ที่มีลูกมากกว่าหนึ่งตัว
ข้อดีและข้อเสียของการใช้ Tree ในการจัดการข้อมูลไดนามิคใน C++ คือ:
ข้อดี:
- การค้นหาข้อมูลที่มีประสิทธิภาพในบางกรณีมีค่าเป็น O(log n)
- ช่วยให้ข้อมูลมีลำดับและสามารถจัดเรียงได้ง่าย
- มีความยืดหยุ่นในการจัดเก็บข้อมูลที่มีขนาดเปลี่ยนแปลงได้
ข้อเสีย:
- ไม่มีประสิทธิภาพสูงสุดเมื่อ Tree ไม่สมดุล (unbalanced)
- ซับซ้อนในการเขียนโค้ดและการจัดการ memory เมื่อเทียบกับโครงสร้างข้อมูลอื่นๆ
- การลบข้อมูลอาจทำให้โครงสร้างของ Tree เสียไป ต้องการการจัดเรียงใหม่เพื่อรักษาความสมดุล
จากที่ได้กล่าวมาการใช้งาน Tree ในการจัดการข้อมูลแบบไดนามิคใน C++ นั้นมีทั้งส่วนที่น่าสนใจและควรพิจารณาให้ดีก่อนสร้างโครงสร้างข้อมูลขึ้นมา สำหรับผู้ที่ต้องการพัฒนาทักษะการเขียนโปรแกรมและการใช้งานโครงสร้างข้อมูลต่างๆ อย่างล้ำลึกควรเริ่มศึกษาให้เข้าใจอย่างถ่องแท้ที่ EPT (Expert-Programming-Tutor) ที่เรามีหลักสูตรและฝึกฝนทักษะการเขียนโปรแกรมให้เหมาะสมกับทุกระดับการเรียนรู้ครับ!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM