แผนผังการค้นหาแบบไบนารี (BST) พร้อมตัวอย่าง

แผนผังการค้นหาแบบไบนารีคืออะไร?

Binary search tree เป็นอัลกอริทึมขั้นสูงที่ใช้ในการวิเคราะห์โหนด สาขาซ้ายและขวาของโหนด ซึ่งจำลองเป็นโครงสร้างแบบต้นไม้และส่งคืนค่า BST ได้รับการออกแบบโดยใช้สถาปัตยกรรมของอัลกอริทึมการค้นหาแบบไบนารีพื้นฐาน ดังนั้นจึงทำให้สามารถค้นหา แทรก และลบโหนดได้เร็วขึ้น ทำให้โปรแกรมทำงานได้อย่างรวดเร็วและแม่นยำยิ่งขึ้น

คุณสมบัติของแผนผังการค้นหาแบบไบนารี

BST ประกอบด้วยโหนดหลายโหนดและประกอบด้วยแอตทริบิวต์ดังต่อไปนี้:

  • โหนดของต้นไม้แสดงอยู่ในความสัมพันธ์ระหว่างพ่อแม่และลูก
  • แต่ละโหนดหลักสามารถมีโหนดลูกเป็นศูนย์ หรือโหนดย่อยหรือทรีย่อยได้สูงสุดสองโหนดทางด้านซ้ายและด้านขวา
  • แผนผังย่อยทุกต้นหรือที่เรียกว่าแผนผังการค้นหาแบบไบนารี มีสาขาย่อยทางด้านขวาและด้านซ้ายของตัวเอง
  • โหนดทั้งหมดเชื่อมโยงกับคู่คีย์-ค่า
  • คีย์ของโหนดที่อยู่บนทรีย่อยด้านซ้ายจะเล็กกว่าคีย์ของโหนดแม่
  • ในทำนองเดียวกัน คีย์ของโหนดทรีย่อยด้านซ้ายมีค่าน้อยกว่าคีย์ของโหนดแม่

คุณสมบัติของแผนผังการค้นหาแบบไบนารี

  1. มีโหนดหลักหรือระดับพาเรนต์ 11 ข้างใต้มีโหนด/สาขาด้านซ้ายและขวาที่มีค่าคีย์ของตัวเอง
  2. แผนผังย่อยที่ถูกต้องมีค่าคีย์มากกว่าโหนดหลัก
  3. ทรีย่อยด้านซ้ายมีค่ามากกว่าโหนดหลัก

เหตุใดเราจึงต้องมี Binary Search Tree?

  • ปัจจัยหลักสองประการที่ทำให้แผนผังการค้นหาแบบไบนารีเป็นวิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับปัญหาในโลกแห่งความเป็นจริงคือความเร็วและความแม่นยำ
  • เนื่องจากการค้นหาแบบไบนารี่อยู่ในรูปแบบที่เหมือนสาขาซึ่งมีความสัมพันธ์ระหว่างพ่อแม่และลูก อัลกอริธึมจึงรู้ว่าจะต้องค้นหาองค์ประกอบในตำแหน่งใดของแผนผังต้นไม้ ซึ่งจะช่วยลดจำนวนการเปรียบเทียบคีย์-ค่าที่โปรแกรมต้องทำเพื่อค้นหาองค์ประกอบที่ต้องการ
  • นอกจากนี้ ในกรณีที่องค์ประกอบที่จะค้นหามากกว่าหรือน้อยกว่าโหนดหลัก โหนดจะรู้ว่าจะต้องค้นหาด้านแผนผังใด เหตุผลก็คือ แผนผังย่อยด้านซ้ายจะน้อยกว่าโหนดหลักเสมอ และแผนผังย่อยด้านขวาจะมีค่าเท่ากับหรือมากกว่าโหนดหลักเสมอ
  • BST มักใช้ในการค้นหาที่ซับซ้อน ตรรกะของเกมที่แข็งแกร่ง กิจกรรมการเติมคำอัตโนมัติ และกราฟิก
  • อัลกอริทึมรองรับการดำเนินการต่างๆ เช่น การค้นหา การแทรก และการลบอย่างมีประสิทธิภาพ

