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

Red Black Tree เป็นต้นไม้ค้นหาแบบไบนารีที่สมดุลในตัวเอง โดยที่แต่ละโหนดของต้นไม้จะมีสีเป็นสีแดงหรือสีดำ มีการดำเนินการสามประเภทที่เราสามารถทำได้บน Red Black Tree – การค้นหา การแทรก และการลบ

สมมติว่าเราต้องแทรกองค์ประกอบใน Red Black Tree ต่อไปนี้

ในการแทรกองค์ประกอบในทรีสีแดง-ดำ แนวคิดนั้นง่ายมาก - เราทำการแทรกเช่นเดียวกับที่เราแทรกในไบนารีทรีปกติ เราเริ่มต้นจากโหนดรูทโดยการตรวจสอบสีของโหนดและแทรกลงในตำแหน่งเฉพาะ อย่างไรก็ตาม ในต้นไม้สีแดง-ดำ ควรมีขั้นตอนเพิ่มเติมในการแทรกองค์ประกอบเข้าไป

อย่างไรก็ตาม เราควรรู้ว่าต้นไม้สีแดงดำมีความสมดุลเมื่อเป็นไปตามเงื่อนไข -

• โหนดรากทั้งหมดต้องเป็นสีดำ

• ทุกโหนดเป็นสีแดงหรือสีดำ

• หากโหนดเป็นสีแดง ลูกของโหนดนั้นต้องเป็นสีดำ

• เส้นทางจากรูทจนถึงจุดสิ้นสุดต้องมีโหนดสีดำจำนวนเท่ากัน

หากเราต้องการแทรกโหนดใหม่ในทรีสีแดง-ดำ เราก็สามารถทำได้โดยดูที่ขั้นตอนการแทรก

ขั้นตอนในการแทรกองค์ประกอบในต้นไม้สีแดงสีดำ -

• ตรวจสอบว่าต้นไม้ว่างเปล่าหรือไม่ หากต้นไม้ว่างเปล่า ให้แทรกโหนดใหม่และระบายสีเป็นสีดำ (เพราะรูตโหนดต้องเป็นสีดำเสมอ)’

• มิฉะนั้น หาก Tree ไม่ว่างเปล่า ให้แทรกโหนดใหม่เป็นโหนดปลายสุดแล้วระบายสีเป็นสีแดง

• หากพาเรนต์ของโหนดใหม่เป็นสีแดงและโหนดเพื่อนบ้าน (ของพาเรนต์) เป็นสีแดงด้วย ให้พลิกสีของทั้งเพื่อนบ้านและผู้ปกครองและปู่ย่าตายาย (หากไม่ใช่โหนดรูท มิฉะนั้น ให้พลิกสีของผู้ปกครองและเพื่อนบ้านเท่านั้น) เช่น , ดำ.

• หากพาเรนต์ของโหนดใหม่เป็นสีแดง และโหนดใกล้เคียง (ของพาเรนต์) ว่างเปล่าหรือเป็น NULL ให้หมุน (หมุนซ้าย-ซ้ายหรือหมุนซ้าย-ขวา) โหนดและพาเรนต์ใหม่

การหมุนมีสองประเภทที่จะนำไปใช้ - การหมุนซ้ายซ้ายและการหมุนซ้ายขวา การหมุนเวียนจะใช้ในบางเงื่อนไขเท่านั้น เงื่อนไขคือ −

• หากพาเรนต์ของโหนดใหม่เป็นสีแดง และโหนดข้างเคียงว่างเปล่าหรือเป็น NULL ให้หมุนการหมุนไปทางซ้ายหรือขวา

• ในการหมุนซ้าย-ซ้าย ให้พลิกสีของพ่อแม่และปู่ย่าตายาย ทำให้พ่อแม่เป็นปู่ย่าตายายและปู่ย่าตายายเป็นเด็ก

อัลกอริทึม

RBTreeInsertion(รูท,คีย์)

//The color of the inserted new node is Red
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 the parent of the new node is Red(if there is Grandparent instead
root Node) Flip the color.
   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]
      //When parent of new node has the red color and its sibling is NULL
   LeftRotate(root,key)
   color(p[key]) ← Black
   color(p[p[key]]) ← Red
RotateRight(root,p[p[key]])
else exchange then left and right elements to make it balance.
color(root)← Black