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

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