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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ค้นหา Operaการ

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

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

ชื่อเล่น Code สำหรับการค้นหาใน 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การ

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

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 – โหนดที่มีลูกสองคน: นี่คือสถานการณ์ที่ยากที่สุด และมันทำงานบนพื้นฐานของกฎสองข้อต่อไปนี้:
  • 3a – ลำดับก่อนหน้า: คุณต้องลบโหนดที่มีลูกสองตัว แล้วแทนที่ด้วยค่าที่มากที่สุดในซับทรีด้านซ้ายของโหนดที่ถูกลบไป
  • 3b – ผู้สืบทอดตามลำดับ: คุณต้องลบโหนดที่มีลูกสองตัว แล้วแทนที่ด้วยค่าที่น้อยที่สุดในซับทรีด้านขวาของโหนดที่ถูกลบไป

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

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

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

1. ลบโหนด 12 ที่มีลูกสองตัว
2. การลบโหนดจะเกิดขึ้นตามกฎ In-Order Successor ซึ่งหมายความว่าองค์ประกอบที่เล็กที่สุดในซับทรีด้านขวาของ 12 จะเข้ามาแทนที่
3. ลบโหนดหมายเลข 12 และแทนที่ด้วยหมายเลข 19 เนื่องจากเป็นค่าที่เล็กที่สุดในซับทรีด้านขวา
4. ดูโครงสร้างใหม่ของ BST หลังจากลบ 12 โหนดออกไป

ชื่อเล่น Code สำหรับการลบโหนด

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, delete the successor
        free(newNode)
    else
        free(y)

เงื่อนไขสำคัญ

• แทรก: แทรกองค์ประกอบลงในโครงสร้างต้นไม้ / สร้างโครงสร้างต้นไม้
• ค้นหา: ค้นหาองค์ประกอบในโครงสร้างต้นไม้
• สั่งซื้อล่วงหน้าสำหรับบริการขนส่ง: ปีนป่ายต้นไม้ตามลำดับที่กำหนดไว้ล่วงหน้า
• การท่องแบบอินออร์เดอร์: สำรวจโครงสร้างต้นไม้ตามลำดับ
• การดำเนินการหลังการสั่งซื้อ: ท่องไปตามโครงสร้างต้นไม้ในลักษณะหลังลำดับ (post-order manner)

คำถามที่พบบ่อย