Method Delete

structure/tree/btree.go:244–345

(tree *BTree[T], key T)

}

func (node *BTreeNode[T]) Delete(tree *BTree[T], key T) {
	node.Verify(tree)
	if node.isLeaf {
		// Case 1: Node is a leaf. Directly delete the key.
		for i := 0; i < node.numKeys; i++ {
			if key == node.keys[i] {
				node.DeleteIthKey(i)
				return
			}
		}
		return
	}

	minKeys := minKeys(tree.maxKeys)
	i := 0
	for ; i < node.numKeys; i++ {
		if key == node.keys[i] {
			// Case 2: key exists in a non-leaf node
			left := node.children[i]
			right := node.children[i+1]
			if left.numKeys > minKeys {
				// Replace the key we want to delete with the max key from the left
				// subtree. Then delete that key from the left subtree.
				//  A B C
				//   /
				// a b c
				//
				// If we want to delete `B`, then replace `B` with `c`, and delete `c` in the subtree.
				//  A c C
				//   /
				// a b
				replacementKey := left.Max()
				node.keys[i] = replacementKey
				left.Delete(tree, replacementKey)
			} else if right.numKeys > minKeys {
				// Replace the key we want to delete with the min key from the right
				// subtree. Then delete that key in the right subtree. Mirrors the
				// transformation above for replacing from the left subtree.
				replacementKey := right.Min()
				node.keys[i] = replacementKey
				right.Delete(tree, replacementKey)
			} else {
				// Both left and right subtrees have the minimum number of keys. Merge
				// the left tree, the deleted key, and the right tree together into the
				// left tree. Then recursively delete the key in the left tree.
				if left.numKeys != minKeys || right.numKeys != minKeys {
					panic("nodes should not have less than the minimum number of keys")
				}
				node.Merge(i)
				left.Delete(tree, key)
			}
			return
		}

		if key < node.keys[i] {
			break
		}
	}