2 - 3 - 4 trees are B - trees of order 4. They are isometric of _________ trees.

Answer: Red-Black trees.

Key idea: 2-3-4 trees (B-trees of order 4) can be represented exactly as red-black trees by replacing multi-key nodes with small binary subtrees connected by red links. This preserves the search structure and yields an isometry.

• 2-node (one key): corresponds to a single black node.

• 3-node (two keys): corresponds to a black node with one red child (the red link represents the extra key).

• 4-node (three keys): corresponds to a black node with two red children (both red links represent the extra keys).

Consequences: the two representations are isometric (they encode the same search order and branching). The black-height of the red-black tree matches the height of the 2-3-4 tree, so search costs correspond.

Why other tree types listed are not correct:

• AVL trees are height-balanced binary search trees with different balancing invariants; they are not the standard isometric representation of 2-3-4 trees.

• AA-trees are a constrained form of red-black trees but are not the canonical one-to-one representation used to show isometry with 2-3-4 trees.

• 2-3 trees are B-trees of order 3 and are related but not the same order as 2-3-4 trees; the standard, exact correspondence for 2-3-4 is with red-black trees.