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

(โรบอต: เปลี่ยนจาก หมวดหมู่:ต้นไม้ (โครงสร้าง) ไปยัง หมวดหมู่:ต้นไม้ (โครงสร้างข้อมูล))
| order = เรียงจากน้อยไปมาก
| same = ไม่อนุญาตให้ซ้ำ
| findi =
| finde = O (log n)
| access = O (log n)
| empty = ทำรากให้เป็น null
| emptytime = O (1)
| parent = [[ต้นไม้ค้นหาแบบทวิภาค]], [[ต้นไม้ได้ดุล 2-3-4]]
| children = [[ต้นไม้แบบบี]]
}}
'''ต้นไม้แดงดำ''' ({{lang-en|Red-Black Tree}}) เป็น[[ต้นไม้ค้นหาแบบทวิภาค]]ที่ประยุกต์แนวคิดมาจาก[[ต้นไม้ได้ดุล 2-3-4]] ให้เป็นต้นไม้ค้นหาแบบทวิภาค โดยที่ปมของต้นไม้แดงดำจะมีการเก็บตัวแปรหนึ่ง มักเรียกว่าสีแดงและสีดำ มีสองสีซึ่งสามารถเก็บด้วยค่าความจริงหรือตัวแปรขนาดหนึ่ง[[บิต]]ได้ และทำให้ต้นไม้นี้ถูกเรียกชื่อว่า '''ต้นไม้แดงดำ'''
== ลักษณะของต้นไม้แดงดำ ==
ต้นไม้แดงดำเป็นต้นไม้ที่นำแนวคิดมาจากต้นไม้ได้ดุล 2-3-4 โดยใช้ปมแบบสองทั้งหมด โดยสำหรับปมแบบ
ปมของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจากปมของต้นไม้ค้นหาแบบทวิภาคแบบปกติคือจะมีการเพิ่มตัวแปรที่เก็บ
สี แดงดำ อาจเป็น ตัวเลข หรือค่าความจริง ซึ่งใช้หน่วยจำเพิ่มขึ้นเพียงแค่หนึ่งบิตต่อหนึ่งปม
== การสร้างบริการของต้นไม้แดงดำ ==
=== การเพิ่มสมาชิก ===
การเพิ่มสมาชิกของต้นไม้แดงดำจะเลียนแบบการทำงานของต้นไม้ได้ดุล 2-3-4 ซึ่งมีการเปลี่ยนสมาชิกของปมให้สูงขึ้นไป หรือการแตกปม เหล่านี้สามารถแทนด้วยต้นไม้แดงดำด้วยวิธีการจัดการตามสมบัติของต้นไม้แดงดำที่ว่า
# สำรวจว่าปมพ่อของปมใหม่ที่เพิ่มขึ้นเป็นสีแดงหรือไม่ ถ้าใช่ก็จะขัดกับสมบัติที่"ห้ามปมที่เป็นพ่อ-ลูกกันเป็นสีแดงเหมือนกัน"ก็จะทำได้สองวิธีดังนี้
## การสลับสีสามปม ในกรณีที่มีการต่อในลักษณะคล้ายกับต่อปมแบบสี่ การสลับสีสามปมจะเสมือนการแตกปมในต้นไม้ได้ดุล2-3-4
## การหมุนปมและสลับสีสามปม ในบางกรณีการสลับสีสามปมเฉยๆเฉย ๆ ไม่อาจช่วยให้ถูกต้องกับสมบัติที่ว่า"ห้ามปมที่เป็นพ่อ-ลูกกันเป็นสีแดงเหมือนกัน" ดังนั้นการหมุนปมเท่านั้นจึงช่วยให้สมบัติถูกต้องแบบนี้จะสอดคล้องกับการเพิ่มข้อมูลในปมในต้นไม้ได้ดุล2-3-4
=== การลบสมาชิก ===
{{โครง-ส่วน}}
* [[ต้นไม้บาน]]
 
[[หมวดหมู่:ต้นไม้ (โครงสร้างข้อมูล)แบบทวิภาค]]
[[หมวดหมู่:1972 in computer science]]
[[หมวดหมู่:ต้นไม้แบบบี]]
{{โครงสร้างข้อมูล}}
 
[[หมวดหมู่:ต้นไม้ (โครงสร้างข้อมูล)]]
 
[[cs:Červeno-černý strom]]