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

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

(เก็บกวาด +แจ้งรอตรวจสอบด้วยบอต)
{{ขาดอ้างอิง}}
{{รอการตรวจสอบ}}
{{กล่องข้อมูล โครงสร้างข้อมูล
| ชื่อ = ต้นไม้แดงดำ (Red-Black Tree)
| ภาพ = [[ภาพไฟล์:Red-black tree example.svg|200px]]
| description = ตัวอย่าง[['''ต้นไม้แดงดำ]]'''
| 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 โดยใช้ปมแบบสองทั้งหมด โดยสำหรับปมแบบ
* การเพิ่ม การลบ และการค้นหา
== ความเร็วที่ใช้ในการทำงาน ==
เนื่องจากต้นไม้แดงดำ มีความสูงจำกัดแน่นอนเป็น log2n ถึง log4n จึงประกันเวลาการทำงานอยู่ใน [[สัญกรณ์โอใหญ่|O (log n)]]
== [[ประเภทข้อมูล]]ที่ใช้สร้างต้นไม้แดงดำ ==
ปมของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจากปมของต้นไม้ค้นหาแบบทวิภาคแบบปกติคือจะมีการเพิ่มตัวแปรที่เก็บ