ข้ามไปเนื้อหา

ผลต่างระหว่างรุ่นของ "ต้นไม้แดงดำ"

ไม่มีความย่อการแก้ไข
'''ต้นไม้แดงดำ''' ({{lang-en|Red-Black Tree}}) เป็น[[ต้นไม้ค้นหาแบบทวิภาค]]ที่ประยุกต์แนวคิดมาจาก[[ต้นไม้ได้ดุล 2-3-4]] ให้เป็นต้นไม้ค้นหาแบบทวิภาค โดยที่ปมของต้นไม้แดงดำจะมีการเก็บตัวแปรหนึ่ง มักเรียกว่าสีแดงและสีดำ มีสองสีซึ่งสามารถเก็บด้วยค่าความจริงหรือตัวแปรขนาดหนึ่ง[[บิต]]ได้ และทำให้ต้นไม้นี้ถูกเรียกชื่อว่า '''ต้นไม้แดงดำ'''
== ลักษณะของต้นไม้แดงดำ ==
ต้นไม้แดงดำ เป็นต้นไม้ที่นำแนวคิดมาจากต้นไม้ได้ดุลค้นหาทวิภาคซึ่งแต่ละ 2-3-4Node โดยใช้ปมแบบสองทั้งหมด โดยสำหรับปมแบบของต้นไม้จะมีสีกำกับคือเป็นสีแดงหรือไม่ก็ดำ
เป็นต้นไม้ที่นำแนวคิดมาจากต้นไม้ได้ดุล 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 แต่เพียงขยายปมแบบสามกับปมแบบสี่เป็นปมแบบสอง ทำให้ความสูงอาจเพิ่มจากต้นไม้ได้ดุล 2-3-4 ที่สมมูลกันประมาณสองเท่า เพราะความสูงเพิ่มอีกหนึ่งเท่าเมื่อขยายปมแบบสามและสี่ให้เป็นเป็นปมแบบสอง
ผู้ใช้นิรนาม