Xem xóa nút khỏi B-Tree. Ví dụ B-Tree:
Ví dụ B-Tree
Xóa: tìm phần tử (giống query). Quy tắc: nút ít nhất m/2 phần tử. Xóa một, nếu còn < m-1, tự điều chỉnh. Xóa hết nút → gộp con, nếu size = m thì tách 2, trung vị lên cha.
Ví dụ xóa 46. Hai con [45] và [47,49] → gộp [45,47,49], 47 lên cha.
Thuật toán
BTreeDelete(x, key) −
Input: gốc, khóa xóa. Giả sử khóa có trong cây.
if x là lá thì
xóa đối tượng khóa 'key' từ x
else if x không chứa 'key' thì
tìm con x->child[i] có khoảng khóa chứa 'key'
y := x->child[i]
if y có m/2 phần tử thì
if anh chị em z (trái/phải) của y có ≥ m/2+1 đối tượng thì
chuyển x->key[i] từ x xuống y,
chuyển đối tượng cuối/đầu từ z lên x.
nếu y không phải lá, con trỏ cuối/đầu của z cũng chuyển sang y
else
gộp y với anh chị em liền kề
end if
BTreeDelete(y, key)
else
if y (trước 'key' trong x) có ≥ m/2+1 đối tượng thì
tìm predecessor k của 'key' trong cây con y. xóa k đệ quy từ cây con, thay key bằng k trong x
else if z (sau 'key') có m/2 phần tử thì
if z có ≥ m/2+1 thì
tìm successor k trong cây con z. xóa k đệ quy, thay key bằng k trong x
else
cả y và z đều m/2 → gộp chúng, đẩy 'key' xuống nút mới. Xóa 'key' đệ quy từ nút mới
end if
end if
end if
end if