ผลต่างระหว่างรุ่นของ "ต้นไม้แดงดำ"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
บรรทัด 33:
== จุดเด่นของต้นไม้แดงดำ ==
ต้นไม้แดงดำดัดแปลงมาจากต้นไม้ได้ดุล 2-3-4 ซึ่งถูกกันความสูงระหว่าง log2n ถึง log4n ระยะทางจากรากไปยังใบที่อยู่ใกล้ที่สุด กับระยะทางจากรากไปยังใบที่อยู่ไกลที่สุดห่างกันไม่เกิน สองเท่า (พิสูจน์โดย Contradiction ให้ระยะทางห่างกันเกินสองเท่า แต่จำนวน Node สีดำจะต้องเท่ากันตามคุณสมบัติของต้นไม้แดงดำดังนั้นจำนวน Node สีแดงของเส้นทางที่ไกลย่อมต้องมากกว่า black-height และมากกว่าจำนวน Node สีแดงของเส้นทางที่ใกล้ แต่ว่าลูกของNodeสีแดงจะต้องเป็นสีดำเสมอทำให้เกิดข้อขัดแย้ง)จึงสามารถบอกได้ว่าต้นไม้แดงดำนี้ค่อนข้างได้ดุลย์ และเนื่องจากประสิทธิภาพเชิงเวลาของการกระทำต่างๆในต้นไม้ค้นหาทวิภาคนั้นขึ้นอยู่กับความสูงทำให้การทำงานมีประสิทธิภาพที่ดีแม้จะอยู่ในกรณีย่ำแย่(ช้ากว่าไม่เกินสองเท่า ของกรณีที่ดี) ซึ่งต่างจาก Binary search tree ทั่วไป
== บริการที่มักจะมี ==
* การเพิ่ม การลบ และการค้นหา
| |||