(2,4) tree is a multi-way tree, which keeps the secondary data structure small; dmax = 4. So every node has at most 4 children.
Size: every node has between 2 and 4 children
Depth: all external nodes are at the same height
Because the secondary structure is bounded, the search through the secondary data structure is O(1) even for a vector ADT.
The depth property insures a balance tree
Also the height of the (2,4) tree storing n entries is O(lg n) because of depth property
The algorithms must maintain the properties.
Depth property
example
Insert new entry (k, x) into T
Search for k terminates at external node z with parent v.
Insert a new item (k, x, w) into v along with the additional external node w.
This may cause an overflow, in other words v becomes a 5-node with keys k1 < k2 < k3 < k4 .
If overflow then split v
Replace v with two nodes v' and v''.
v' a 3-node with children v1, v2, v3 storing k1 and k2
v'' is a 2-node with children v4 and v5 storing k4
If v is root then make new root u
u is parent of v in either case
Insert k3 into u and make v' and v'' children of u
Note the tree grows up through the root.
Would a parent sit idly as its child gets split in two? No! The parent gets involved.
Remove item with key k from tree T.
Search for k terminates at z such that ki = k
If z does not have external children then we must swap ki with node v that has only external children
Find the right most node v in subtree rooted at ith child of z (v has only external node children)
Swap the item ki at z with the last item v. Note we will remove item ki so the ordering will be OK
Else v = z // z originally only had external node children
Remove the item with k from v
This may cause and underflow in other words v becomes a 1-node.
If underflow then
If v's adjacent sibling, w, is 3-node or greater then transfer
move a key of u to v
move a key of w to parent u.
// which keys depends on which sibling we transfer from
If v's adjacent sibling is 2-node then fusion
merge v with adjacent sibling, w, making v'
move a key from the parent u to v'
// which keys depends on which sibling we fussing to
Check for underflow at u.
If root underflow then replace root with u (delete root)
Transfers and fusion are O(1) but cascading underflow may take O(lg n)
Previous classes call the transfer, “stealing from your bother”.
Also the fusion is called “killing your brother”.
Again I ask, will the parent sit idly
while siblings and children are stealing and killing?
Note that the cascading underflow causes the tree to shrink at the root.
Fusion does not seem like a Fusion in a (2, 4) tree because the node v is empty. For example in a (3, 5) tree then the node that has underflow is not empty and could be fussed. The essence of Fusion is that we are reducing the number children of the parent node, u, so we must remove a key from the parent and but it into the new node representing the fusion, v'.
Because the tree grows and shrink at the root then depth property is maintain, so the tree is balanced and the methods cost O(lg n).
|
Operation |
Time |
|
size, isEmpty |
O(1) |
|
find, insert, remove |
O(log n) |
|
findAll, reomveAll |
O(log n + s) |