บทความน ไม ม การอ างอ งจากแหล งท มาใดกร ณาช วยปร บปร งบทความน โดยเพ มการอ างอ งแหล งท มาท น าเช อถ อ เน อความท ไม ม แหล

ต้นไม้แดงดำ (อังกฤษ: red-black tree) เป็นต้นไม้ค้นหาแบบทวิภาคที่ประยุกต์แนวคิดมาจาก ให้เป็นต้นไม้ค้นหาแบบทวิภาค โดยที่ปมของต้นไม้แดงดำจะมีการเก็บตัวแปรหนึ่ง มักเรียกว่าสีแดงและสีดำ มีสองสีซึ่งสามารถเก็บด้วยค่าความจริงหรือตัวแปรขนาดหนึ่งบิตได้ และทำให้ต้นไม้นี้ถูกเรียกชื่อว่า ต้นไม้แดงดำ

ต้นไม้แดงดำ (red-black tree)
ตัวอย่างต้นไม้แดงดำ
ความสำคัญของลำดับ	เรียงจากน้อยไปมาก
การซ้ำกันของสมาชิก	ไม่อนุญาตให้ซ้ำ
เวลาที่ใช้ค้นหาตามค่า	O (log n)
เวลาที่ใช้ในการเข้าถึง	O (log n)
การทำให้ว่าง	ทำรากให้เป็น null
เวลาที่ใช้ทำให้ว่าง	O (1)
โครงสร้างต้นแบบ	ต้นไม้ค้นหาแบบทวิภาค,
โครงสร้างที่นำไปใช้	ต้นไม้แบบบี

ลักษณะของต้นไม้แดงดำ

ต้นไม้แดงดำ เป็นต้นไม้ค้นหาทวิภาคซึ่งแต่ละ 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 ใหม่ที่เพิ่มขึ้นเป็นสีแดงหรือไม่ ถ้าใช่จะขัดกับสมบัติกล่าวมาข้างต้น ก็จะทำได้สองวิธีดังนี้
1. การสลับสีสาม Node ในกรณีที่มีการต่อในลักษณะคล้ายกับต่อ Node แบบสี่ การสลับสีสาม Node จะเสมือนการแตก Node ในต้นไม้ได้ดุล2-3-4
2. การหมุน 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 ได้