ต้นไม้แดงดำ
 | บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
| ต้นไม้แดงดำ (red-black tree) | |
|---|---|
 ตัวอย่างต้นไม้แดงดำ | |
| ความสำคัญของลำดับ | เรียงจากน้อยไปมาก |
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำ |
| เวลาที่ใช้ค้นหาตามค่า | O (log n) |
| เวลาที่ใช้ในการเข้าถึง | O (log n) |
| การทำให้ว่าง | ทำรากให้เป็น null |
| เวลาที่ใช้ทำให้ว่าง | O (1) |
| โครงสร้างต้นแบบ | ต้นไม้ค้นหาแบบทวิภาค, ต้นไม้ได้ดุล 2-3-4 |
| โครงสร้างที่นำไปใช้ | ต้นไม้แบบบี |
ต้นไม้แดงดำ (อังกฤษ: red-black tree) เป็นต้นไม้ค้นหาแบบทวิภาคที่ประยุกต์แนวคิดมาจากต้นไม้ได้ดุล 2-3-4 ให้เป็นต้นไม้ค้นหาแบบทวิภาค โดยที่ปมของต้นไม้แดงดำจะมีการเก็บตัวแปรหนึ่ง มักเรียกว่าสีแดงและสีดำ มีสองสีซึ่งสามารถเก็บด้วยค่าความจริงหรือตัวแปรขนาดหนึ่งบิตได้ และทำให้ต้นไม้นี้ถูกเรียกชื่อว่า ต้นไม้แดงดำ
ลักษณะของต้นไม้แดงดำ
[แก้]ต้นไม้แดงดำ เป็นต้นไม้ค้นหาทวิภาคซึ่งแต่ละ Node ของต้นไม้จะมีสีกำกับคือเป็นสีแดงหรือไม่ก็ดำ เป็นต้นไม้ที่นำแนวคิดมาจากต้นไม้ได้ดุล 2-3-4 มาประยุกต์โดยใช้ Node แบบสองทั้งหมด โดยสำหรับ Node แบบสามจะถูกแทนด้วย Node แบบสองสองและเรียงกันโดย Node ใด Node หนึ่งเป็นสีแดง ส่วน Node แบบสี่จะถูกแทนด้วย Node แบบสองสาม โดยลูกทั้งคู่เป็นสีแดง มีข้อกำหนดต่างๆตามต้นไม้ค้นหาทวิภาค และมีข้อบังคับเพิ่มเติมคือ
1.Node เป็นสีแดงหรือสีดำ
2.ราก(Root)เป็นสีดำ
3.ใบ(leaves)ทุกใบเป็นสีดำ
4.ลูกของ Node ที่เป็นสีแดงต้องเป็นสีดำ
5.ทุกๆทางเดินอย่างง่าย(simple path; ทางเดินที่ผ่านแต่ละ Node เพียงครั้งเดียว)จากรากไปยังใบจะผ่านจำนวน Node สีดำเท่ากัน
จุดเด่นของต้นไม้แดงดำ
[แก้]ต้นไม้แดงดำดัดแปลงมาจากต้นไม้ได้ดุล 2-3-4 ซึ่งถูกกันความสูงระหว่าง log2n ถึง log4n ระยะทางจากรากไปยังใบที่อยู่ใกล้ที่สุด กับระยะทางจากรากไปยังใบที่อยู่ไกลที่สุดห่างกันไม่เกิน สองเท่า (พิสูจน์โดย Contradiction ให้ระยะทางห่างกันเกินสองเท่า แต่จำนวน Node สีดำจะต้องเท่ากันตามคุณสมบัติของต้นไม้แดงดำดังนั้นจำนวน Node สีแดงของเส้นทางที่ไกลย่อมต้องมากกว่า black-height(จำนวน Node สีดำจากรากไปยังใบ) และมากกว่าจำนวน Node สีแดงของเส้นทางที่ใกล้ แต่ว่าลูกของNodeสีแดงจะต้องเป็นสีดำเสมอทำให้เกิดข้อขัดแย้ง)จึงสามารถบอกได้ว่าต้นไม้แดงดำนี้ค่อนข้างได้ดุลย์ และเนื่องจากประสิทธิภาพเชิงเวลาของการกระทำต่างๆในต้นไม้ค้นหาทวิภาคนั้นขึ้นอยู่กับความสูงทำให้การทำงานมีประสิทธิภาพที่ดีแม้จะอยู่ในกรณีย่ำแย่(ช้ากว่าไม่เกินสองเท่าของกรณีที่ดี) ซึ่งต่างจาก Binary search tree ทั่วไป
บริการที่มักจะมี
[แก้]- การเพิ่ม การลบ และการค้นหา
ความเร็วที่ใช้ในการทำงาน
[แก้]เนื่องจากต้นไม้แดงดำ มีความสูงจำกัดแน่นอนเป็น log2n ถึง log4n จึงประกันเวลาการทำงานอยู่ใน O (log n)
ประเภทข้อมูลที่ใช้สร้างต้นไม้แดงดำ
[แก้]Node ของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจาก Node ของ binary search tree แบบปกติคือจะมีการเพิ่มตัวแปรที่เก็บ สี แดงดำ อาจเป็น ตัวเลข หรือค่าความจริง ซึ่งใช้หน่วยจำเพิ่มขึ้นเพียงแค่หนึ่งบิตต่อหนึ่งปม การแสดงสีอาจแสดงด้วย edge แทนที่จะเป็นสีของ nodeซึ่งไม่ได้ทำให้เกิดข้อแตกต่างแต่อย่างใด
การสร้างบริการของต้นไม้แดงดำ
[แก้]การเพิ่มสมาชิก
[แก้]การเพิ่มสมาชิกของต้นไม้แดงดำจะเลียนแบบการทำงานของต้นไม้ได้ดุล 2-3-4 ซึ่งมีการเปลี่ยนสมาชิกของ Node ให้สูงขึ้นไป หรือการแตก Node เหล่านี้สามารถแทนด้วยต้นไม้แดงดำด้วยวิธีการจัดการตามสมบัติของต้นไม้แดงดำที่ว่า ลูกของ Node ที่เป็นสีแดงต้องเป็นสีดำ และจัดการดังต่อไปนี้ได้
- เพิ่มสมาชิกโดยใช้วิธีการเดียวกับ binary search tree ทั่วไป เพียงแต่ Node ที่เพิ่มใหม่นี้ให้เป็น Node สีแดง
- สำรวจว่า Node พ่อของ Node ใหม่ที่เพิ่มขึ้นเป็นสีแดงหรือไม่ ถ้าใช่จะขัดกับสมบัติกล่าวมาข้างต้น ก็จะทำได้สองวิธีดังนี้
- การสลับสีสาม Node ในกรณีที่มีการต่อในลักษณะคล้ายกับต่อ Node แบบสี่ การสลับสีสาม Node จะเสมือนการแตก Node ในต้นไม้ได้ดุล2-3-4
- การหมุน Node และสลับสีสาม Node ในบางกรณีการสลับสีสาม Node เฉย ๆ ไม่อาจช่วยให้ถูกต้องกับสมบัติที่กล่าวมาข้างต้นได้ ดังนั้นการหมุน Node เท่านั้นจึงช่วยให้สมบัติถูกต้องแบบนี้จะสอดคล้องกับการเพิ่มข้อมูลใน Node ในต้นไม้ได้ดุล2-3-4
การลบสมาชิก
[แก้]สำหรับการ delete ก็จะเป็นลักษณะเดียวกับการทำ insert คือ operation ของการทำ delete ทั่วๆไปจะมีลักษณะเหมือนกับ delete ของ Binary Search Tree เริ่มจากพิจารณาว่า Node ที่จะทำการ delete นั้นไม่มีลูกเป็น Node ภายใน , มีลูก 1 Node เป็น Node ภายใน, ลูกทั้ง 2 Node เป็น Node ภายใน โดยถ้าเป็นกรณีที่ Node ที่จะทำการ delete ไม่มีลูกเป็น Node ภายในก็จะลบ Node นั้นทิ้งแล้วแทนด้วย sentinelเลย แต่ถ้ามี 1 Node ภายใน ก็จะแทน Node ที่ต้องการลบด้วยลูกของ Node นั้นเลย และในกรณีสุดท้ายจะหา successor (ตัวที่มีค่าน้อยที่สุดที่มีค่ามากกว่า Node นั้น) มาแล้วทำการลบ successor แทน แล้วย้ายค่าของ successor มาไว้ใน Node นั้น จากนั้นก็ต้องพิจารณาว่าการลบนั้นทำให้เกิดข้อขัดแย้งในคุณสมบัติ 5 ข้อหรือไม่ โดยจะเกิดข้อขัดแย้งขึ้นเมื่อ Node ที่เราทำการลบไป เป็นสีดำก็จะต้องทำการ fixup เพื่อขจัดข้อขัดแย้งไป
การค้นหาสมาชิก
[แก้]การค้นหาสมาชิกนั้นสะดวกมากกว่าต้นไม้ได้ดุล2-3-4 เพราะใช้วิธีค้นหาแบบเดียวกับ Binary search tree ได้