การจัดการข้อมูลเป็นหนึ่งในส่วนสำคัญของการพัฒนาโปรแกรม เพราะข้อมูลถือเป็นหัวใจของการดำเนินการต่างๆ และหากการจัดการดี จะทำให้โปรแกรมทำงานได้รวดเร็ว มีประสิทธิภาพ และเชื่อถือได้ ในภาษาโปรแกรม C ที่ถือเป็นภาษาที่มีประสิทธิภาพสูง เรื่องของการจัดการข้อมูลแบบไดนามิคจึงเป็นที่สนใจมาก หนึ่งในโครงสร้างข้อมูลที่พัฒนามาเพื่อจัดการข้อมูลที่เปลี่ยนแปลงไปได้ตลอดเวลาคือ Red-Black Tree
Red-Black Tree เป็นโครงสร้างข้อมูลแบบยืดหยุ่นที่เป็นประเภทของ binary search tree ที่มีคุณสมบัติพิเศษเพิ่มขึ้นมา เพื่อรักษาความสมดุลของต้นไม้แม้หลังจากการเพิ่มหรือลบข้อมูล ทำให้ประสิทธิภาพสำหรับการค้นหา การแทรก(insert) และการลบ(delete) มีค่าเฉลี่ยเป็น O(log n)
คุณสมบัติของ Red-Black Tree
- คุณสมบัติที่ 1: แต่ละโหนดจะเป็นสีแดงหรือสีดำ
- คุณสมบัติที่ 2: โหนดราก(root) เป็นโหนดสีดำ
- คุณสมบัติที่ 3: ทุกโหนดสีแดงต้องมีโหนดลูกสองโหนดและเป็นโหนดสีดำ
- คุณสมบัติที่ 4: ทุกโหนดที่มีข้อมูลจะมี path-black-count เท่ากัน นั่นคือ ทุก path จากโหนดหนึ่งไปยัง leaf-nodes ย่อมมีจำนวนโหนดสีดำเท่ากัน
- คุณสมบัติที่ 5: โหนดสีดำสามารถเป็นลูกของโหนดสีดำได้ แต่โหนดสีแดงไม่สามารถเป็นลูกของโหนดสีแดงได้ (ห้ามมีโหนดสีแดงต่อเนื่องกันเกินหนึ่งโหนด)
เรามักจะใช้การจัดการข้อมูลแบบไดนามิคผ่าน Red-Black Tree เมื่อต้องการประสิทธิภาพการค้นหาที่รวดเร็วและคงที่ไม่ขึ้นกับ volume ของข้อมูลที่เพิ่มขึ้น ลองมาดูตัวอย่างโค้ดในภาษา C การใช้งาน Red-Black Tree สำหรับการ insert, insertAtFront, find และ delete.
// สมมุติโค้ด C สำหรับแสดงการกระทำพื้นฐานของ Red-Black Tree
#include
#include
/* ใส่โครงสร้างข้อมูลและฟังก์ชันสำหรับ Red-Black Tree ที่นี่ */
// เพิ่มข้อมูล
void insert(int data) {
// โค้ดสำหรับการแทรกข้อมูลที่นี่
}
// ค้นหาข้อมูล
Node* find(int data) {
// โค้ดสำหรับการค้นหาข้อมูลที่นี่
// คืนค่า Node ที่พบหรือ NULL ถ้าไม่พบ
}
// ลบข้อมูล
void delete(int data) {
// โค้ดสำหรับการลบข้อมูลที่นี่
}
/* หมายเหตุ: แสดงตัวอย่างโค้ดเพื่อเป็นแนวทางเท่านั้น ไม่ได้เป็นโค้ดสมบูรณ์สามารถทำงานได้จริง */
int main() {
// ตัวอย่างการใช้งานฟังก์ชันที่ได้ประกาศไว้ข้างต้น
insert(50);
insert(30);
insert(20);
Node* found = find(30);
if (found != NULL) {
printf("Found: %d\n", found->data);
}
delete(20);
// ดำเนินการต่อ...
return 0;
}
ในทุกการแทรก(insert) หรือการลบ(delete) ข้อมูล Red-Black Tree จะต้องดำเนินการ re-balance ต้นไม้เพื่อรักษาความสมดุลตามคุณสมบัติที่กล่าวไป การค้นหา(find) เกิดขึ้นโดยการท่องไปตามโหนดของต้นไม้จากรากไปยังใบไม้ และหากไม่พบข้อมูลก็จะคืนค่า NULL
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM