A 2–3-4 trees is a B-tree of order 4.
It is balanced, meaning that each right, center 0, center 1, and left subtree contains the same or close to the same amount of data.
Any internal node has children node vary between 2 ~ 4 (Every node in a 2-3-4 tree is either a leaf, or has either 2 or 3 or 4 children).
Abstract Data Type (ADT)
template<class Type>
struct node234
{
Type *data[3];
node234<Type> *child[4];
};
Get number of node in a 2-3-4 tree
template<class Type>
int Tree234_size(node234<Type>* root)
{
return ((root) ? Tree234_size(root->child[0]) + Tree234_size(root->child[1]) +
Tree234_size(root->child[2]) + Tree234_size(root->child[3]) + 1 : 0);
}
Get level of tree height
template<class Type>
int Tree234_height(node234<Type> * root)
{
return ((root) ? Tree234_height(root->child[1]) + 1 : 0);
}
Display data of 2-3 tree in order
// Return # of nodes
templat<class Type>
int Tree234_display(node234<Type> * root)
{
int count = 0;
if(root)
{
count = Tree234_display(root->child[0]) + 1;
if (root->data[0])
cout << *(root->data[0]) << " ";
count += Tree234_display(root->child[1]);
if (root->data[1]) // middle data must exist
cout << *(root->data[1]) << " ";
count += Tree234_display(root->child[2]);
if (root->data[2])
cout << *(root->data[2]) << " ";
count += Tree234_display(root->child[3]);
}
return count;
}
Copy data from a 2-3-4 tree to another 2-3-4 tree
// Return number of nodes copied
template<class Type>
int Tree234_copy(node234<Type> * &destination, node234<Type>* source)
{
int count = 0;
if (source)
{
++count;
destination = new node234<Type>;
int i;
for (i = 0; i < 3; ++i)
{
if (*(source->data + i))
{
*(destination->data + i) = new Type;
**(destination->data + i) = **(source->data + i);
}
else
*(destination->data + i) = 0;
}
for (i = 0; i < 4; ++i)
count += Tree234_copy(*(destination->child + i), *(source->child + i));
}
else
destination = NULL;
return count;
}
Insert data into a 234 tree
Process:
1. Start from root, going down
2. If encounter a node with 3 data, do split, then go back to where it is
3. If root node has 3 data, create a new root node at the begin
4. keep moving down to a leaf
5. always insert to an end leaf
This operation has 3 functions:
1. A recursive traversal function
2. Splitting function to split a child node from a parent node.
3. Inserting function to insert a data into a node of 2-3-4 tree.
template<class Type>
void Tree234_insert(const Type &insert, node234<Type>* &root, node234<Type>* parent)
{
if (root)
{
if (root->data[0] && root->data[2]) // 3 data in a node, split this node
{
Tree234_split(insert, root, parent);
}
else if (!root->child[1]) // no children, end leaf with 1 or 2 data
{
Tree234_insert_at_node(insert, root);
//return 1;
}
else // 1 or 2 data with children
{
if (insert < *(root->data[1]))
{
if (root->data[0] && insert < *(root->data[0]))
Tree234_insert(insert, root->child[0], root);
else
Tree234_insert(insert, root->child[1], root);
}
else
{
if (!root->data[2] || insert < *(root->data[2]))
Tree234_insert(insert, root->child[2], root);
else
Tree234_insert(insert, root->child[3], root);
}
}
}
else // root is NULL, insert the 1st node
{
Tree234_insert_at_node(insert, root);
//return 1;
}
}
/*
split a node having 3 data inside
*/
template<class Type>
void Tree234_split(const Type &insert, node234<Type>* &root, node234<Type>* parent)
{
if (parent)
{
node234<Type> *temp = new node234<Type>;
if (root == parent->child[0])
{
parent->data[2] = parent->data[1];
parent->data[1] = parent->data[0];
parent->data[0] = root->data[1];
parent->child[3] = parent->child[2];
parent->child[2] = parent->child[1];
parent->child[1] = temp;
root->data[1] = root->data[0];
temp->data[1] = root->data[2];
temp->child[1] = root->child[2];
temp->child[2] = root->child[3];
root->child[2] = root->child[1];
root->child[1] = root->child[0];
root->data[0] = root->data[2] = temp->data[0] = temp->data[2] = NULL;
root->child[0] = root->child[3] = temp->child[0] = temp->child[3] = NULL;
if (insert < *(parent->data[0]))
Tree234_insert(insert, parent->child[0], parent);
else
Tree234_insert(insert, parent->child[1], parent);
}
else if (root == parent->child[3])
{
parent->data[0] = parent->data[1];
parent->data[1] = parent->data[2];
parent->data[2] = root->data[1];
parent->child[0] = parent->child[1];
parent->child[1] = parent->child[2];
parent->child[2] = temp;
root->data[1] = root->data[2];
temp->data[1] = root->data[0];
temp->child[1] = root->child[0];
temp->child[2] = root->child[1];
root->child[1] = root->child[2];
root->child[2] = root->child[3];
root->data[0] = root->data[2] = temp->data[0] = temp->data[2] = NULL;
root->child[0] = root->child[3] = temp->child[0] = temp->child[3] = NULL;
if (insert < *(parent->data[2]))
Tree234_insert(insert, parent->child[2], parent);
else
Tree234_insert(insert, parent->child[3], parent);
}
else if (root == parent->child[1])
{
if (parent->data[0])
{
parent->data[2] = parent->data[1];
parent->data[1] = root->data[1];
parent->child[3] = parent->child[2];
parent->child[2] = temp;
temp->data[1] = root->data[2];
root->data[1] = root->data[0];
temp->child[1] = root->child[2];
temp->child[2] = root->child[3];
root->child[2] = root->child[1];
root->child[1] = root->child[0];
root->data[0] = root->data[2] = temp->data[0] = temp->data[2] = NULL;
root->child[0] = root->child[3] = temp->child[0] = temp->child[3] = NULL;
if (insert < *(parent->data[1]))
Tree234_insert(insert, parent->child[1], parent);
else
Tree234_insert(insert, parent->child[2], parent);
}
else
{
parent->data[0] = root->data[1];
parent->child[0] = temp;
temp->data[1] = root->data[0];
root->data[1] = root->data[2];
temp->child[1] = root->child[0];
temp->child[2] = root->child[1];
root->child[1] = root->child[2];
root->child[2] = root->child[3];
root->data[0] = root->data[2] = temp->data[0] = temp->data[2] = NULL;
root->child[0] = root->child[3] = temp->child[0] = temp->child[3] = NULL;
if (insert < *(parent->data[0]))
Tree234_insert(insert, parent->child[0], parent);
else
Tree234_insert(insert, parent->child[1], parent);
}
}
else // child[2]
{
if (parent->data[2])
{
parent->data[0] = parent->data[1];
parent->data[1] = root->data[1];
parent->child[0] = parent->child[1];
parent->child[1] = temp;
temp->data[1] = root->data[0];
root->data[1] = root->data[2];
temp->child[1] = root->child[0];
temp->child[2] = root->child[1];
root->child[1] = root->child[2];
root->child[2] = root->child[3];
root->data[0] = root->data[2] = temp->data[0] = temp->data[2] = NULL;
root->child[0] = root->child[3] = temp->child[0] = temp->child[3] = NULL;
if (insert < *(parent->data[1]))
Tree234_insert(insert, parent->child[1], parent);
else
Tree234_insert(insert, parent->child[2], parent);
}
else
{
parent->data[2] = root->data[1];
parent->child[3] = temp;
temp->data[1] = root->data[2];
root->data[1] = root->data[0];
temp->child[1] = root->child[2];
temp->child[2] = root->child[3];
root->child[2] = root->child[1];
root->child[1] = root->child[0];
root->data[0] = root->data[2] = temp->data[0] = temp->data[2] = NULL;
root->child[0] = root->child[3] = temp->child[0] = temp->child[3] = NULL;
if (insert < *(parent->data[2]))
Tree234_insert(insert, parent->child[2], parent);
else
Tree234_insert(insert, parent->child[3], parent);
}
}
}
else // 1st node
{
node234<Type> *left = new node234<Type>, *right = new node234<Type>;
left->data[1] = root->data[0];
right->data[1] = root->data[2];
left->child[1] = root->child[0];
left->child[2] = root->child[1];
right->child[1] = root->child[2];
right->child[2] = root->child[3];
root->child[1] = left;
root->child[2] = right;
left->data[0] = left->data[2] = right->data[0] = right->data[2] = root->data[0] = root->data[2] = NULL;
left->child[0] = left->child[3] = right->child[0] = right->child[3] = root->child[0] = root->child[3] = NULL;
Tree234_insert(insert, root);
}
}
/*
Insert a data into an end node
*/
template<class Type>
void Tree234_insert_at_node(const Type &insert, node234<Type>* &root)
{
if (root)
{
if (insert < *(root->data[1]))
{
if (root->data[0])
{
if (insert < *(root->data[0])) // 1st
{
root->data[2] = root->data[1];
root->data[1] = root->data[0];
root->data[0] = new Type;
*(root->data[0]) = insert;
}
else // 2nd
{
root->data[2] = root->data[1];
root->data[1] = new Type;
*(root->data[1]) = insert;
}
}
else // 1st
{
root->data[0] = new Type;
*(root->data[0]) = insert;
}
}
else
{
if (root->data[2])
{
if (insert <= *(root->data[2])) // 2nd
{
root->data[0] = root->data[1];
root->data[1] = new Type;
*(root->data[1]) = insert;
}
else // 3rd
{
root->data[0] = root->data[1];
root->data[1] = root->data[2];
root->data[2] = new Type;
*(root->data[2]) = insert;
}
}
else // 3rd
{
root->data[2] = new Type;
*(root->data[2]) = insert;
}
}
}
else
{
root = new node234<Type>;
root->data[1] = new Type;
*(root->data[1]) = insert;
root->child[0] = root->child[1] = root->child[2] = root->child[3] = NULL;
root->data[0] = root->data[2] = NULL;
}
}
Clear a 2-3-4 tree
// Return # of node deleted
template<class Type>
int Tree234_clear(node234<Type> *&root)
{
int count = 0;
if (root)
{
++count;
for (int i = 0; i < 4; ++i) count += Tree234_clear(root->child[i]);
for (int i = 0; i < 3; ++i) if (root->data[i])
delete root->data[i];
delete root;
root = 0;
}
return count;
}
Kanra 
