createNewParent = (blockMap: BlockMap, key: string): BlockMap => {
  verifyTree(blockMap);
  const block = blockMap.get(key);
  invariant(block != null, 'block must exist in block map');
  const newParent = new ContentBlockNode({
    key: generateRandomKey(),
    text: '',
    depth: block.depth,
    type: block.type,
    children: Immutable.List([]),
  });
  // add the parent just before the child in the block map
  let newBlockMap = blockMap
    .takeUntil(block => block.getKey() === key)
    .concat(Immutable.OrderedMap([[newParent.getKey(), newParent]]))
    .concat(blockMap.skipUntil(block => block.getKey() === key));
  // set parent <-> child connection
  newBlockMap = updateParentChild(newBlockMap, newParent.getKey(), key, 0);
  // set siblings & parent for the new parent key to child's siblings & parent
  const prevSibling = block.getPrevSiblingKey();
  const nextSibling = block.getNextSiblingKey();
  const parent = block.getParentKey();
  if (prevSibling != null) {
    newBlockMap = updateSibling(newBlockMap, prevSibling, newParent.getKey());
  }
  if (nextSibling != null) {
    newBlockMap = updateSibling(newBlockMap, newParent.getKey(), nextSibling);
  }
  if (parent != null) {
    newBlockMap = replaceParentChild(
      newBlockMap,
      parent,
      key,
      newParent.getKey(),
    );
  }
  verifyTree(newBlockMap);
  return newBlockMap;
}
This is a utility method that abstracts the operation of creating a new parent
for a particular node in the block map.

This operation respects the tree data invariants - it expects and returns a
valid tree.