ต้นไม้ 2–3

ในวิทยาการคอมพิวเตอร์ ต้นไม้ 2-3 (อังกฤษ: 2–3 tree) เป็นโครงสร้างข้อมูลต้นไม้ ซึ่งทุกโหนดที่มี children มี children สอง (2 โหนด) และหนึ่งองค์ประกอบข้อมูลหรือสาม children (3 โหนด) และสององค์ประกอบข้อมูล อ้างอิงจาก Knuth “B – tree ของลำดับที่ 3 คือ 2 – 3 tree” โหนดที่อยู่ด้านนอกของต้นไม้ (leaf nodes) ไม่มี children และ 1 หรือ 2 องค์ประกอบข้อมูล 2 – 3 tree ถูกคิดค้นโดย John Hopcroft ในปี พ.ศ. 2513

2 node
3 node

2-3 tree มีความสมดุล ซึ่งหมายความว่าด้านขวา, กึ่งกลางและด้านซ้ายแต่ละอันมีข้อมูลเดียวกันหรือใกล้เคียงกับข้อมูลเท่ากัน

คำนิยาม

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

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

T เป็น 2-3 tree ถ้าหากมีคำใดข้อหนึ่งต่อไปนี้:

T ว่างเปล่า กล่าวอีกนัยหนึ่ง T ไม่มีโหนดใด ๆ
T เป็นโหนด 2 โหนดที่มีองค์ประกอบข้อมูล a ถ้า T ทิ้งลูก L และขวาไว้ที่ R แล้ว
L และ R เป็นต้นไม้ที่ไม่ว่างเปล่า 2-3 tree ที่มีความสูงเท่ากัน
a มากกว่าแต่ละองค์ประกอบใน L
a น้อยกว่าหรือเท่ากับแต่ละองค์ประกอบข้อมูลใน R
T คือโหนด 3 ที่มีองค์ประกอบข้อมูล a และ b ซึ่ง a < b ถ้า T มี child ข้างซ้ายเรียก L, child ตรงกลางเรียก M และ child ข้างขวา เรียก R
L, M และ R เป็นต้นไม้ที่ไม่ว่างเปล่า 2-3 ต้นที่มีความสูงเท่ากัน
a มากกว่าแต่ละองค์ประกอบข้อมูลใน L และน้อยกว่าหรือเท่ากับแต่ละองค์ประกอบข้อมูลใน M
b มากกว่าแต่ละองค์ประกอบข้อมูลใน M และน้อยกว่าหรือเท่ากับแต่ละองค์ประกอบข้อมูลใน R

คุณสมบัติ

ทุกโหนดภายในเป็นโหนด 2 โหนดหรือ 3 โหนด
ใบทั้งหมดอยู่ในระดับเดียวกัน
ข้อมูลทั้งหมดจะถูกเก็บไว้ในลำดับที่เรียงลำดับ

การดำเนินงาน

ค้นหา

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

ให้ T เป็น 2-3 tree และ 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 ต้นและกลับไปที่ขั้นตอนที่ 2
- ถ้า d > e ให้ตั้ง T ไปที่ R และกลับไปยังขั้นตอนที่ 2
สมมติว่า r คือโหนด 3 ตัวที่มีลูกซ้าย L, ลูกคนกลาง M และลูกขวา R ให้ a และ b เป็นสององค์ประกอบข้อมูลของ r โดยที่ a < b มีสี่กรณี:
- ถ้า d เท่ากับ a หรือ b แล้ว d อยู่ใน T และเราทำเสร็จแล้ว
- ถ้า d < a แล้วตั้ง T ไปที่ L และกลับไปยังขั้นตอนที่ 2
- ถ้า a < d < b แล้วตั้ง T เป็น M และกลับไปยังขั้นตอนที่ 2
- ถ้า d > b ให้ตั้ง T ไปที่ R และกลับไปยังขั้นตอนที่ 2

การลบ

การประมวลผลการลบอาจแตกต่างกันระหว่าง 2-3 tree และ BB tree ในกรณีต้นไม้ 2-3 tree จะเป็นดังนี้

หากผู้ปกครองที่มีองค์ประกอบลบมีสาม children ให้ลบองค์ประกอบนั้นและอัปเดตคีย์ของ parent ถ้าค่าลบเป็นค่าที่ใหญ่ที่สุดในกลุ่มพี่น้องให้ลบคีย์เดียวกันกับค่าลบออกจากคีย์ของ parent ถ้าค่าลบอยู่ตรงกลางระหว่าง parent's ให้ลบค่าของคุณจากคีย์หลักและย้าย parent's ขวาไปตรงกลาง ในกรณีด้านซ้ายสุดให้ลบคีย์กลางและเลื่อนตรงกลางไปทางซ้ายและขวาไปตรงกลาง
หากผู้ปกครองที่มีองค์ประกอบลบมี 2 children จะค้นหาพี่น้องของ parent
หากพี่น้องของ parent ที่ดึงข้อมูลมามี 2 children ให้รวมผู้ปกครองและ parent's กันเป็น parent หนึ่งที่มีสาม children
เมื่อรวมเข้าด้วยการดำเนินงาน 3 จะยืนยันได้ว่าจำนวน parents and parents of parents มีค่าเท่ากับ 2 หรือ 3 ถ้ามีเพียง children เดียวให้ทำซ้ำตั้งแต่ 2 เป็นต้นไป

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

การแทรก

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