ต้นไม้สีแดง-ดำในโครงสร้างข้อมูล

ในส่วนนี้เราจะมาดูกันว่าต้นไม้สีแดง-ดำคืออะไร ต้นไม้สีแดง-ดำเป็นต้นไม้ค้นหาไบนารีที่สมดุลในตัวเอง มีเงื่อนไขบางประการสำหรับแต่ละโหนด เหล่านี้เป็นเหมือนด้านล่าง −

• แต่ละโหนดมีสี อันไหนแดงหรือดำ

• รากจะเป็นสีดำเสมอ

• จะไม่มีโหนดสีแดงสองโหนดที่อยู่ติดกัน

• ทุกเส้นทางจากโหนด (รวมถึงรูท) ไปยังโหนด NULL ที่สืบทอดมามีจำนวนโหนดสีดำเท่ากัน

ตัวอย่างต้นไม้สีแดง-ดำ

ต้นไม้สีแดง-ดำ มีโหนด Null อยู่ที่ใบ

เปรียบเทียบกับแผนผัง AVL

ต้นไม้ AVL มีความสมดุลมากกว่าต้นไม้สีแดงดำ แต่ข้อเสียที่สำคัญคือ จะมีการหมุนเวียนมากขึ้นระหว่างการแทรกและการลบ สำหรับการแทรกและการลบหลายรายการ ต้นไม้สีแดง-ดำจะเป็นประโยชน์