Minimum # Of PairsHappens when all internal nodes are 2-nodes.
2-3-4 Trees
LC P1 MC P2 RC 2-3 node structure 2-nodes waste space.
Overhead of moving a pair and pointers when changing between 2-node and 3-node use.
Extend to 2-3-4 tree, which may be represented as a binary tree. Problems with 2-3 trees.
Note that 2-3-4 trees waste even more space and require even more overhead when changing between a 3-node and a 4-node. However, 2-3-4 trees will be efficiently stored as binary search trees that will not have any of this overhead.
2-3-4 Tree Definition
Every internal node is either a 2-, 3-, or 4-node.
2- and 3-nodes have same properties as in a 2-3 tree.
A 4-node has 3 keys and 4 children; 1st key is smaller than 2nd key which is smaller than 3rd key.
All keys in left subtree are smaller than 1st key.
All keys in 2nd subtree are bigger than 1st key and smaller than 2nd key.
All keys in 3rd subtree are bigger than 2nd key and smaller than 3rd key.
All keys in right subtree are bigger than 3rd key.
All external nodes are on the same level.
4-node
10 30 35 k < 10 10 < k < 30 30 < k < 35 k > 35
Minimum # Of Pairs
Happens when all internal nodes are 2-nodes.
Minimum # Of Pairs
Number of nodes = 2h – 1, where h is tree height (excluding external nodes).
Each node has 1 (key, value) pair.
So, minimum # of pairs = 2h – 1
Maximum # Of Pairs
Happens when all internal nodes are 4-nodes.
Full degree 4 tree.
# of nodes = 1 + 4 + 42 + 43 + … + 4h-1 = (4h – 1)/3.
Each node has 3 pairs.
So, # of pairs = 4h – 1.
2-3-4 Tree Height Bounds
2h – 1 <= n <= 4h – 1.
log4(n+1) <= h <= log2(n+1).
Node Structure
LC P1 LMC P2 RC RMC P3 2-node uses LC, P1, and LMC.
3-node uses LC, P1, LMC, P2, and RMC.
4-node uses all fields.
Optional parent field.
Only internal nodes are represented!
LC = left child
P1 = first pair (key, value)
MC = middle child
P2 = second pair
RC = right child
Two-Pass Insert
A B C D E 10 20 30 40 Insert 20 and pointer to new 3-node into parent, as was done for 2-3 trees. 10 A B 20 30 40 C D E Move down from root to a leaf.
Insert in leaf.
If leaf now has 4 pairs, split as below.
Two-Pass Delete
Transform interior delete to leaf delete.
Delete from a 3-node or 4-node leaf reduces leaf degree.
Delete from a 2-node leaf.
Check one sibling and determine if it is a 3- or 4-node.
If so, borrow a pair and a subtree via parent node.
If not, combine with sibling 2-node and in-between pair in parent. Continue up the tree if parent was a 2-node.
One-Pass Operations
No bottom-to-top pass.
Can pipeline inserts.
Can pipeline deletes from leaf nodes.
Top-Down Insert
Bottom-up pass is triggered when new pair is inserted into a 4-node leaf.
Split 4-nodes on the way down so you never insert into a 4-node leaf!
Look before you leap!
If the node you are about to move to is a 4-node, split it into two 2-nodes.
Then move to a 2-node.
Cases For 4-node Move
The 4-node we attempt to move to may be:
The root.
Child of a 2-node.
Child of a 3-node.
It cannot be the child of a 4-node, because we will never be at a 4-node.
Root Is A 4-node
x y z a b c d x y z a b c d Height of tree increases by 1.
Compare with y and then move to x or z.
Note that this transformation doesn’t work for 2-3 trees. I.e., in a 2-3 tree we must avoid moving to 3-nodes. A 3-node root cannot be split in this manner.
4-node Left Child Of 2-node
w x y a b c d z e w z y a b c d x e No change in height of subtree.
Compare with x and then move to w or y.
4-node right child of 2-node is similar.
This transformation doesn’t work for a 2-3 tree either. When the left child is a 3-node, we cannot split it into 2 2-nodes to avoid moving to a 3-node.
4-node Left Child Of 3-node
v w x a b c d f z y e v x a b c d w y z f e No change in height of subtree.
Compare with w and then move to v or x.
4-node middle or right child of 3-node is similar.
Exercise – build a 2-3-4 tree Use one pass top-down insert to build a 2-3-4 tree from the following key values in sequence: 45, 28, 36, 22, 68, 50, 10, 98, 26, 15, 25, 27, 78
Top-Down Delete
Bottom-up pass is triggered when deletion is from a 2-node leaf.
Look before you leap!
May start at a 2-node root but may not be at any other 2-node.
If the node you are about to move to is a 2-node, make it a 3-node or 4-node.
Then move to the 3-node 4-node.
Cases For 2-node Move
Moving to a 2-node root is permitted.
No other move to a 2-node is permitted.
Other attempts to move to a 2-node may be classified as below.
The 2-node’s nearest sibling is also a 2-node.
The 2-node’s nearest sibling is a 3-node.
The 2-node’s nearest sibling is a 4-node.
In each of the preceding cases, the 2-node’s parent may be a 2-node root, a 3-node, or a 4-node.
Comments