Editing 2–3 tree (section)

==Definitions==
We say that an internal node is a '''2-node''' if it has ''one'' data element and ''two'' children.

We say that an internal node is a '''3-node''' if it has ''two'' data elements and ''three'' children.

A '''4-node''', with three data elements, may be temporarily created during manipulation of the tree but is never persistently stored in the tree.

<gallery heights="95px">
Image:2-3-4 tree 2-node.svg|2 node
Image:2-3-4-tree 3-node.svg|3 node
</gallery>

We say that {{mvar|T}} is a '''2–3 tree''' if and only if one of the following statements hold:<ref name="A4"/>

* {{mvar|T}} is empty. In other words, {{mvar|T}} does not have any nodes.
* {{mvar|T}} is a 2-node with data element {{mvar|a}}. If {{mvar|T}} has left child {{mvar|p}} and right child {{mvar|q}}, then 
** {{mvar|p}} and {{mvar|q}} are 2–3 trees of the same [[Tree (data structure)#Terminology|height]];
** {{mvar|a}} is greater than each element in {{mvar|p}}; and
** {{mvar|a}} is less than each data element in {{mvar|q}}.
* {{mvar|T}} is a 3-node with data elements {{mvar|a}} and {{mvar|b}}, where {{mvar|a}} {{Math| <}} {{mvar|b}}. If {{mvar|T}} has left child {{mvar|p}}, middle child {{mvar|q}}, and right child {{mvar|r}}, then
** {{mvar|p}}, {{mvar|q}}, and {{mvar|r}} are 2–3 trees of equal height;
** {{mvar|a}} is greater than each data element in {{mvar|p}} and less than each data element in {{mvar|q}}; and
** {{mvar|b}} is greater than each data element in {{mvar|q}} and less than each data element in {{mvar|r}}.