closest to this node moves up to the parent key that overlooks the two nodes. The parent key moves down to this node to form a 3-node. The child that was originally with the rotated sibling key is now this node's additional child. If the parent is a 2-node and the sibling is also a 2-node, combine all three elements to form a new 4-node and shorten the tree. (This rule can only trigger if the parent 2-node is the root, since all other 2-nodes along the way will have been modified to not be 2-nodes. This is why "shorten the tree" here preserves balance; this is also an important assumption for the fusion operation.) If the parent is a 3-node or a 4-node and all adjacent siblings are 2-nodes, do a fusion operation with the parent and an adjacent sibling: The adjacent sibling and the parent key overlooking the two sibling nodes come together to form a 4-node. Transfer the sibling's children to this node. Once the sought value is reached, it can now be placed at the removed entry's location without a problem because we have ensured that the leaf node has more than 1 key. Deletion in a 2–3–4 tree is O(log n), assuming transfer and fusion run in constant time (O(1)). Parallel operations Since 2–3–4 trees are similar in structure to red–black trees, parallel algorithms for red–black trees can be applied to 2–3–4 trees as well. See also 2–3 tree Red–black tree B-tree Queap References External links Algorithms In Action, with 2–3–4 Tree animation Left-leaning Red–Black Trees – Robert Sedgewick, Princeton University, 2008 Open Data Structures – Section 9.1 – 2–4 Trees , Pat Morin 2–3–4 Trees: A Visual Introduction, 2017 B-tree