ต้นไม้สีแดงและสีดำ
ต้นไม้สีแดงและสีดำเป็นต้นไม้ที่มักถูกกล่าวถึงในโครงสร้างข้อมูลและอัลกอริทึม แต่ไม่สามารถอธิบายได้ในรายละเอียด พวกเขายังเป็นต้นไม้ที่มักถูกถามในการสัมภาษณ์ทางเทคนิค อย่างไรก็ตามไม่ว่าจะเป็นวัสดุในหนังสือหรือออนไลน์พวกเขามักจะเข้มงวดและเข้าใจยากกว่า คุณสามารถเข้าใจต้นไม้สีแดงและสีดำได้หรือไม่? บทความนี้จะอธิบายการแทรกและการลบของต้นไม้สีแดงและสีดำในรูปแบบกราฟิก
การเรียนรู้โครงสร้างต้นไม้เป็นกระบวนการที่ก้าวหน้า ต้นไม้ที่เรามักจะสัมผัสกับต้นไม้ไบนารี กล่าวง่ายๆว่าโหนดที่ไม่ใช่ใบแต่ละใบมีและมีลูกเพียงสองคนที่เรียกว่าเด็กซ้ายและลูกที่เหมาะสม มีต้นไม้ชนิดพิเศษในต้นไม้ไบนารีที่เรียกว่าต้นไม้ค้นหาไบนารี ต้นไม้ค้นหาไบนารีเป็นต้นไม้ที่สั่ง สำหรับโหนดที่ไม่ใช่ใบแต่ละใบค่าของทรีย่อยด้านซ้ายจะเล็กกว่ามันและค่าของทรีย่อยด้านขวานั้นมากกว่า ขั้นตอนต่อไปกว่าแผนผังการค้นหาแบบไบนารีคือต้นไม้สมดุลไบนารี นอกเหนือจากการสร้างความมั่นใจว่าคำสั่งซื้อต้นไม้สมดุลไบนารียังสามารถรักษาความสูงของความสูงระหว่างทรีทรีย่อยและขวาของแต่ละโหนดและไม่เกิน 1 ต้นไม้ที่สมดุลทั่วไปคือต้นไม้ AVL, Treaps, ต้นไม้สีแดงและสีดำ, ต้นไม้ยืดและอื่น ๆ
ต้นไม้สีแดงและสีดำเป็นต้นไม้ค้นหาไบนารี แต่เพิ่มบิตที่เก็บของแต่ละโหนดเพื่อแสดงสีของโหนดซึ่งอาจเป็นสีแดงหรือสีดำ โดยการ จำกัด วิธีที่แต่ละโหนดมีการแรเงาบนเส้นทางใด ๆ จากรูทถึงใบไม้ต้นไม้สีแดงดำทำให้มั่นใจได้ว่าจะไม่มีเส้นทางใดที่จะเป็นสองเท่าของเส้นทางอื่น ๆ จึงเข้าใกล้ความสมดุล
ต้นไม้สีแดงและสีดำเป็นไปตามคุณสมบัติ 5 ประการ:
โปรดทราบว่าในต้นไม้สีแดงดำชี้ให้ลูกของโหนดใบไม้ของต้นไม้ไบนารีแบบดั้งเดิมไปยังไม่มีและเรียกโหนดใบในต้นไม้สีแดงดำ โหนด NIL มีตัวชี้ไปยังโหนดพาเรนต์ซึ่งอาจเป็นสาเหตุที่ต้องเปลี่ยน NULL เป็น NIL
1. แทรกการทำงาน
ขั้นแรกให้ใส่โหนดใหม่ในการแทรกแผนผังไบนารี (โหนดใหม่ที่แทรกอยู่ทั้งหมดที่โหนดใบไม้) และวาดเป็นสีแดง จากนั้นวาดสีใหม่หรือหมุนเพื่อรักษาคุณสมบัติของต้นไม้สีแดงและสีดำ การปรับแบ่งออกเป็นสามสถานการณ์ต่อไปนี้:
1 โหนดใหม่ n ไม่มีโหนดพาเรนต์ (เช่นมันอยู่บนรูท)
ทาสีโหนดใหม่ n เป็นสีดำ
2 โหนดพาเรนต์ P ของโหนดใหม่ n เป็นสีดำ
ไม่จำเป็นต้องปรับ
3 โหนดพาเรนต์ p ของโหนดใหม่ n เป็นสีแดง
เนื่องจากต้นไม้สีแดงและสีดำไม่อนุญาตให้มีการปรับโหนดสีแดงสองโหนด (คุณสมบัติ 4) จึงจำเป็นต้องปรับ ตามสีของโหนดลุงของ N มันแบ่งออกเป็นสองสถานการณ์: (เราใช้โหนดแม่ของ N เป็นตัวอย่างของเด็กซ้ายเป็นตัวอย่างและ P เป็นเด็กที่เหมาะสมเป็นสถานการณ์ที่คล้ายกันดังนั้นฉันจะไม่อธิบายรายละเอียด)
3.1 โหนดลุงของโหนดใหม่ n เป็นสีแดง โหนดหลัก P และลุงโหนด U ของโหนดใหม่ n ถูกทาสีเป็นสีดำและโหนดปู่โหนด G ถูกทาสีเป็นสีแดงเพื่อให้แน่ใจว่าจำนวนโหนดสีดำที่มีอยู่บนเส้นทางจาก G ไปยังโหนด NULL แต่ละโหนดนั้นสอดคล้องกับอันดั้งเดิม แต่เนื่องจากเราเปลี่ยน G เป็นสีแดงถ้าพ่อของ G เป็นสีแดงก็อาจนำไปสู่โหนดสีแดงสองโหนดติดต่อกัน (ละเมิดธรรมชาติ 4) ดังนั้นจึงจำเป็นต้องตรวจสอบอีกครั้งว่า G ละเมิดธรรมชาติของต้นไม้สีแดงและสีดำ
3.2 โหนดลุงของโหนดใหม่ n เป็นสีดำ หากโหนดใหม่ n เป็นลูกซ้ายของโหนดพาเรนต์ P: วาดโหนดแม่เป็นสีดำให้วาดโหนดปู่ของปู่เป็นสีแดงแล้วหมุน G ขวาหนึ่งครั้ง
หากโหนดใหม่ n เป็นลูกที่ถูกต้องของโหนดแม่ p: ทำการหมุนซ้ายบนโหนดพาเรนต์ของมันปัญหาจะถูกเปลี่ยนเป็นสถานการณ์ของเด็กซ้าย
2. ลบการดำเนินการ
วิธีการใน "คำแนะนำสู่อัลกอริทึม" และวิกิพีเดียคือการลบโหนดสีดำ d, "ดันลง" สีดำของ d ไปยังโหนดลูกของมันคือ C มีชั้นสีดำพิเศษนอกเหนือจากสีของมันเอง เพื่อให้จำนวนโหนดสีดำบนเส้นทางทั้งหมดจะลดลงหนึ่งและยังคงเท่ากัน ในระหว่างการเคลื่อนไหวขึ้นไปสีโหนดบางอย่างอาจต้องหมุนและแก้ไขเพื่อให้แน่ใจว่าจำนวนโหนดสีดำบนเส้นทางยังคงไม่เปลี่ยนแปลง
วิธีการนี้อาจเป็นประโยชน์ต่อการใช้รหัส (ซึ่งสามารถใช้ในรูปแบบซ้ำ) แต่ก็ไม่สะดวกที่จะเข้าใจ (เชื่อส่วนตัว) เพื่อจุดประสงค์ในการทำความเข้าใจลำดับความสำคัญฉันได้จัดหมวดหมู่ดังต่อไปนี้โดยพิจารณาจากว่าลูกของโหนดที่ถูกลบ D เป็นไม่มี:
1 เด็กทั้งสองที่มีโหนด D ถูกลบไม่มี
1.1 หากโหนดที่ถูกลบ D เป็นสีแดงเพียงแทนที่ D ด้วย NIL
1.2 โหนดที่ถูกลบ D เป็นสีดำ (ลองใช้ D เป็นตัวอย่าง)
1.2.1 เด็กทั้งสองของ Node B ซึ่งเป็นพี่ชายของ D ถูกลบออกเป็นศูนย์
Node Brother B ของ D ถูกทาสีเป็นสีแดงและโหนดหลัก P ถูกทาสีเป็นสีดำ
ครึ่งสีแดงและสีดำครึ่งหนึ่งในรูปหมายความว่าโหนดอาจเป็นสีแดงหรือสีดำ หาก P กลายเป็นสีแดงจำนวนโหนดสีดำบนเส้นทางหลังจากการดัดแปลงจะเหมือนกับก่อนการลบ D; หาก P กลายเป็นสีดำการลบ D จะส่งผลให้โหนดสีดำน้อยลงหนึ่งโหนดบนเส้นทางมากกว่าก่อนการลบดังนั้นคุณต้องตรวจสอบต่อไปว่าการเปลี่ยนแปลงจำนวนโหนดสีดำบนเส้นทางที่ผ่าน P ส่งผลกระทบต่อคุณสมบัติของต้นไม้สีแดงและสีดำ
1.2.2 พี่ชายโหนด B ของโหนด D มีลูกไม่ไม่มี NIL
เด็กจะต้องเป็นสีแดงมิฉะนั้นจำนวนโหนดสีดำบนเส้นทางจากโหนดแม่ของ D ไปยังโหนดใบแต่ละใบจะแตกต่างกันไป (การละเมิด 5)
หากเด็กคนนี้เป็นเด็กที่เหมาะสมให้วาดลูกที่ถูกต้องของ B เป็นสีดำให้วาด b เป็นสีดั้งเดิมของโหนดแม่ของมันวาด p เป็นสีดำแล้วหมุน p ด้วยซ้ายหนึ่ง
หากเด็กคนนี้เป็นเด็กซ้ายให้วาดลูกซ้ายของ B เป็นสีดำ b เป็นสีแดงและจากนั้นหมุน b ขวาหนึ่งครั้งปัญหาจะถูกเปลี่ยนเป็นสถานการณ์ของเด็กที่เหมาะสม
1.2.3 เด็กทั้งสองของโหนด B ที่ถูกลบ
ถ้า B เป็นสีแดงลูกสองคนของ B จะต้องเป็นสีดำ วาด B เป็นสีดำลูกซ้ายของ B เป็นสีแดงจากนั้นทำการหมุนซ้ายของ P.
ถ้า B เป็นสีดำลูกสองคนของ B จะต้องเป็นสีแดง วาดโหนดแม่ของ B เป็นสีดำลูกขวาของ B เป็นสีดำสีดั้งเดิมของ B เป็นโหนดหลัก P จากนั้นหมุน p ด้วยซ้ายหนึ่ง
2 เด็กทั้งสองคนที่มีการลบโหนด D ไม่ได้เป็นศูนย์
ตามแผนการค้นหาไบนารีเพื่อลบโหนดให้ค้นหาโหนดผู้สืบทอด S ของ D, แลกเปลี่ยนเนื้อหาของ D และ S (สียังคงไม่เปลี่ยนแปลง) และโหนดที่ถูกลบจะกลายเป็น S ถ้า S มีโหนดที่ไม่ได้อยู่ ปัญหาเปลี่ยนไปสู่สถานการณ์ที่เด็กทั้งสองของโหนดที่ถูกลบ D เป็นศูนย์
3 โหนดที่ถูกลบ d มีลูกไม่ไม่มี
เด็กคนนี้จะต้องเป็นโหนดสีแดงมิฉะนั้นจำนวนโหนดสีดำบนเส้นทางจาก D ไปยังโหนด NIL แต่ละโหนดจะแตกต่างกัน (การละเมิด 5)
เนื้อหาของ D และ C มีการแลกเปลี่ยน (สียังคงเหมือนเดิม) โหนดที่ถูกลบจะกลายเป็น C และปัญหาจะเปลี่ยนเป็นสถานการณ์ที่เด็กทั้งสองของโหนดที่ถูกลบ D เป็นศูนย์
Traversal of Binary Trees
มีสามประเภทของการสำรวจในต้นไม้ไบนารี: การเดินทางล่วงหน้าล่วงหน้า, การสำรวจกลางและการเดินทางหลังการเดินทาง มีการใช้งานแบบสำรวจสองประเภท: การเรียกซ้ำและการทำซ้ำ ในบทความนี้เราจะหารือเกี่ยวกับวิธีการใช้รหัสที่สง่างามมากขึ้นเพื่อใช้การสำรวจต้นไม้ไบนารี
ก่อนอื่นฉันจะกำหนดโหนดของต้นไม้ไบนารี:
TREENODE ชั้นเรียนสาธารณะ {int val; treenode ซ้าย; Treenode ขวา; สาธารณะ treenode (int x) {val = x; -
1. การเดินทางล่วงหน้า
พูดง่ายๆคือการสั่งการเดินทางล่วงหน้าคือการเข้าถึงโหนดพาเรนต์ก่อนจากนั้นเข้าถึงเด็กซ้ายและในที่สุดก็เข้าถึงเด็กที่เหมาะสมนั่นคือการสำรวจตามลำดับของพาเรนต์ซ้ายและขวา
การใช้งานแบบเรียกซ้ำนั้นง่ายมากรหัสมีดังนี้:
โซลูชันคลาสสาธารณะ {รายการ <จำนวนเต็ม> result = new ArrayList <integer> (); รายการสาธารณะ <integer> preordertraversal (treenode root) {dfs (root); ผลการกลับมา; } โมฆะส่วนตัว DFS (ทรีโนดรูท) {if (root == null) {return; } result.add (root.val); dfs (root.left); dfs (root.right); - การใช้งานซ้ำต้องใช้สแต็กเพื่อจัดเก็บโหนดที่เหมาะสมที่ไม่สามารถเข้าถึงได้ รหัสมีดังนี้:
โซลูชันคลาสสาธารณะ {รายการสาธารณะ <integer> preordertraversal (treenode root) {list <integer> result = new ArrayList <integer> (); if (root == null) {ส่งคืนผลลัพธ์; } สแต็ก <Treenode> stack = ใหม่สแต็ก <Treenode> (); stack.push (รูท); ในขณะที่ (! stack.isempty ()) {treenode curr = stack.pop (); result.add (curr.val); if (curr.right! = null) {stack.push (curr.right); } if (curr.left! = null) {stack.push (curr.left); }} ผลการส่งคืน; -
2. Inorder Traversal
พูดง่ายๆคือการเดินทางกลางลำดับกลางคือการเข้าถึงเด็กซ้ายก่อนจากนั้นเข้าถึงโหนดพาเรนต์และในที่สุดก็เข้าถึงลูกที่เหมาะสมนั่นคือการเดินทางตามลำดับของซ้ายผู้ปกครองและขวา
รหัสซ้ำนั้นง่ายกว่าดังที่แสดงด้านล่าง:
โซลูชันคลาสสาธารณะ {รายการสาธารณะ <จำนวนเต็ม> InorderTraversal (ทรีโนดรูท) {รายการ <จำนวนเต็ม> result = new ArrayList <integer> (); ซ้ำ (รูทผลลัพธ์); ผลการกลับมา; } โมฆะส่วนตัว Recurse (ทรีโนดรูท, รายการ <จำนวนเต็ม> ผลลัพธ์) {ถ้า (root == null) ส่งคืน; ซ้ำ (root.left ผลลัพธ์); result.add (root.val); ซ้ำ (root.right, ผลลัพธ์); - วิธีการเขียนข้างต้นนั้นแตกต่างจากรหัสซ้ำของการเดินทางล่วงหน้า เราใช้ตัวแปรสมาชิกเพื่อจัดเก็บผลลัพธ์ของการสำรวจในการเดินทางล่วงหน้าและที่นี่เราใช้พารามิเตอร์วิธีการเพื่อบันทึกผลลัพธ์ของการเดินทาง วิธีการเขียนทั้งสองใช้งานได้ดีใช้สิ่งที่คุณชอบ
การใช้งานซ้ำ ๆ ของการเดินทางระยะกลางไม่ง่ายเหมือนการเดินทางล่วงหน้า แม้ว่ามันจะต้องใช้สแต็ก แต่เงื่อนไขสำหรับการยกเลิกซ้ำก็แตกต่างกัน ลองนึกภาพว่าสำหรับต้นไม้ไบนารีโหนดที่เราเข้าถึงก่อนคือโหนดซ้ายสุด แน่นอนว่าเราสามารถไปถึงโหนดซ้ายสุดผ่านไปได้สักพัก แต่เมื่อเราถอยกลับเราจะรู้ได้อย่างไรว่าเด็กที่เหลือของโหนดได้รับการเข้าถึงหรือไม่? เราใช้ตัวแปร CURR เพื่อบันทึกโหนดที่เข้าถึงได้ในปัจจุบัน เมื่อเราเข้าถึงโหนดที่ถูกต้องของทรีย่อยเราควรถอยกลับไปที่โหนดพาเรนต์ของทรีย่อย ในเวลานี้ Curr เป็นโมฆะดังนั้นเราจึงสามารถใช้สิ่งนี้เพื่อแยกแยะว่ามีการเข้าถึงทรีย่อยด้านซ้ายของโหนดหรือไม่ รหัสมีดังนี้:
โซลูชันคลาสสาธารณะ {รายการสาธารณะ <จำนวนเต็ม> InorderTraversal (ทรีโนดรูท) {รายการ <จำนวนเต็ม> result = new ArrayList <integer> (); สแต็ค <Treenode> stack = ใหม่สแต็ก <Treenode> (); treenode curr = root; ในขณะที่ (curr! = null ||! stack.isempty ()) {ในขณะที่ (curr! = null) {stack.push (curr); curr = curr.left; } curr = stack.pop (); result.add (curr.val); curr = curr.right; } ผลตอบแทนผลลัพธ์; -
3. โพสต์ออร์เดอร์ทราเวิร์ด
พูดง่ายๆคือการเดินทางหลังการสั่งซื้อคือการเข้าถึงเด็กซ้ายก่อนเข้าถึงเด็กที่ถูกต้องและในที่สุดก็เข้าถึงโหนดพาเรนต์นั่นคือการเดินทางข้ามตามลำดับทางซ้ายขวาและผู้ปกครอง
โดยการเลียนแบบการเดินทางกลางลำดับกลางคุณสามารถเขียนการใช้งานซ้ำของการเดินทางหลังการสั่งซื้อ:
โซลูชันระดับสาธารณะ {รายการสาธารณะ <จำนวนเต็ม> postorderTraversal (treenode root) {list <integer> result = new ArrayList <integer> (); ซ้ำ (รูทผลลัพธ์); ผลการกลับมา; } โมฆะส่วนตัว Recurse (ทรีโนดรูท, รายการ <จำนวนเต็ม> ผลลัพธ์) {ถ้า (root == null) ส่งคืน; ซ้ำ (root.left ผลลัพธ์); ซ้ำ (root.right, ผลลัพธ์); result.add (root.val); - การทำซ้ำของการเดินทางหลังการสั่งซื้อยังต้องมีการระบุตัวตนเพื่อแยกแยะว่ามีการเข้าถึงเด็กซ้ายและขวาของโหนดหรือไม่ หากไม่เป็นเช่นนั้นเด็กซ้ายและขวาจะถูกเข้าถึงในทางกลับกัน หากมีการเข้าถึงโหนดจะเข้าถึงได้ ด้วยเหตุนี้เราจึงใช้ตัวแปรล่วงหน้าเพื่อแสดงโหนดที่เราไปเยี่ยมชม หากโหนดที่เราเยี่ยมชมคือลูกซ้ายหรือขวาของโหนดปัจจุบันหมายความว่าเด็กซ้ายและขวาของโหนดปัจจุบันได้รับการเข้าถึงและจากนั้นเราสามารถเข้าถึงโหนดได้ มิฉะนั้นเราต้องป้อนเด็กซ้ายและขวาเพื่อเข้าถึงมัน รหัสมีดังนี้:
โซลูชันคลาสสาธารณะ {รายการสาธารณะ <จำนวนเต็ม> postorderTraversal (treenode root) {list <integer> result = new LinkedList <integer> (); สแต็ค <Treenode> stack = ใหม่สแต็ก <Treenode> (); if (root! = null) stack.push (root); treenode pre = root; ในขณะที่ (! stack.isempty ()) {treenode curr = stack.peek (); if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) {result.add (curr.val); stack.pop (); pre = curr; } else {ถ้า (curr.right! = null) stack.push (curr.right); if (curr.left! = null) stack.push (curr.left); }} ผลการส่งคืน; - มีการใช้งานการทำซ้ำของการเดินทางแบบโพสต์ตามลำดับ เรารู้ว่าคำสั่งของการเดินทางล่วงหน้าที่สั่งซื้อล่วงหน้าคือผู้ปกครองซ้ายและขวาในขณะที่คำสั่งของการข้ามลำดับการเดินทางถูกทิ้งไว้ทางซ้ายขวาและผู้ปกครอง ดังนั้นหากเราปรับเปลี่ยนการเดินทางก่อนการสั่งซื้อล่วงหน้าเล็กน้อยและเปลี่ยนเป็นลำดับของผู้ปกครองขวาและซ้ายแล้วมันก็เป็นสิ่งที่ตรงกันข้ามกับคำสั่งของการเดินทางข้ามคำสั่ง หลังจากเข้าถึงตามลำดับนี้เราสามารถกลับผลลัพธ์การเข้าถึงในที่สุด การดำเนินการวนซ้ำของการเดินทางก่อนการสั่งซื้อล่วงหน้านั้นค่อนข้างง่าย ตามวิธีการเขียนข้างต้นเราสามารถนำไปใช้ดังนี้:
โซลูชันคลาสสาธารณะ {รายการสาธารณะ <จำนวนเต็ม> postorderTraversal (treenode root) {list <integer> result = new LinkedList <integer> (); สแต็ค <Treenode> stack = ใหม่สแต็ก <Treenode> (); if (root! = null) stack.push (root); ในขณะที่ (! stack.isempty ()) {treenode curr = stack.pop (); result.add (curr.val); if (curr.left! = null) stack.push (curr.left); if (curr.right! = null) stack.push (curr.right); } collections.reverse (ผลลัพธ์); ผลการกลับมา; -
4. สรุป
การใช้งานซ้ำของการเดินทางทั้งสามนั้นเป็นเรื่องง่าย เป็นการดีที่สุดที่จะเขียนการใช้งานซ้ำของการเดินทางล่วงหน้าและจำเป็นต้องใช้สแต็กเพียงครั้งเดียวเท่านั้น การเดินทางระยะกลางเป็นเรื่องยากที่สุด นอกเหนือจากการพิจารณาว่าสแต็กว่างเปล่าเงื่อนไขการวนซ้ำยังจำเป็นต้องพิจารณาว่าโหนดปัจจุบันนั้นว่างเปล่าหรือไม่เพื่อระบุว่าทรีย่อยด้านซ้ายนั้นถูกสำรวจหรือไม่ หากการทำซ้ำของการเดินทางข้ามครั้งต่อไปจะถูกแปลงเป็นการทำซ้ำก่อนการเดินทางก่อนการทำซ้ำมันจะง่ายขึ้นมาก มิฉะนั้นก็จำเป็นที่จะต้องบันทึกโหนดการเข้าถึงก่อนหน้าเพื่อระบุว่ามีการเข้าถึงทรีทรีด้านซ้ายและขวาของโหนดปัจจุบันหรือไม่