แผนผังการค้นหาแบบไบนารี (BST) พร้อมตัวอย่าง
แผนผังการค้นหาแบบไบนารีคืออะไร?
Binary search tree เป็นอัลกอริทึมขั้นสูงที่ใช้ในการวิเคราะห์โหนด สาขาซ้ายและขวาของโหนด ซึ่งจำลองเป็นโครงสร้างแบบต้นไม้และส่งคืนค่า BST ได้รับการออกแบบโดยใช้สถาปัตยกรรมของอัลกอริทึมการค้นหาแบบไบนารีพื้นฐาน ดังนั้นจึงทำให้สามารถค้นหา แทรก และลบโหนดได้เร็วขึ้น ทำให้โปรแกรมทำงานได้อย่างรวดเร็วและแม่นยำยิ่งขึ้น
คุณสมบัติของแผนผังการค้นหาแบบไบนารี
BST ประกอบด้วยโหนดหลายโหนดและประกอบด้วยแอตทริบิวต์ดังต่อไปนี้:
- โหนดของต้นไม้แสดงอยู่ในความสัมพันธ์ระหว่างพ่อแม่และลูก
- แต่ละโหนดหลักสามารถมีโหนดลูกเป็นศูนย์ หรือโหนดย่อยหรือทรีย่อยได้สูงสุดสองโหนดทางด้านซ้ายและด้านขวา
- แผนผังย่อยทุกต้นหรือที่เรียกว่าแผนผังการค้นหาแบบไบนารี มีสาขาย่อยทางด้านขวาและด้านซ้ายของตัวเอง
- โหนดทั้งหมดเชื่อมโยงกับคู่คีย์-ค่า
- คีย์ของโหนดที่อยู่บนทรีย่อยด้านซ้ายจะเล็กกว่าคีย์ของโหนดแม่
- ในทำนองเดียวกัน คีย์ของโหนดทรีย่อยด้านซ้ายมีค่าน้อยกว่าคีย์ของโหนดแม่
- มีโหนดหลักหรือระดับพาเรนต์ 11 ข้างใต้มีโหนด/สาขาด้านซ้ายและขวาที่มีค่าคีย์ของตัวเอง
- แผนผังย่อยที่ถูกต้องมีค่าคีย์มากกว่าโหนดหลัก
- ทรีย่อยด้านซ้ายมีค่ามากกว่าโหนดหลัก
เหตุใดเราจึงต้องมี Binary Search Tree?
- ปัจจัยหลักสองประการที่ทำให้แผนผังการค้นหาแบบไบนารีเป็นวิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับปัญหาในโลกแห่งความเป็นจริงคือความเร็วและความแม่นยำ
- เนื่องจากการค้นหาแบบไบนารี่อยู่ในรูปแบบที่เหมือนสาขาซึ่งมีความสัมพันธ์ระหว่างพ่อแม่และลูก อัลกอริธึมจึงรู้ว่าจะต้องค้นหาองค์ประกอบในตำแหน่งใดของแผนผังต้นไม้ ซึ่งจะช่วยลดจำนวนการเปรียบเทียบคีย์-ค่าที่โปรแกรมต้องทำเพื่อค้นหาองค์ประกอบที่ต้องการ
- นอกจากนี้ ในกรณีที่องค์ประกอบที่จะค้นหามากกว่าหรือน้อยกว่าโหนดหลัก โหนดจะรู้ว่าจะต้องค้นหาด้านแผนผังใด เหตุผลก็คือ แผนผังย่อยด้านซ้ายจะน้อยกว่าโหนดหลักเสมอ และแผนผังย่อยด้านขวาจะมีค่าเท่ากับหรือมากกว่าโหนดหลักเสมอ
- BST มักใช้ในการค้นหาที่ซับซ้อน ตรรกะของเกมที่แข็งแกร่ง กิจกรรมการเติมคำอัตโนมัติ และกราฟิก
- อัลกอริทึมรองรับการดำเนินการต่างๆ เช่น การค้นหา การแทรก และการลบอย่างมีประสิทธิภาพ
ประเภทของต้นไม้ไบนารี
ต้นไม้ไบนารีสามประเภทคือ:
- แผนผังไบนารีที่สมบูรณ์: ทุกระดับในแผนผังเต็มไปด้วยข้อยกเว้นที่เป็นไปได้ของระดับสุดท้าย ในทำนองเดียวกัน โหนดทั้งหมดจะเต็มโดยหันไปทางซ้ายสุด
- Full binary tree: โหนดทั้งหมดมีโหนดย่อย 2 โหนด ยกเว้นลีฟ
- Balanced หรือ Perfect binary tree: ในแผนผัง โหนดทั้งหมดมีลูกสองคน นอกจากนี้ยังมีระดับเดียวกันของแต่ละโหนดย่อย
เรียนรู้เพิ่มเติมเกี่ยวกับ ต้นไม้ไบนารีในโครงสร้างข้อมูล ถ้าคุณสนใจ.
แผนผังการค้นหาแบบไบนารีทำงานอย่างไร
ต้นไม้จะมีโหนดรากและโหนดย่อยอื่นๆ เสมอ ไม่ว่าจะอยู่ทางซ้ายหรือขวา อัลกอริทึมจะดำเนินการทั้งหมดโดยเปรียบเทียบค่ากับรากและโหนดย่อยอื่นๆ ในซับทรีทางซ้ายหรือขวาตามลำดับ
ขึ้นอยู่กับองค์ประกอบที่จะแทรก ค้นหา หรือลบ หลังจากการเปรียบเทียบ อัลกอริธึมสามารถปล่อยแผนผังย่อยทางซ้ายหรือขวาของโหนดรูทได้อย่างง่ายดาย
BST เสนอการดำเนินการสามประเภทหลักต่อไปนี้สำหรับการใช้งานของคุณ:
- ค้นหา: ค้นหาองค์ประกอบจากแผนผังไบนารี
- แทรก: เพิ่มองค์ประกอบให้กับต้นไม้ไบนารี
- ลบ: ลบองค์ประกอบออกจากแผนผังไบนารี
การดำเนินการแต่ละอย่างมีโครงสร้างและวิธีการดำเนินการ/วิเคราะห์ของตัวเอง แต่สิ่งที่ซับซ้อนที่สุดคือการดำเนินการลบ
ค้นหา Operaการ
เริ่มต้นการวิเคราะห์ทรีที่โหนดรูทเสมอ จากนั้นย้ายต่อไปไปยังทรีย่อยทางขวาหรือซ้ายของโหนดรูท ขึ้นอยู่กับองค์ประกอบที่จะระบุตำแหน่งว่าน้อยกว่าหรือมากกว่ารูท
- องค์ประกอบที่ต้องการค้นหาคือ 10
- เปรียบเทียบองค์ประกอบกับโหนดรูท 12, 10 < 12 ดังนั้นคุณจึงย้ายไปที่แผนผังย่อยด้านซ้าย ไม่จำเป็นต้องวิเคราะห์ทรีย่อยที่ถูกต้อง
- ตอนนี้เปรียบเทียบ 10 กับโหนด 7, 10 > 7 ดังนั้นให้ย้ายไปที่แผนผังย่อยด้านขวา
- จากนั้นเปรียบเทียบ 10 กับโหนดถัดไปซึ่งก็คือ 9, 10 > 9 ดูในแผนผังย่อยด้านขวา
- 10 ตรงกับค่าในโหนด 10 = 10 ส่งคืนค่าให้กับผู้ใช้
รหัสหลอกสำหรับการค้นหาใน BST
search(element, root) if !root return -1 if root.value == element return 1 if root.value < element search(element, root.right) else search(element, root.left)
สิ่งที่ใส่เข้าไป Operaการ
นี่เป็นการดำเนินการที่ตรงไปตรงมามาก ขั้นแรก ให้แทรกโหนดราก จากนั้นเปรียบเทียบค่าถัดไปกับโหนดราก หากค่ามากกว่าโหนดราก ค่าดังกล่าวจะถูกเพิ่มลงในซับทรีด้านขวา และหากค่าน้อยกว่าโหนดราก ค่าดังกล่าวจะถูกเพิ่มลงในซับทรีด้านซ้าย
- มีรายการองค์ประกอบ 6 รายการที่ต้องแทรกใน BST ตามลำดับจากซ้ายไปขวา
- แทรก 12 เป็นโหนดรูทและเปรียบเทียบค่าถัดไป 7 และ 9 สำหรับการแทรกลงในแผนผังย่อยด้านขวาและซ้าย
- เปรียบเทียบค่าที่เหลือ 19, 5 และ 10 กับโหนดรูท 12 และวางไว้ตามลำดับ 19 > 12 วางเป็นลูกด้านขวาของ 12, 5 < 12 & 5 < 7 ดังนั้นให้วางไว้เป็นลูกซ้ายของ 7 ทีนี้เปรียบเทียบ 10, 10 คือ < 12 & 10 คือ > 7 & 10 คือ > 9, อันดับที่ 10 เป็นแผนผังย่อยทางขวาของ 9
Pseudocode สำหรับการแทรกโหนดใน BST
insert (element, root) Node x = root Node y = NULL while x: y = x if x.value < element.value x = x.right else x = x.left if y.value < element y.right = element else y.left = element
ลบ Operations
สำหรับการลบโหนดจาก BST มีบางกรณี เช่น การลบรูทหรือการลบโหนดปลายสุด นอกจากนี้ หลังจากลบรูทแล้ว เราต้องคิดถึงโหนดรูทด้วย
สมมติว่าเราต้องการลบโหนดย่อย เราสามารถลบได้เลย แต่ถ้าเราต้องการลบรูท เราจะต้องแทนที่ค่าของรูทด้วยโหนดอื่น มาดูตัวอย่างต่อไปนี้:
- กรณีที่ 1- โหนดที่มีลูกเป็นศูนย์: นี่เป็นสถานการณ์ที่ง่ายที่สุด คุณเพียงแค่ต้องลบโหนดที่ไม่มีลูกเพิ่มเติมทางด้านขวาหรือซ้าย
- กรณีที่ 2 – โหนดที่มีลูกหนึ่งตัว: เมื่อคุณลบโหนดแล้ว เพียงเชื่อมต่อโหนดลูกกับโหนดหลักของค่าที่ถูกลบ
- กรณีที่ 3 โหนดที่มีลูกสองคน: นี่เป็นสถานการณ์ที่ยากที่สุดและต้องปฏิบัติตามกฎ XNUMX ข้อต่อไปนี้
- 3a – เรียงตามลำดับ: คุณต้องลบโหนดที่มีลูกสองคน และแทนที่ด้วยค่าที่ใหญ่ที่สุดบนแผนผังย่อยด้านซ้ายของโหนดที่ถูกลบ
- 3b – In Order Successor: คุณต้องลบโหนดที่มีลูกสองคนและแทนที่ด้วยค่าที่ใหญ่ที่สุดบนแผนผังย่อยด้านขวาของโหนดที่ถูกลบ
- นี่เป็นกรณีแรกของการลบที่คุณลบโหนดที่ไม่มีลูก ดังที่คุณเห็นในแผนภาพว่า 19, 10 และ 5 ไม่มีลูก แต่เราจะลบ 19.
- ลบค่า 19 และลบลิงก์ออกจากโหนด
- ดูโครงสร้างใหม่ของ BST ที่ไม่มี 19
- นี่เป็นกรณีที่สองของการลบ โดยที่คุณลบโหนดที่มี 1 ลูก ดังที่คุณเห็นในแผนภาพว่า 9 มีลูกหนึ่งลูก
- ลบโหนด 9 และแทนที่ด้วยโหนดย่อย 10 และเพิ่มลิงก์จาก 7 ถึง 10
- ดูโครงสร้างใหม่ของ BST ที่ไม่มี 9
- ที่นี่คุณจะลบโหนด 12 ที่มีลูกสองคน
- การลบโหนดจะเกิดขึ้นตามกฎตามลำดับก่อนหน้า ซึ่งหมายความว่าองค์ประกอบที่ใหญ่ที่สุดบนแผนผังย่อยด้านซ้ายจำนวน 12 จะถูกแทนที่
- ลบโหนด 12 และแทนที่ด้วย 10 เนื่องจากเป็นค่าที่ใหญ่ที่สุดในแผนผังย่อยด้านซ้าย
- ดูโครงสร้างใหม่ของ BST หลังจากลบ 12
- 1 ลบโหนด 12 ที่มีลูกสองคน
- 2 การลบโหนดจะเกิดขึ้นตามกฎ In Order Successor ซึ่งหมายความว่าองค์ประกอบที่ใหญ่ที่สุดบนแผนผังย่อยด้านขวาของ 12 จะเข้ามาแทนที่
- 3 ลบโหนด 12 และแทนที่ด้วย 19 เนื่องจากเป็นค่าที่ใหญ่ที่สุดในแผนผังย่อยด้านขวา
- 4 ดูโครงสร้างใหม่ของ BST หลังจากลบ 12
รหัสหลอกสำหรับการลบโหนด
delete (value, root): Node x = root Node y = NULL # searching the node while x: y = x if x.value < value x = x.right else if x.value > value x = x.left else if value == x break # if the node is not null, then replace it with successor if y.left or y.right: newNode = GetInOrderSuccessor(y) root.value = newNode.value # After copying the value of successor to the root #we're deleting the successor free(newNode) else free(y)
เงื่อนไขสำคัญ
- แทรก: แทรกองค์ประกอบในต้นไม้/สร้างต้นไม้
- ค้นหา: ค้นหาองค์ประกอบในแผนภูมิ
- Preorder Traversal: สำรวจต้นไม้ในลักษณะสั่งจองล่วงหน้า
- Inorder Traversal: สำรวจต้นไม้ในลักษณะตามลำดับ
- Postorder Traversal: สำรวจต้นไม้ในลักษณะหลังการสั่งซื้อ
สรุป
- BST เป็นอัลกอริทึมระดับสูงที่ดำเนินการต่างๆ โดยอิงตามการเปรียบเทียบค่าโหนดกับโหนดราก
- จุดใด ๆ ในลำดับชั้นหลักและรองแสดงถึงโหนด อย่างน้อยหนึ่งพาเรนต์หรือโหนดรูทยังคงอยู่ตลอดเวลา
- มีแผนผังย่อยด้านซ้ายและแผนผังย่อยด้านขวา ทรีย่อยด้านซ้ายมีค่าที่น้อยกว่าโหนดรูท อย่างไรก็ตาม ทรีย่อยที่ถูกต้องมีค่าที่มากกว่าโหนดรูท
- แต่ละโหนดสามารถมีลูกเป็นศูนย์ หนึ่ง หรือสองคนก็ได้
- ต้นไม้ค้นหาแบบไบนารีช่วยอำนวยความสะดวกให้กับการดำเนินการหลัก เช่น การค้นหา การแทรก และการลบ
- การลบข้อมูลเป็นเรื่องที่ซับซ้อนที่สุดหากมีหลายกรณี เช่น โหนดไม่มีโหนดย่อย โหนดที่มีโหนดย่อยหนึ่งโหนด และโหนดที่มีโหนดย่อยสองโหนด
- อัลกอริธึมถูกนำมาใช้ในโซลูชันในโลกแห่งความเป็นจริง เช่น เกม ข้อมูลเติมข้อความอัตโนมัติ และกราฟิก