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