Monday, February 14, 2011

2-3-4 tree


ทำไมต้องชื่อ 2-3-4 tree?
ตัวเลข 2 3 และ 4 บอกถึงรูปแบบของ node ที่มีใช้ใน tree นี้ 3 แบบ คือ

ปมแบบ 2 (2-node)
ใน 1 node จะมี ข้อมูล 1 ตัว และมี child node ได้ 2 nodes (มี 2 pointer ชี้ไปที่ children)

 ปมแบบ 3 (3-node)
ใน 1 node จะมี ข้อมูล 2 ตัว และมี child node ได้ 3 nodes
  
 ปมแบบ 4 (4-node)
ใน 1 node จะมี ข้อมูล 3 ตัว และมี child node ได้ 4 nodes 


ข้อมูลทั่วไปของ 2-3-4 tree
2-3-4 tree (หรือเรียกอีกอย่างหนึ่งว่า 2-4 tree) เป็นโครงสร้างข้อมูลแบบต้นไม้ได้ดุล คือจัดสมดุลด้วยตัวเองเมื่อมีการเพิ่มหรือลบข้อมูล ซึ่งโดยทั่วไปจะใช้เป็นส่วนหนึ่งในการทำระบบพจนานุกรม
2-3-4 tree คือ B-trees อันดับ 2 (order 2) โดยพื้นฐานจึงเหมือนกับ B-trees สามารถค้นหา เพิ่มและลบข้อมูลในเวลา O(log n) คุณสมบัติอย่างหนึ่งที่สำคัญของ 2-3-4 tree คือ ใบ (leaf หรือ external nodes) จะมีความลึกเท่ากัน (มีการประกันความสูงเป็น O(log n) )
2-3-4 tree มีโครงสร้างเหมือนกับ red-black trees เพราะ red-black trees  ประยุกต์แนวคิดมาจาก 2-3-4 tree  ในอีกแง่หนึ่งก็คือ ทุกๆ 2-3-4 tree จะมี red-black tree อย่างน้อย 1 ต้นกับ data element ในอันดับเดียวกัน ยิ่งกว่านั้น การเพิ่มและลบข้อมูลของ 2-3-4 trees ที่ทำให้แต่ละ node ขยาย แยก หรือรวมกัน ก็เหมือนกับการสลับสีและการหมุนของ node ใน red-black trees ด้วยเหตุนี้ในการอธิบายเกี่ยวกับ red-black trees จึงมักจะแนะนำถึง 2-3-4 trees ก่อน แต่อย่างไรก็ตาม การจะ implement 2-3-4 trees ในการเขียนโปรแกรมมักจะยาก เพราะมีกรณีเฉพาะที่เกี่ยวข้องกับการทำงานของต้นไม้แบบนี้เยอะ ส่วนใหญ่จึงหันไปใช้ red-black trees แทนเพราะ implement ได้ง่ายกว่า

Magic of the Lower Left Leaf ในการทำงานตั้งแต่ต้นจนจบ ถ้าคุณมีความระมัดระวังในการรวมข้อมูลใน node (fusions) จะพบว่า the Lower Left Leaf จะเป็น node เดิมเสมอ ดังนั้นในการหาค่าข้อมูลที่น้อยที่สุดจึงหาได้ในเวลาคงตัว O(1) จากจุดนี้ถ้าใช้การค้นคืนข้อมูลแบบตามลำดับ (in-order) ในข้อมูลทั้งหมด p ตัว ข้อมูลน้อยสุด p ตัว (ข้อมูลทั้งหมดจากน้อยไปหามาก) จะหาพบได้ในเวลา O(p log(n))


Insertion การเพิ่มข้อมูล
การเพิ่มข้อมูล เราจะเริ่มต้นที่ root ของ 2-3-4 tree

1. ถ้า node ปัจจุบันที่ดูอยู่เป็น 4-node
  • นำค่าที่อยู่ตรงกลางไปเก็บไว้ และลบออกจาก node เพื่อให้ได้ 3-node
  • แยก 3-node ที่เหลือออกเป็น 2-node 2อัน
