ที่นี่เราจะดูวิธีการลบโหนดจาก B-Tree สมมติว่าเรามี BTree ด้านล่าง -
ตัวอย่าง B-Tree −
การลบมีสองส่วน อันดับแรกเราต้องหาองค์ประกอบ กลยุทธ์นั้นก็เหมือนกับการสอบถาม ตอนนี้สำหรับการลบ เราต้องคำนึงถึงกฎบางอย่าง โหนดหนึ่งต้องมีองค์ประกอบอย่างน้อย m/2 ดังนั้นหากเราลบองค์ประกอบหนึ่งองค์ประกอบและองค์ประกอบเหลือน้อยกว่า m-1 มันจะปรับตัวเอง หากโหนดทั้งหมดถูกลบ โหนดย่อยจะถูกรวมเข้าด้วยกัน และหากขนาดของโหนดเท่ากับ m ให้แยกโหนดออกเป็นสองส่วน และค่ามัธยฐานจะเพิ่มขึ้นอีกครั้ง
สมมติว่าเราต้องการลบ 46 ตอนนี้มีลูกสองคน [45] และ [47, 49] จากนั้นจะรวมกันเป็น [45, 47, 49] ตอนนี้ 47 จะขึ้นไป
อัลกอริทึม
BTreeDelete(x, คีย์) −
ป้อนข้อมูล − รากของต้นไม้และปุ่มสำหรับลบ
เราจะถือว่ามีคีย์อยู่ในรายการ
if x is leaf, then delete object with key ‘key’ from x else if x does not contain the object with key ‘key’, then locate the child x->child[i] whose key range is holding ‘key’ y := x->child[i] if y has m/2 elements, then If the sibling node z immediate to the left or right of y, has at least one more object than m/2, add one more object by moving x->key[i] from x to y, and move that last or first object from z to x. If y is non-leaf node, then last or first child pointer in z is also moved to y else any immediate sibling of y has m/2 elements, merge y with immediate sibling end if BTreeDelete(y, key) else if y that precedes ‘key’ in x, has at-least m/2 + 1 objects, then find predecessor k of ‘key’, in the sub-tree rooted by y. then recursively delete k from the sub-tree and replace key with k in x else if ys has m/2 elements, then check the child z, which is immediately follows ‘key’ in x if z has at least m/2+1 elements, then find successor k of ‘key’, in the sub-tree rooted by z. recursively delete k from sub-tree, and replace key with k in x else both y and z has m/2 elements, then merge then into one node, and push ‘key’ down to the new node as well. Recursively delete ‘key’ from this new node end if end if
