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

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
OctraBot (คุย | ส่วนร่วม)
แทนที่ ‘(?mi)\{\{Link GA\|.+?\}\}\n?’ ด้วย ‘’: เลิกใช้ เปลี่ยนไปใช้วิกิสนเทศ
ไม่มีความย่อการแก้ไข
บรรทัด 38:
## การหมุนปมและสลับสีสามปม ในบางกรณีการสลับสีสามปมเฉย ๆ ไม่อาจช่วยให้ถูกต้องกับสมบัติที่ว่า"ห้ามปมที่เป็นพ่อ-ลูกกันเป็นสีแดงเหมือนกัน" ดังนั้นการหมุนปมเท่านั้นจึงช่วยให้สมบัติถูกต้องแบบนี้จะสอดคล้องกับการเพิ่มข้อมูลในปมในต้นไม้ได้ดุล2-3-4
=== การลบสมาชิก ===
สำหรับการ delete ก็จะเป็นลักษณะเดียวกับการทำ insert คือ operation ของการทำ delete ทั่วๆไปจะมีลักษณะเหมือนกับ delete ของ Binary Search Tree เริ่มจากพิจารณาว่า Node ที่จะทำการ delete นั้นไม่มีลูกเป็น Node ภายใน , มีลูก 1 Node เป็น Node ภายใน, ลูกทั้ง 2 Node เป็น Node ภายใน โดยถ้าเป็นกรณีที่ Node ที่จะทำการ delete ไม่มีลูกเป็น Node ภายในก็จะลบ Node นั้นทิ้งแล้วแทนด้วย sentinelเลย แต่ถ้ามี 1 Node ภายใน ก็จะแทน Node ที่ต้องการลบด้วยลูกของ Node นั้นเลย และในกรณีสุดท้ายจะหา successor (ตัวที่มีค่าน้อยที่สุดที่มีค่ามากกว่า Node นั้น) มาแล้วทำการลบ successor แทน แล้วย้ายค่าของ successor มาไว้ใน Node นั้น จากนั้นก็ต้องพิจารณาว่าการลบนั้นทำให้เกิดข้อขัดแย้งในคุณสมบัติ 5 ข้อหรือไม่ โดยจะเกิดข้อขัดแย้งขึ้นเมื่อ Node ที่เราทำการลบไป เป็นสีดำก็จะต้องทำการ fixup เพื่อขจัดข้อขัดแย้งไป
{{โครง-ส่วน}}
 
=== การค้นหาสมาชิก ===