Next:5.3.1 2-3 Trees: InsertionUp:5. Balanced TreesPrevious:5.2.3 Red-Black Trees: Deletion

# 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

 p1 : Pointer to the first child p2 : Pointer to the second child p3 : Pointer to the third child k1 : Smallest key that is a descendent of the second child k2 : Smallest key that is a descendent of the third child

Leaf Node
 key other fields

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

Example: See Figure 5.23

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 k1 and k2 be the two values stored here.
• 1.
If x < k1, move to the first child
2.
If x k1 and the node has only two children, move to the second child
3.
If x k1 and the node has three children, move to the second child if x < k2 and to the third child if x k2.
• 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 2k - 1 and 3k - 1 leaves
• Thus a 2-3 tree with n elements (leaves) requires

• at least 1 + log3n levels

at most 1 + log2n levels

Next:5.3.1 2-3 Trees: InsertionUp:5. Balanced TreesPrevious:5.2.3 Red-Black Trees: Deletion
eEL,CSA_Dept,IISc,Bangalore