- ถ้า node นี้เป็น root node (ซึ่งไม่มี parent) ค่าที่เก็บไว้จะเป็น root ใหม่ของ 2-node 2อัน และความสูงของ tree เพิ่มขึ้น 1 แล้วย้อนกลับไปพิจารณาขั้นต่อไปที่ root
- ถ้าไม่ใช่ ดันค่าที่เก็บไว้ขึ้นไปที่ parent node แล้วย้อนกลับไปพิจารณาขั้นต่อไปที่ parent
2. หา child ที่มีช่วงของค่าที่จะทำการเพิ่ม
3. ถ้า child นั้นเป็นใบ ใส่ค่าที่จะทำการเพิ่มเข้าไปใน node นั้นเป็นอันเสร็จสิ้น
-ถ้าไม่ใช่ลงไปที่ child ของ node นั้น และเริ่มทำ step 1 ใหม่

ตัวอย่าง
ในการเพิ่มค่า 25 ลงไปใน 2-3-4 tree


- เริ่มที่ root (10,20) และลงไปพิจารณาที่ child ขวาสุด (22,24,29) เพราะ 25 อยู่ในช่วง 20 ถึง
- Node (22,24,29) เป็น 4-node ดังนั้นค่าที่อยู่ตรงกลางคือ 24 ถูกดันขึ้นไปที่ parent node


- 3-node ที่เหลือ (22,29) แยกเป็น 2-node 2 อัน (22) และ (29) จากนั้นย้อนกลับไปที่ parent ใหม่ (10,20,24)
- ลงไปพิจารณาที่ child ขวาสุด (29) เพราะ 25 อยู่ในช่วง 24 ถึง


- Node 29 ไม่มี child ขวาสุด (ไม่มี child ที่อยู่ในช่วง 29 ถึง ) ดังนั้นจึงใส่ค่า 25 ที่ node นี้


Deletion การลบข้อมูล
- การลบข้อมูลใน 2-3-4 tree จะใช้เวลา O(log n) โดยถือว่าการ transfer และ fusion ใช้เวลาคงที่ O(1) ในส่วนของการลบนี้จะมีความซับซ้อนและมีกรณีพิเศษค่อนข้างมาก ดังนี้
- ขั้นแรกต้องหาข้อมูลที่จะทำการลบให้เจอก่อน โดยข้อมูลนั้นจะต้องเป็น node ที่อยู่ล่างสุดของ tree ถ้าไม่ใช่ต้องทำการสลับข้อมูลกับข้อมูลก่อนหน้า(คือ ข้อมูลที่พบได้ก่อนข้อมูลใน node นี้ ในการเรียงแบบ in-order) ซึ่งต้องอยู่ใน node ล่างสุด และลบ node นี้ทิ้งแทน
- ถ้าข้อมูลที่จะต้องลบอยู่ใน 2-node เมื่อลบข้อมูลแล้ว node นี้จะหายไป เรียกว่า underflow การแก้ underflow นี้ ข้อมูล 1 ตัวจาก child ของ node ที่จะถูกลบ(ถือว่าเป็น parent) จะถูกดึงขึ้นมา เมื่อลบข้อมูลแล้วจะแทนช่องว่างของข้อมูลที่เกิดขึ้นจาก sibling node (คือ node ที่มี parent เดียวกัน) วิธีนี้เรียกว่า transfer
- พิจารณาต่อว่า ถ้า sibling node เป็น 2-node เช่นกัน จะเกิด underflow ต่อ เพราะขณะนี้ sibling ไม่มีข้อมูลแล้ว จึงต้องทำการรวม (fused) 2 sibling nodes เข้าด้วยกัน (หลังจากที่มีการดึงข้อมูลโดย parent node แล้ว)
- สุดท้ายพิจารณาต่อว่า ถ้า parent เป็น 2-node จะเกิด underflow ที่ parent node ด้วย สามารถแก้ไขได้โดยใช้วิธีข้างต้น ด้วยเหตุนี้เมื่อมีการลบและแทนที่เกิดขึ้น จะทำให้หลายๆ parent node เกิด underflow ต่อกันเป็นทอดๆ เรียกว่า underflow cascading

สามารถลองใช้ 2-3-4 tree แบบ Java applet ซึ่งแสดงการทำงานต่างๆของ tree นี้ ได้ที่
http://www.cse.ohio-state.edu/~bondhugu/acads/234-tree/index.shtml

อ้างอิง
http://en.wikipedia.org/wiki/2-3-4_tree
http://www.clear.rice.edu/comp212/01-fall/lectures/33/