04-07-2012, 02:07 PM
Seminar on 2-3 Trees
2-3 Trees.ppt (Size: 361.5 KB / Downloads: 148)
INTRODUCTION
What Is a 2-3 Tree?
Definition: A 2-3 tree is a tree in which each internal node(nonleaf) has either 2 or 3 children, and all leaves are at the same level.
2-3 Trees
a node may contain 1 or 2 keys
all leaf nodes are at the same depth
all non-leaf nodes (except the root) have either 1 key and two subtrees, or 2 keys and three subtrees
insertion is at the leaf: if the leaf overflows, split it into two leaves, insert them into the parent, which may also overflow
deletion is at the leaf: if the leaf underflows (has no items), merge it with a sibling, removing a value and subtree from the parent, which may also underflow
the only changes in depth are when the root splits or underflows
2-3 Tree vs. Binary Tree
A 2-3 tree is not a binary tree since a node in the 2-3 tree can have three children.
A 2-3 tree does resemble a full binary tree.
If a 2-3 tree does not contain 3-nodes, it is like a full binary tree since all its internal nodes have two children and all its leaves are at the same level.
If a 2-3 tree does have three children, the tree will contain more nodes than a full binary tree of the same height.
Therefore, a 2-3 tree of height h has at least 2^h - 1 nodes.
In other words, a 2-3 tree with N nodes never has height greater then log (N+1), the minimum height of a binary tree with N nodes.
The Advantages of the 2-3 trees
Even though searching a 2-3 tree is not more efficient than searching a binary search tree, by allowing the node of a 2-3 tree to have three children, a 2-3 tree might be shorter than the shortest possible binary search tree.
Maintaining the balance of a 2-3 tree is relatively simple than maintaining the balance of a binary search tree .
The Insertion Algorithm
To insert an item I into a 2-3 tree, first locate the leaf at which the search for I would terminate.
Insert the new item I into the leaf.
If the leaf now contains only two items, you are done. If the leaf contains three items, you must split it.
Deleting from a 2-3 Tree
The deletion strategy for a 2-3 tree is the inverse of its insertion strategy. Just as a 2-3 tree spreads insertions throughout the tree by splitting nodes when they become too full, it spreads deletions throughout the tree by merging nodes when they become empty.
Example: