5.3 2-3 Trees

Definition

• A 2-3 Tree is a null tree (zero nodes) or a single node tree (only one node) or a multiple node tree with the following properties:

1.

Each interior node has two or three children

2.

Each path from the root to a leaf has the same length.

Fields of a Node :

Internal Node

p1

k1

p2

k2

p3

p₁ : Pointer to the first child

p₂ : Pointer to the second child

p₃ : Pointer to the third child

k₁ : Smallest key that is a descendent of the second child

k₂ : Smallest key that is a descendent of the third child

Leaf Node

key	other fields

$\bullet$ Records are placed at the leaves. Each leaf contains a record (and key)

Example: See Figure 5.23
 
 

Figure 5.23: An example of a 2-3 tree

Search

• The values recorded at the internal nodes can be used to guide the search path.
• To search for a record with key value x, we first start at the root. Let k₁ and k₂ be the two values stored here.

1.

If x < k₁, move to the first child

2.

If x $\geq$k₁ and the node has only two children, move to the second child

3.

If x $\geq$k₁ and the node has three children, move to the second child if x < k₂ and to the third child if x $\geq$k₂.

• Eventually, we reach a leaf. x is in the tree iff x is at this leaf.

Path Lengths

• A 2-3 Tree with k levels has between 2^{k - 1} and 3^{k - 1} leaves
• Thus a 2-3 tree with n elements (leaves) requires


at least 1 + log₃n levels

at most 1 + log₂n levels