2-3 Trees (ค้นหาและแทรก) ใน C/C++?

ต้นไม้ 2-3 ต้นถูกกำหนดให้เป็นโครงสร้างข้อมูลต้นไม้ โดยที่ทุกโหนดที่มีลูก (โหนดภายใน) มีลูกสองคน (2 โหนด) เช่นเดียวกับองค์ประกอบข้อมูลหนึ่งองค์ประกอบหรือลูกสามคน (3 โหนด) รวมถึงสองข้อมูล องค์ประกอบ

คำจำกัดความ

เราเรียกว่าโหนดภายในเป็น 2 โหนดหากมีองค์ประกอบข้อมูลหนึ่งองค์ประกอบและลูกสองคน

เราเรียกโหนดภายในว่าเป็นโหนด 3 โหนดหากมีองค์ประกอบข้อมูล 2 รายการและโหนดลูก 3 รายการ

เราเรียกสิ่งนั้นว่า T เป็นต้นไม้ 2-3 ต้นก็ต่อเมื่อข้อความต่อไปนี้ตรงกับข้อใดข้อหนึ่ง -

• T ว่างเปล่าหรือว่างเปล่า กล่าวอีกนัยหนึ่ง T ไม่มีโหนดใด ๆ

• T คือ 2 โหนดที่ติดตั้งองค์ประกอบข้อมูล a ถ้า T ทิ้งลูก L และลูกขวา R เราก็สรุป

• L และ R ถือเป็นต้นไม้ที่มีความสูงเท่ากัน 2-3 ต้น

• a สูงกว่าแต่ละองค์ประกอบใน L; และ

• a น้อยกว่าหรือเท่ากับแต่ละองค์ประกอบข้อมูลใน R.

• T คือโหนด 3 โหนดที่มีองค์ประกอบข้อมูล a และ b โดยที่ a น้อยกว่า b ถ้า T ทิ้งลูก L ลูกกลาง M และลูกขวา R เราก็สรุป

• L, M และ R ถือเป็นต้นไม้ 2-3 ต้นที่มีความสูงเท่ากัน

• a สูงกว่าองค์ประกอบข้อมูลแต่ละองค์ประกอบใน L และเล็กกว่าหรือเท่ากับองค์ประกอบข้อมูลแต่ละรายการใน M และ

• b สูงกว่าองค์ประกอบข้อมูลแต่ละองค์ประกอบใน M และเล็กกว่าหรือเท่ากับองค์ประกอบข้อมูลแต่ละรายการใน R

คุณสมบัติ

• โหนดภายในทั้งหมดถือเป็น 2 โหนดหรือ 3 โหนด

• ใบทั้งหมดอยู่ในระดับเดียวกัน

• ข้อมูลทั้งหมดจะได้รับการดูแลหรือจัดเรียงลำดับ

ปฏิบัติการ

กำลังค้นหา

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

• ให้ T เป็นต้นไม้ 2-3 ต้น และ d เป็นองค์ประกอบข้อมูลที่เราต้องการค้นหา หาก T ว่างเปล่า แสดงว่า d ไม่อยู่ใน T และเราจะถูกดำเนินการ

• ให้ r เป็นรากของ T.

• ให้ r เป็นใบไม้ ถ้า d ไม่อยู่ใน r ดังนั้น d จึงไม่อยู่ใน T มิฉะนั้น d อยู่ใน T โดยเฉพาะอย่างยิ่ง d สามารถพบได้ที่โหนดปลายสุด เราไม่ต้องการขั้นตอนเพิ่มเติมและเราจะดำเนินการ

• สมมติว่า r ถูกปฏิบัติเป็น 2 โหนดโดยมี L ลูกด้านซ้ายและ R ลูกด้านขวา ให้ e ถูกถือเป็นองค์ประกอบข้อมูลใน r

มีสามกรณี -

• หาก d เท่ากับ e เราพบ d ใน T แล้วจึงดำเนินการ

• ถ้า d น้อยกว่า e ให้ตั้งค่า T เป็น L ซึ่งตามคำจำกัดความคือ 2-3 tree แล้วกลับไปที่ขั้นตอนที่ 2

• หาก d มากกว่า e ให้ตั้งค่า T เป็น R แล้วกลับไปที่ขั้นตอนที่ 2

• ให้ r เป็น 3 โหนดที่มี L ลูกซ้าย ลูกกลาง M และลูกขวา R ให้ a และ b เป็นองค์ประกอบข้อมูลสององค์ประกอบของ r โดยที่ a

  • ถ้า d เท่ากับ a หรือ b ดังนั้น d อยู่ใน T และเราจะดำเนินการ

  • หาก d น้อยกว่า a ให้ตั้งค่า T เป็น L แล้วกลับไปที่ขั้นตอนที่ 2

  • หาก ais น้อยกว่า d และ d น้อยกว่า b ให้ตั้งค่า T เป็น M และกลับไปที่ขั้นตอนที่ 2

  • ถ้า d มากกว่า b ให้ตั้งค่า T เป็น R แล้วย้อนกลับไปยังขั้นตอนที่ 2