ประเภทของต้นไม้ไบนารี

ต้นไม้ไบนารีสามประเภทคือ:

  • แผนผังไบนารีที่สมบูรณ์: ทุกระดับในแผนผังเต็มไปด้วยข้อยกเว้นที่เป็นไปได้ของระดับสุดท้าย ในทำนองเดียวกัน โหนดทั้งหมดจะเต็มโดยหันไปทางซ้ายสุด
  • Full binary tree: โหนดทั้งหมดมีโหนดย่อย 2 โหนด ยกเว้นลีฟ
  • Balanced หรือ Perfect binary tree: ในแผนผัง โหนดทั้งหมดมีลูกสองคน นอกจากนี้ยังมีระดับเดียวกันของแต่ละโหนดย่อย

เรียนรู้เพิ่มเติมเกี่ยวกับ ต้นไม้ไบนารีในโครงสร้างข้อมูล ถ้าคุณสนใจ.

แผนผังการค้นหาแบบไบนารีทำงานอย่างไร

ต้นไม้จะมีโหนดรากและโหนดย่อยอื่นๆ เสมอ ไม่ว่าจะอยู่ทางซ้ายหรือขวา อัลกอริทึมจะดำเนินการทั้งหมดโดยเปรียบเทียบค่ากับรากและโหนดย่อยอื่นๆ ในซับทรีทางซ้ายหรือขวาตามลำดับ

ขึ้นอยู่กับองค์ประกอบที่จะแทรก ค้นหา หรือลบ หลังจากการเปรียบเทียบ อัลกอริธึมสามารถปล่อยแผนผังย่อยทางซ้ายหรือขวาของโหนดรูทได้อย่างง่ายดาย

BST เสนอการดำเนินการสามประเภทหลักต่อไปนี้สำหรับการใช้งานของคุณ:

  • ค้นหา: ค้นหาองค์ประกอบจากแผนผังไบนารี
  • แทรก: เพิ่มองค์ประกอบให้กับต้นไม้ไบนารี
  • ลบ: ลบองค์ประกอบออกจากแผนผังไบนารี

การดำเนินการแต่ละอย่างมีโครงสร้างและวิธีการดำเนินการ/วิเคราะห์ของตัวเอง แต่สิ่งที่ซับซ้อนที่สุดคือการดำเนินการลบ

ค้นหา Operaการ

เริ่มต้นการวิเคราะห์ทรีที่โหนดรูทเสมอ จากนั้นย้ายต่อไปไปยังทรีย่อยทางขวาหรือซ้ายของโหนดรูท ขึ้นอยู่กับองค์ประกอบที่จะระบุตำแหน่งว่าน้อยกว่าหรือมากกว่ารูท

ค้นหา Operaการ

  1. องค์ประกอบที่ต้องการค้นหาคือ 10
  2. เปรียบเทียบองค์ประกอบกับโหนดรูท 12, 10 < 12 ดังนั้นคุณจึงย้ายไปที่แผนผังย่อยด้านซ้าย ไม่จำเป็นต้องวิเคราะห์ทรีย่อยที่ถูกต้อง
  3. ตอนนี้เปรียบเทียบ 10 กับโหนด 7, 10 > 7 ดังนั้นให้ย้ายไปที่แผนผังย่อยด้านขวา
  4. จากนั้นเปรียบเทียบ 10 กับโหนดถัดไปซึ่งก็คือ 9, 10 > 9 ดูในแผนผังย่อยด้านขวา
  5. 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การ

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

สิ่งที่ใส่เข้าไป Operaการ

  1. มีรายการองค์ประกอบ 6 รายการที่ต้องแทรกใน BST ตามลำดับจากซ้ายไปขวา
  2. แทรก 12 เป็นโหนดรูทและเปรียบเทียบค่าถัดไป 7 และ 9 สำหรับการแทรกลงในแผนผังย่อยด้านขวาและซ้าย
  3. เปรียบเทียบค่าที่เหลือ 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: คุณต้องลบโหนดที่มีลูกสองคนและแทนที่ด้วยค่าที่ใหญ่ที่สุดบนแผนผังย่อยด้านขวาของโหนดที่ถูกลบ

