2-4
Tree / 2-3-4 Tree
Size Property: Every node has at most four children
Depth
Property: All the external nodes have the same depth
Let’s
insert (k,e)
Search
for k in the 2-4 tree T. The search
will end up at an external node z if no element with key k.
Let
v be the parent of z. Insert (k,e) in
node v and add a new external child w to v.
Overflow – Node v becomes a 5-node
A
split has to be done on node v
1. Replace v with two nodes v’ and v’’
v’ is a 3-node storing keys k1 and k2
v’’ is a 2-node storing key k4
2. If v was the root of T, we create a new root
u. Else, let u be the parent of v
3.Put k3 into u and make v’ and v’’
children of u. If v was i-th child of
u, v’ is i-th child of u and v’’ is (i+1)st child of u
Let’s
delete (k,e)
Search
for key k in T.
Suppose
node z has (k,e), key k is the ith key in z and it has only internal-node
children. Then we need to find a node v
1.
We
find the right-most internal node v in the subtree rooted at the ith child of
z.
2.
We swap the item (k, x) at z with the last
item of v.
Underflow - If v was previously a
2-node, then it becomes a 1-node with no item after the deletion.
1. We find a sibling node w of v that is 3-node or 4-node.
2. Move a child of w to v, move a key of w to the parent
u of v, and move a key of u to v.
If v has only one sibling, or if both siblings of v
are 2-nodes, then fusion is needed.
Merge
v with a sibling and move a key from the parent u of v to the merged node.
Parent
u may suffer underflow after a fusion operation. Then transfer/fusion at u may be needed.
1.
Root Property: The root is black
2.
External Property: Every external node is black
3.
Internal Property: The children of a red node are black (A red node must have
two black children)
4.
Depth Property: All the external nodes have the same black depth.
We
search for an external node z in T so that we can make z as internal node and
store (k,e) in it (expandExternal(z)).
Color
z with red and its children with black
If
parent v of z is red, then the parent u of v must be black (rule 3).
Node
v cannot be the root (rule 1) if v is red.
Since
the parent v and z are red, there is a double red at node z.
Case
1. The sibling w of v is black
Rotate(z) (just like section 7.4 in AVL p.270)
Recall: After rotation, node b is the root of the
subtree and nodes a and c are the children of b. Color b black and color a and c red.
Case
2. The Sibling w of v is red
Color
v and w black and their parent u red (Exception: if u is the root, it is
colored black)
If
u is not the root, the double red problem may occur on both node u and its
parent. So, recoloring/rotation may be
needed. We need to propagate up until
double red problem is resolved.
Let’s
delete (k,e) from T
Search
key k in tree T.
Suppose
node u store k, and node u does not have an external child. Then we find the internal node v so that we
can move the item at v to u and delete v from the tree T.
To
delete node v, which has an external node w, from the tree T, we do the
following.
Suppose
r is the sibling of w and x be the parent of v.
1.
We
remove nodes v and w and make r a child of x.
2.
If
node v is red, we are done.
3.
If
r is red, we color it black and we are done with the deletion process. Otherwise, we need to do more. Node r is colored with double black.
Case
1: The sibling y of r is black and has a red child z.
Rotate(z)
Color
a and c black, color b with the former color of x, and color r black.
Case
2: The sibling y of r is black and both children of y are black.
Recoloring:
we color r black, color y red. If x is
red, we color it black else we color it double black.
Since
x can be double black, we need to propagate up; we consider three cases for x
again.
Case
3: The sibling y of r is red.
We
perform an adjustment.
If
y is the right child of x, let z be the right child of y. Otherwise, let z be the left child of y.
Rotate(z)
– After the rotation, y becomes the parent of x.
Color
y black and x red. The sibling of r is
black.
We
apply either case 1 or case 2 to node r to complete the deletion operation.