home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

2-3 Trees - โครงสร้างข้อมูลและอัลกอริทึมใน C++

ต้นไม้ 2-3 ต้นเป็นต้นไม้ชนิดหนึ่งในโครงสร้างข้อมูลที่ทุกโหนดของต้นไม้เป็น 2 โหนด

หรือ 3 โหนด เป็น B-Tree . ชนิดพิเศษ กับคำสั่งที่ 3.

2 โหนดในทรีคือโหนดที่มีหนึ่งส่วนข้อมูลและสองโหนดย่อย

3 โหนดในทรีคือโหนดที่มีสองส่วนข้อมูลและสามโหนดย่อย

2-3 Trees - โครงสร้างข้อมูลและอัลกอริทึมใน C++

มะเดื่อ:- ต้นไม้ 2-3 ต้น

คุณสมบัติของต้นไม้ 2-3 ต้น:-

  • ทุกโหนดภายในเป็น 2 โหนดหรือ 3 โหนด

  • โหนดที่มีหนึ่งส่วนข้อมูลสามารถเป็น 2 โหนดที่มีลูก 2 คนหรือโหนดปลายสุดที่ไม่มีลูก

  • โหนดที่มีสองส่วนข้อมูลสามารถเป็นโหนด 3 ที่มีลูก 3 เท่านั้น

  • โหนดปลายสุดทั้งหมดอยู่ในระดับเดียวกันเสมอ

  • ต้นไม้ 2-3 ต้นเป็นต้นไม้ที่มีความสูงเสมอกัน

  • การดำเนินการค้นหานั้นรวดเร็วและมีประสิทธิภาพในลำดับต้น 2-3

2 โหนด:-

  • ลูกสองคนนั่นเอง

  • ทิ้งเด็กที่มีน้ำหนักน้อยกว่า

  • เด็กที่มีน้ำหนักตัวที่เหมาะสม

  • สามารถเป็นโหนดปลายสุดได้โดยไม่มีลูก

2-3 Trees - โครงสร้างข้อมูลและอัลกอริทึมใน C++

3 โหนด:-

  • ลูกสามคนนั่นเอง

  • 2 ค่าข้อมูล

  • ลูกซ้ายที่มีน้ำหนักน้อยกว่าค่าข้อมูลด้านซ้าย

  • เด็กกลางที่มีน้ำหนักอยู่ระหว่างค่าข้อมูลทั้งสอง

  • ลูกที่ใช่ที่มีน้ำหนักมากกว่าค่าข้อมูลที่ถูกต้อง

  • ไม่สามารถเป็นโหนดปลายสุดได้

2-3 Trees - โครงสร้างข้อมูลและอัลกอริทึมใน C++

การดำเนินการใน 2-3 Tree:-

1. กำลังค้นหาต้นไม้ 2-3 ต้น

  • คล้ายกับการดำเนินการค้นหาในแผนผังการค้นหาแบบไบนารีเมื่อมีการจัดเรียงข้อมูล

  • หากต้องการค้นหา X ในต้นไม้ 2-3 ต้น

  • หากต้นไม้ว่างเปล่า → คืนค่า False

  • หากเราไปถึง root node แล้วให้คืนค่า False (ไม่พบ)

  • หาก X น้อยกว่าส่วนข้อมูลด้านซ้าย ให้ค้นหาทรีย่อยด้านซ้าย

  • หาก X มากกว่าข้อมูลด้านซ้ายและมากกว่าข้อมูลที่ถูกต้อง ให้ค้นหาทรีย่อยตรงกลาง

  • หาก X มากกว่าส่วนข้อมูลที่ถูกต้อง ให้ค้นหาทรีย่อยทางขวา

2-3 Trees - โครงสร้างข้อมูลและอัลกอริทึมใน C++

2. การแทรกโหนดในทรี 2-3

  • การแทรก X ในต้นไม้ 2-3 ต้น

  • หากต้นไม้ว่างเปล่า → เพิ่ม X เป็นรูท

  • ค้นหาตำแหน่งที่ถูกต้องของ X และเพิ่มเป็นโหนดปลายสุด

  • หากมีโหนดปลายสุดที่มีหนึ่งส่วนข้อมูล ให้เพิ่ม X ด้วย และโหนดปลายสุดจะกลายเป็น 2 - โหนด

  • หากโหนดปลายสุดมีส่วนข้อมูลสองส่วน ให้เพิ่ม X แยกโหนด 3 โหนดชั่วคราวและย้ายข้อมูลไปยังโหนดหลักตามลำดับการจัดเรียง

สร้าง 2-3 tree และเพิ่มโหนดตามลำดับ → 10, 5, 8, 15, 23, 21

2-3 Trees - โครงสร้างข้อมูลและอัลกอริทึมใน C++

3. การลบโหนดใน 2-3 tree

  • การลบ X ใน 2-3 tree.

  • หากต้นไม้ว่างเปล่าให้คืนค่าเท็จ

  • ค้นหาตำแหน่งของ X แล้วลบออก จากนั้นปรับโครงสร้างต้นไม้

  • ถ้า X เป็นส่วนหนึ่งของ 3 โหนด ให้ลบ X และปรับค่าด้านซ้ายและค่ากลาง ปรับค่าซ้ายและค่ากลางของบรรพบุรุษของโหนดด้วยหากจำเป็น

  • หาก X เป็นส่วนหนึ่งของ 2 โหนด ให้ปรับและแยกทรีในลักษณะแบบเรียกซ้ำ โดยจัดเรียงโหนดตามลำดับการจัดเรียง