ลบ Operations

  1. นี่เป็นกรณีแรกของการลบที่คุณลบโหนดที่ไม่มีลูก ดังที่คุณเห็นในแผนภาพว่า 19, 10 และ 5 ไม่มีลูก แต่เราจะลบ 19.
  2. ลบค่า 19 และลบลิงก์ออกจากโหนด
  3. ดูโครงสร้างใหม่ของ BST ที่ไม่มี 19

ลบ Operations

  1. นี่เป็นกรณีที่สองของการลบ โดยที่คุณลบโหนดที่มี 1 ลูก ดังที่คุณเห็นในแผนภาพว่า 9 มีลูกหนึ่งลูก
  2. ลบโหนด 9 และแทนที่ด้วยโหนดย่อย 10 และเพิ่มลิงก์จาก 7 ถึง 10
  3. ดูโครงสร้างใหม่ของ BST ที่ไม่มี 9

ลบ Operations

  1. ที่นี่คุณจะลบโหนด 12 ที่มีลูกสองคน
  2. การลบโหนดจะเกิดขึ้นตามกฎตามลำดับก่อนหน้า ซึ่งหมายความว่าองค์ประกอบที่ใหญ่ที่สุดบนแผนผังย่อยด้านซ้ายจำนวน 12 จะถูกแทนที่
  3. ลบโหนด 12 และแทนที่ด้วย 10 เนื่องจากเป็นค่าที่ใหญ่ที่สุดในแผนผังย่อยด้านซ้าย
  4. ดูโครงสร้างใหม่ของ BST หลังจากลบ 12

ลบ Operations

  1. 1 ลบโหนด 12 ที่มีลูกสองคน
  2. 2 การลบโหนดจะเกิดขึ้นตามกฎ In Order Successor ซึ่งหมายความว่าองค์ประกอบที่ใหญ่ที่สุดบนแผนผังย่อยด้านขวาของ 12 จะเข้ามาแทนที่
  3. 3 ลบโหนด 12 และแทนที่ด้วย 19 เนื่องจากเป็นค่าที่ใหญ่ที่สุดในแผนผังย่อยด้านขวา
  4. 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 เป็นอัลกอริทึมระดับสูงที่ดำเนินการต่างๆ โดยอิงตามการเปรียบเทียบค่าโหนดกับโหนดราก
  • จุดใด ๆ ในลำดับชั้นหลักและรองแสดงถึงโหนด อย่างน้อยหนึ่งพาเรนต์หรือโหนดรูทยังคงอยู่ตลอดเวลา
  • มีแผนผังย่อยด้านซ้ายและแผนผังย่อยด้านขวา ทรีย่อยด้านซ้ายมีค่าที่น้อยกว่าโหนดรูท อย่างไรก็ตาม ทรีย่อยที่ถูกต้องมีค่าที่มากกว่าโหนดรูท
  • แต่ละโหนดสามารถมีลูกเป็นศูนย์ หนึ่ง หรือสองคนก็ได้
  • ต้นไม้ค้นหาแบบไบนารีช่วยอำนวยความสะดวกให้กับการดำเนินการหลัก เช่น การค้นหา การแทรก และการลบ
  • การลบข้อมูลเป็นเรื่องที่ซับซ้อนที่สุดหากมีหลายกรณี เช่น โหนดไม่มีโหนดย่อย โหนดที่มีโหนดย่อยหนึ่งโหนด และโหนดที่มีโหนดย่อยสองโหนด
  • อัลกอริธึมถูกนำมาใช้ในโซลูชันในโลกแห่งความเป็นจริง เช่น เกม ข้อมูลเติมข้อความอัตโนมัติ และกราฟิก