procedure delete(parent, N, K)
    # N is node to insert in (a subtree); parent is... its parent;
    # K is the key to delete
    #
    # this pseudocode is missing the case of the root being deleted
    # (assume tree is never empty)

    if N is a non-leaf:
        determine which subtree P[i] to delete K from, based on keys
            in N

        # old Entry is a key to be deleted
        oldEntry = delete(N, P[i], K)

        if oldEntry == None:
            # child was not deleted, so nothing new to do here
            return None
        else:
            remove oldEntry and the pointer to its right

            if N has room to spare:
                return None

            else:
                get a sibling S of N:
                if S has extra entries:
                    redistribute evenly between N and S through parent
                    return None
                else:
                    K' = key in parent between N and S
                    pull K' from parent down into node on left
                    move all entries from right node into left
                    discard empty right node
                    return K'

    else:  # N is a leaf
        if N has room to spare:
            remove K and associated pointer
            return None

        else:
            get a sibling S of N
            if S has extra entries:
                redistribute evenly beween N and S
                K' = key in parent between N and S
                change K' to be new low-key value of node on right
                return None
            else:
                K' = key in parent between N and S
                move all entries from right node into left
                discard empty right nodew
                adjust sibling pointers
                return K'