ต้นไม้สีแดงและสีดำเป็นต้นไม้ค้นหาที่สมดุลแบบไบนารี แต่ละโหนดมีบิตที่เก็บเพื่อแสดงสีของโหนดซึ่งอาจเป็นสีแดงหรือสีดำ
ต้นไม้สีแดงและสีดำมีคุณสมบัติดังต่อไปนี้:
(1) แต่ละโหนดเป็นสีแดงหรือสีดำ
(2) โหนดรูทเป็นสีดำ
(3) ถ้าโหนดเป็นสีแดงลูกชายสองคนของมันเป็นสีดำ
(4) สำหรับแต่ละโหนดเส้นทางทั้งหมดจากโหนดนั้นไปยังลูกหลานของมันมีจำนวนโหนดสีดำจำนวนเท่ากัน
ผ่านคุณสมบัติของต้นไม้สีแดงดำรับประกันได้ว่าการใช้งานบนต้นไม้สีแดงดำทั้งหมดสามารถมั่นใจได้ว่าเวลาทำงานของการดำเนินการคือลอการิทึม (ยกเว้นการค้นหาช่วงเวลาพิเศษที่ใช้เป็นสัดส่วนกับจำนวนคีย์ที่ส่งคืน)
treemap ของ Java ถูกนำไปใช้ผ่านต้นไม้สีแดงและสีดำ
หากคุณไม่วาดรูปมันเป็นเรื่องง่ายที่จะสับสน ต่อไปนี้เป็นไดอะแกรมเพื่อแสดงให้เห็นถึงการทำงานของต้นไม้สีแดงและสีดำ
หลังจากแทรกโหนดสีแดงลงในต้นไม้สีแดงและสีดำจะมี 6 สถานการณ์: n หมายถึงโหนดที่แทรก P แสดงถึงโหนดพาเรนต์ u แสดงถึงโหนดลุง G หมายถึงโหนดปู่และ x หมายถึงโหนดการทำงานปัจจุบัน
รหัสมีดังนี้:
คลาสสาธารณะ redblackbst <คีย์ขยาย <key>, ค่า> {รูทโหนดส่วนตัว; บูลีนสุดท้ายคงที่ส่วนตัวสีแดง = true; บูลีนสีดำสุดท้ายแบบคงที่ส่วนตัว = เท็จ; โหนดคลาสส่วนตัว {คีย์ส่วนตัว // คีย์ค่าส่วนตัว Val; // ค่าโหนดส่วนตัวซ้าย, ขวา, ผู้ปกครอง; // ซ้ายและซ้ายต้นไม้ลูกและโหนดแม่แม่สีบูลีนส่วนตัว; // สีของลิงก์ที่ชี้ไปที่โหนดโหนดสาธารณะโหนด (คีย์คีย์, ค่า Val, โหนดพาเรนต์, สีบูลีน) {this.key = key; this.val = val; this.color = color; }} ค่าสาธารณะรับ (คีย์คีย์) {node x = root; ในขณะที่ (x! = null) {int cmp = key.compareto (x.key); if (cmp <0) x = x.left; อื่นถ้า (cmp> 0) x = x.right; อื่นกลับ x.val; } return null; } โมฆะสาธารณะใส่ (คีย์คีย์, val val) {ถ้า (root == null) {// ถ้าเป็นโหนดรูทให้สร้างโหนดเป็น black root = โหนดใหม่ (คีย์, val, null, ดำ); กลับ; } // ค้นหาตำแหน่งการแทรกที่เหมาะสมโหนด parent = null; โหนด cur = รูท; ในขณะที่ (cur! = null) {parent = cur; if (key.compareto (cur.key)> 0) cur = cur.right; else cur = cur.left; } โหนด n = โหนดใหม่ (คีย์, val, พาเรนต์, สีแดง); // ORD โหนดใหม่ปกติเป็นสีแดง // แทรกโหนดใหม่ภายใต้ Parents ถ้า (key.Compareto (parent.key)> 0) parent.right = n; อื่น ๆ parent.left = n; // หลังจากแทรกโหนดใหม่คุณต้องปรับสีและคุณสมบัติของโหนดบางอย่างในต้นไม้เพื่อให้แน่ใจว่าคุณสมบัติของต้นไม้สีแดงและสีดำจะไม่ถูกทำลาย fixafterinsertion (n); } โหนดส่วนตัว parentof (โหนด x) {return (x == null? null: x.parent); } private boolean colorof (node x) {return (x == null? null: x.right); } โหนดส่วนตัวซ้าย (โหนด x) {return (x == null? null: x.right); } โหนดส่วนตัว Rightof (โหนด x) {return (x == null? null: x.right); } โมฆะส่วนตัว setColor (โหนด X, สีบูลีน) {ถ้า (x! = null) x.color = สี; } โมฆะส่วนตัว fixafterinsertion (โหนด x) {ในขณะที่ (x! = null && colorof (parentof (x)) == สีแดง) {node grandpa = parentof (parentof (x)); โหนด parent = parentof (x); if (parent == leftof (คุณปู่)) {// กรณี 1 || case2 || case3 โหนดลุง = Rightof (คุณปู่); if (colorof (ลุง) == สีแดง) {// case1, ลุงเป็นสีแดง setcolor (parent, black); // โหนดพาเรนต์เป็นสีดำ setColor (ลุง, ดำ); // โหนดลุงเป็นสีดำ setcolor (คุณปู่, สีแดง); // โหนดปู่คือสีแดง x = คุณปู่; // เนื่องจากโหนดปู่เป็นสีแดงจากสีดำเป็นสีแดงคุณลักษณะสีแดงและสีดำของโหนดแม่และบรรพบุรุษของมันจำเป็นต้องได้รับการปรับปรุง} อื่น {// case2 || case3, ลุงเป็นสีดำถ้า (x == rightof (parent)) {// case2 x = parent; Rotateleft (x); } // case3 setColor (parent, black); SetColor (คุณปู่, สีแดง); Rotateright (คุณปู่); }} else {// case4 || กรณีที่ 5 || case6 โหนดลุง = ซ้าย (ปู่); if (colorof (ลุง) == สีแดง) {// case4 || case5 || case6 setColor (parent, black); SetColor (ลุง, ดำ); SetColor (คุณปู่, สีแดง); x = คุณปู่; } else {// case5 || case6, ลุงเป็นสีดำถ้า (x == ซ้าย (parent)) {// case5 x = parent; Rotateright (x); } // case6 setColor (parent, black); SetColor (คุณปู่, สีแดง); Rotateleft (คุณปู่); }}}} โมฆะส่วนตัว rotateleft (โหนด x) {ถ้า (x == null) ส่งคืน; โหนด y = x.right; x.right = y.left; if (y.left! = null) y.left.parent = x; y.left = x; y.parent = x.parent; if (x.parent == null) {root = y; } อื่นถ้า (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; } โมฆะส่วนตัว rotateright (โหนด x) {if (x == null) return; โหนด y = x.left; x.left = y.right; ถ้า (y.right! = null) y.right.parent = x; y.right = x; y.parent = x.parent; if (x.parent == null) {root = y; } อื่นถ้า (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; -จำเป็นต้องวาดแผนภาพสำหรับ rotateleft และ rotateright ด้านบน:
บทความข้างต้นขึ้นอยู่กับหลักการของการดำเนินการแทรกต้นไม้สีแดงและสีดำและวิธีการใช้งาน Java (การแบ่งปัน) ซึ่งเป็นเนื้อหาทั้งหมดที่ฉันแบ่งปันกับคุณ ฉันหวังว่าคุณจะให้ข้อมูลอ้างอิงและฉันหวังว่าคุณจะสนับสนุน wulin.com มากขึ้น