B-Tree Deletion ในโครงสร้างข้อมูล

ตัวอย่าง B-Tree

กระบวนการลบ

1. ค้นหา (เหมือน Query)
2. ลบพร้อมรักษา: โหนดต้องมี ≥ m/2 Elements

ลบแล้ว < m-1 → Adjust ลบโหนดทั้งโหนด → Merge Children ถ้าขนาด = m → Split 2 ส่วน Median ขึ้น

ตัวอย่าง: ลบ 46

Children: [45] และ [47, 49] → Merge → [45, 47, 49] → 47 ขึ้นไป

อัลกอริทึม

BTreeDelete(x, key)
Input: Root, Key to delete (assume exists)
if x leaf: delete key from x
else if key not in x:
    locate child y = x→child[i] holding key
    if y has m/2 elements:
        if sibling z has ≥ m/2+1: move x→key[i] to y, move first/last from z to x (move child ptr if non-leaf)
        else: merge y with sibling
    BTreeDelete(y, key)
else:
    if predecessor y has ≥ m/2+1: find pred k in y, recursively delete k, replace key with k in x
    else if successor z has m/2:
        if z has ≥ m/2+1: find succ k in z, recursively delete k, replace key with k in x
        else: merge y and z, push key down, recursively delete key from new node
    end if
end if