2-3-4 Trees

A variation on the B-Tree is a 2-3-4 Tree, which is a multiway tree in which all non-leaf nodes have 2, 3, or 4 children. Therefore:

1. Each node stores at most 3 values
2. Each internal node is a 2-node, 3-node, or 4-node
3. All the leaves are on the same level

Processing a 2-3-4 Tree

Searching is the same as with multiway search trees.

Insertion into a 2-3-4 Tree begins with a single node where values are inserted until it becomes full (ie. until it becomes a 4-node). The next value that is inserted will cause a split into two nodes: one containing values less than the median value and the other containing values greater than the median value. The median value is then stored in the parent node. It's possible that insertion could cause splitting up to the root node.

Insert the values 53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65, 60, 46, 55, 33, 68, 79, and 48.

Inserting the 25 results in a split:

Inserting 38 causes a split:

Inserting 73 causes a split:

Inserting 46 results in a split that propagates up to the root:

Inserting 55 causes a split:

Deletion from a 2-3-4 Tree will always occurs in a leaf node.

• If the value to be deleted is in a leaf node and that node is a 3 or 4-node, then deletion is simple - the value is removed and the node becomes a 2 or 3 node, respectively.
• If the value to be deleted is in a leaf node and that node is a 2 node, then underflow occurs. Underflow is "fixed" by transferring a value from the parent node to the node where underflow occurs and transferring a value from a sibling that is a 3 or 4-node. If the node where underflow occurred doesn't have a sibling that is a 3 or 4-node, then fusion occurs. The fusion requires the underflow node become a 3-node that contains the value from the sibling node and the separating value from the parent.
• If the value to be deleted is NOT in a leaf node, then it is replaced by its immediate predecessor and the predecessor value is deleted from the tree.

Storage

A 2-3-4 Tree can be stored in the same manner as a B-Tree, but for small amounts of data that isn't located on external storage devices it would be ideal to store the information as a binary search tree. The only thing that must be distinguished is whether values are contained within a 2-3-4 node or whether they are located in child nodes. Let links between value within a node be represented with red links and links between parent/child values be represented by black links. Therefore:

A 2-node:

    results in    

A 3-node:

    results in        OR   

A 4-node:

    results in   

Red-Black Trees

This type of representation results in a Red-Black Tree, which is a binary search tree with two types of links/nodes, red and black, that satisfy the following properties:

• black condition - every path from the root to a leaf node has the same number of black links/nodes
• red condition - no path from the root a leaf node has two or more consecutive red links/nodes (ie. every red node will have a black parent)
• the root is always black

The nodes in a Red-Black Tree might be represented as follows:

template <class T>
class RedBlackNode
{
public:
  ...
  
private:
  T data;
  char color;     // 'R' if the incoming link is red, 'B' if the incoming link is black
  RedBlackNode *leftChild, *rightChild;
};

Processing Red-Black Trees

Insertion

A value is inserted into the tree using the standard binary search tree algorithm, however a decision must be made as to whether it should be inserted as a red or black link/node. If the node is inserted as a black link/node, then the number of black links/nodes in the one path would increase, which would violate the black condition. Therefore the node will be inserted as a red link/node.

This could result in a violation of the red condition but that can be fixed by performing either a color change or a rotation. Three possible cases arise:

Case 1: If the parent node is a black node, then insertion is finished.

Case 2: If the parent node is a red node and the aunt/uncle node is black.

Case 2a: If the node was inserted into the left child of the left child of the grandparent, then the violation is fixed by performing a single right rotation.

Case 2b: If the node was inserted into the right child of the right child of the grandparent, then the violation is fixed by performing a single left rotation.

Case 2c: If the node was inserted into the right child of the left child of the grandparent, then the violation is fixed by performing a left-right rotation.

Case 2d: If the node was inserted into the left child of the right child of the grandparent, then the violation is fixed by performing a right-left rotation.

After all of the rotations, the parent node is made black and the child nodes are made red.

Case 3: If the parent node is a red node and the aunt/uncle node is red.

The parent and aunt/uncle nodes will be made black and the grandparent node will be made red. The exception to the grandparent becoming red is if the grandparent is the root of the tree - in this case it will remain black.

                    OR if 84 is the root, then   

Fixing one violation of the red condition could cause it to propagate up the tree. The violations should be fixed until the root of the tree is reached.