Red-Black Tree คืออะไร
Red-Black Trees เป็น Self-Balancing Binary Search Tree มีเงื่อนไขสำหรับแต่ละโหนด:
- ทุกโหนดมีสี: Red หรือ Black
- Root ต้องเป็น Black เสมอ
- ไม่มีโหนด Red 2 ตัวติดกัน (Parent-Child)
- ทุกเส้นทางจากโหนดใดๆ (รวม Root) ไปยัง Descendant NULL Node ต้องมีจำนวน Black Nodes เท่ากัน
ตัวอย่าง Red-Black Tree
Red-Black Tree พร้อม NULL Nodes ที่ใบ
เปรียบเทียบกับ AVL Tree
AVL Trees สมดุลกว่า Red-Black Tree แต่ข้อเสียคือ มีการ Rotate มากกว่าเวลา Insert/Delete สำหรับการ Insert/Delete หลายครั้ง Red-Black Tree จะดีกว่า
