การแทรกข้อมูลใน Red-Black Tree ในโครงสร้างข้อมูล

Red-Black Tree

Self-Balanced BST โหนดสี Red หรือ Black มี 3 Operations: Search, Insert, Delete

ตัวอย่าง Tree

แนวคิดการ Insert

Insert เหมือน BST ปกติ เริ่มจาก Root ตรวจสอบสี แทรกตำแหน่งที่เหมาะสม แต่ Red-Black Tree ต้องมีขั้นตอนเพิ่มเติม

เงื่อนไข Red-Black Tree ที่สมดุล

• Root ต้องเป็น Black เสมอ
• ทุกโหนดเป็น Red หรือ Black
• ถ้าโหนดเป็น Red → ลูกต้องเป็น Black
• ทุกเส้นทาง Root ถึง Leaf ต้องมี Black Nodes เท่ากัน

ขั้นตอน Insert

1. Tree ว่าง? ใส่ Node ใหม่ สี Black (Root ต้อง Black)
2. Tree ไม่ว่าง: ใส่เป็น Leaf สี Red
3. ถ้า Parent เป็น Red และ Uncle (Sibling ของ Parent) เป็น Red → Flip สี Parent, Uncle, Grandparent (ถ้าไม่ใช่ Root) → Black
4. ถ้า Parent เป็น Red และ Uncle เป็น Empty/NULL → Rotate (Left-Left หรือ Left-Right)

Rotation Types

• Left-Left Rotation: Flip สี Parent/Grandparent Parent กลายเป็น Grandparent
• Left-Right Rotation

Pseudocode

color[key] ← Red
while(key ≠ root and color(p[key]) = Red) do
    if p[key] = left(p[p[key]])
        then y ← right[p[p[key]]]
        if color[y] = Red
            then color(p[key]) ← Black; color(p[p[key]]) ← Red; key ← p[p[key]]
        else if key = right[p[key]]
            then key ← p[key]; LeftRotate(root, key)
            color(p[key]) ← Black; color(p[p[key]]) ← Red; RightRotate(root, p[p[key]])
    else exchange left/right to balance
color(root) ← Black