ข้ามไปเนื้อหา

ต้นไม้ 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-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 โหนดและคีย์กลางจะถูกย้ายไปยังพาเรนต์ แผนภาพแสดงให้เห็นถึงกระบวนการ

การแทรกเลขใน 2-3 tree