ต้นไม้ 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 ที่ถูกต้องและในที่สุดจะเป็นโหนดที่ถูกต้องซึ่งประกอบด้วยรายการดังกล่าว
1. ให้ T เป็น 2-3 tree และ d เป็นองค์ประกอบข้อมูลที่เราต้องการหา ถ้า T ว่างเปล่าแล้ว d ไม่อยู่ใน T และเราทำเสร็จแล้ว
2. ให้ r เป็นรากของ T.
3. สมมติว่า r คือใบ ถ้า d ไม่อยู่ใน r แล้ว d ไม่อยู่ใน T มิฉะนั้น d อยู่ใน T โดยเฉพาะอย่างยิ่ง d สามารถพบได้ที่โหนดใบ เราไม่จำเป็นต้องทำตามขั้นตอนต่อไปและเราทำเสร็จแล้ว
4. สมมติว่า r เป็นโหนด 2 โหนดที่มีลูกซ้าย L และลูกขวา R ให้ e เป็นอิลิเมนต์ข้อมูลใน r มีสามกรณี:
- ถ้า d เท่ากับ e แล้วเราพบ d ใน T และเราทำเสร็จแล้ว
- ถ้า d <e ให้ตั้ง T ไปที่ L ซึ่งตามความหมายคือต้นไม้ 2-3 ต้นและกลับไปที่ขั้นตอนที่ 2
- ถ้า d> e ให้ตั้ง T ไปที่ R และกลับไปยังขั้นตอนที่ 2
5. สมมติว่า r คือโหนด 3 ตัวที่มีลูกซ้าย L, ลูกคนกลาง M และลูกขวา R ให้ a และ b เป็นสององค์ประกอบข้อมูลของ r โดยที่ a <b. มีสี่กรณี:
- ถ้า d เท่ากับ a หรือ b แล้ว d อยู่ใน T และเราทำเสร็จแล้ว
- ถ้า d <a แล้วตั้ง T ไปที่ L และกลับไปยังขั้นตอนที่ 2 - ถ้า a<d b ให้ตั้ง T ไปที่ R และกลับไปยังขั้นตอนที่ 2
การลบ
[แก้]การประมวลผลการลบอาจแตกต่างกันระหว่าง 2-3 tree และ BB tree ในกรณีต้นไม้ 2-3 tree จะเป็นดังนี้
1. หากผู้ปกครองที่มีองค์ประกอบลบมีสาม children ให้ลบองค์ประกอบนั้นและอัปเดตคีย์ของ parent ถ้าค่าลบเป็นค่าที่ใหญ่ที่สุดในกลุ่มพี่น้องให้ลบคีย์เดียวกันกับค่าลบออกจากคีย์ของ parent ถ้าค่าลบอยู่ตรงกลางระหว่าง parent's ให้ลบค่าของคุณจากคีย์หลักและย้าย parent's ขวาไปตรงกลาง ในกรณีด้านซ้ายสุดให้ลบคีย์กลางและเลื่อนตรงกลางไปทางซ้ายและขวาไปตรงกลาง
2. หากผู้ปกครองที่มีองค์ประกอบลบมี 2 children จะค้นหาพี่น้องของ parent
3. หากพี่น้องของ parent ที่ดึงข้อมูลมามี 2 children ให้รวมผู้ปกครองและ parent's กันเป็น parent หนึ่งที่มีสาม children
4. เมื่อรวมเข้าด้วยการดำเนินงาน 3 จะยืนยันได้ว่าจำนวน parents and parents of parents มีค่าเท่ากับ 2 หรือ 3 ถ้ามีเพียง children เดียวให้ทำซ้ำตั้งแต่ 2 เป็นต้นไป
ในกรณีของ BB tree ให้ลบค่าลบก่อนเพื่อตัดสินว่าสภาพของต้นไม้ 2-3 tree มีความพึงพอใจหรือไม่ หากค่าการลบเป็นใบที่มีสององค์ประกอบให้ลบค่านั้นออก ในกรณีอื่น ๆ จะมีการดำเนินการโดยการคำนวณค่ามัธยฐานกับ parent หลังจากลบและทำซ้ำการผสมผสานกับพี่น้องของผู้ปกครองหากเด็กอายุสั้น
การแทรก
[แก้]แทรกทำงานโดยการค้นหาตำแหน่งที่เหมาะสมของคีย์และเพิ่มที่นั่น ถ้าโหนดกลายเป็น 4 โหนดโหนดจะถูกแบ่งออกเป็น 2 โหนดและคีย์กลางจะถูกย้ายไปยังพาเรนต์ แผนภาพแสดงให้เห็นถึงกระบวนการ
