2-3 Tree เป็นต้นไม้ในโครงสร้างข้อมูลที่โหนดทุกตัวเป็น 2-node หรือ 3-node เป็นกรณีพิเศษของ B-Tree ออร์เดอร์ 3
- 2-node: มี 1 ส่วนข้อมูล (data) และ 2 ลูก
- 3-node: มี 2 ส่วนข้อมูล และ 3 ลูก
คุณสมบัติของ 2-3 Tree
- โหนดภายในทุกตัวเป็น 2-node หรือ 3-node
- โหนดที่มี 1 data → 2-node มี 2 ลูก หรือเป็น leaf ไม่มีลูก
- โหนดที่มี 2 data → 3-node มี 3 ลูกเท่านั้น
- Leaf ทุกตัวอยู่ระดับเดียวกัน
- 2-3 Tree เป็น height-balled tree เสมอ
- ค้นหา (Search) รวดเร็วและมีประสิทธิภาพ
2-Node
- มีลูก 2 ตัว
- ลูกซ้ายมีค่าน้อยกว่า
- ลูกขวามีค่ามากกว่า
- อาจเป็น leaf ไม่มีลูก
3-Node
- มีลูก 3 ตัว
- มีค่าข้อมูล 2 ค่า
- ลูกซ้าย < data ซ้าย, ลูกกลางอยู่ระหว่าง 2 data, ลูกขวา > data ขวา
- ไม่เคยเป็น leaf
การดำเนินการใน 2-3 Tree
1. การค้นหา (Searching)
- คล้าย Binary Search Tree เพราะข้อมูลเรียงลำดับ
- ถ้าต้นไม้ว่าง → False
- ถ้าถึงรากแล้วไม่เจอ → False
- X < data ซ้าย → ค้นหา subtree ซ้าย
- data ซ้าย < X < data ขวา → ค้นหา subtree กลาง
- X > data ขวา → ค้นหา subtree ขวา
2. การแทรก (Insertion)
- ถ้าต้นไม้ว่าง → ใส่ X เป็นราก
- ค้นหาตำแหน่งที่ถูกต้อง ใส่เป็น leaf
- ถ้า leaf มี 1 data → ใส่ X กลายเป็น 2-node
- ถ้า leaf มี 2 data → ใส่ X แยก 3-node ชั่วคราว ย้าย data ขึ้นไปพาเรนต์ตามลำดับ
ตัวอย่างสร้าง 2-3 tree ใส่: 10, 5, 8, 15, 23, 21
3. การลบ (Deletion)
- ถ้าต้นไม้ว่าง → False
- ค้นหาตำแหน่ง X ลบ แล้วปรับโครงสร้าง
- ถ้า X อยู่ใน 3-node → ลบ X ปรับค่าซ้าย/กลาง รวมถึง ancestor ถ้าจำเป็น
- ถ้า X อยู่ใน 2-node → ปรับและแยกต้นไม้แบบ recursive เรียงลำดับใหม่
